Module: Connected::Graph

Includes:
Comparable
Included in:
GenericGraph
Defined in:
lib/connected/graph.rb

Overview

A collection of related vertices and edges

Instance Method Summary collapse

Instance Method Details

#<=>(other) ⇒ Object 



69
70
71
 
# File 'lib/connected/graph.rb', line 69

def <=>(other)
  vertices == other.vertices && edges == other.edges
end

#adjacency_matrix ⇒ Object 



13
14
15
16
17
18
19
20
 
# File 'lib/connected/graph.rb', line 13

def adjacency_matrix
  rows = @vertices.map do |i|
    @vertices.map do |j|
      i == j || i.neighbors.include?(j) ? 1 : 0
    end.to_a
  end.to_a
  Matrix.rows(rows)
end

#complete? ⇒ Boolean

A “complete graph” is one where all vertices connect to all others

Returns:

  • (Boolean) 


23
24
25
 
# File 'lib/connected/graph.rb', line 23

def complete?
  density == 1 || vertices.size == 1
end

#density ⇒ Object

The density is the ratio to a complete graph of the same number of vertices



28
29
30
31
32
33
34
 
# File 'lib/connected/graph.rb', line 28

def density
  return 0 if edges.size.zero? # otherwise we'd divide by 0!

  # Assumes an directed graph for now, therefore e / n(n -1)
  # is the ratio of edges (e) to edges in a complete graph
  edges.size.to_f / ((vertices.size * (vertices.size - 1)))
end

#diameter ⇒ Object

The diameter of a graph is the longest of all shortest paths between all vertices on a graph



37
38
39
40
41
42
43
44
45
 
# File 'lib/connected/graph.rb', line 37

def diameter
  longest = nil
  vertices.each do |v|
    dist = v.eccentricity
    longest = dist if longest.nil? || dist > longest
  end

  longest
end

#edges ⇒ Object 



47
48
49
 
# File 'lib/connected/graph.rb', line 47

def edges
  @edges || vertices.map(&:connections).flatten.uniq
end

#initialize(vertices:, edges: nil) ⇒ Object 



8
9
10
11
 
# File 'lib/connected/graph.rb', line 8

def initialize(vertices:, edges: nil)
  @vertices = vertices
  @edges = edges
end

#length ⇒ Object 



51
52
53
 
# File 'lib/connected/graph.rb', line 51

def length
  edges.size
end

#radius ⇒ Object 



55
56
57
58
59
60
61
62
63
 
# File 'lib/connected/graph.rb', line 55

def radius
  shortest = nil
  vertices.each do |v|
    ecc = v.eccentricity
    shortest = ecc if shortest.nil? || ecc < shortest
  end

  shortest
end

#vertices ⇒ Object 



65
66
67
 
# File 'lib/connected/graph.rb', line 65

def vertices
  @vertices
end