Class: AbstractGraph::Graph

Inherits:
Object
  • Object
show all
Includes:
Composition
Defined in:
lib/abstract_graph/graph.rb,
lib/abstract_graph/graph/dup.rb,
lib/abstract_graph/graph/add_edge.rb,
lib/abstract_graph/graph/has_edge.rb,
lib/abstract_graph/graph/connected.rb,
lib/abstract_graph/graph/add_vertex.rb,
lib/abstract_graph/graph/has_vertex.rb,
lib/abstract_graph/graph/initialize.rb,
lib/abstract_graph/graph/delete_edge.rb,
lib/abstract_graph/graph/is_adjacent.rb,
lib/abstract_graph/graph/split_vertex.rb,
lib/abstract_graph/graph/delete_vertex.rb,
lib/abstract_graph/graph/get_edge_name.rb,
lib/abstract_graph/graph/adjacency_list.rb,
lib/abstract_graph/graph/merge_vertices.rb,
lib/abstract_graph/graph/change_edge_name.rb,
lib/abstract_graph/graph/change_vertex_name.rb,
lib/abstract_graph/graph/templates/path_graph.rb,
lib/abstract_graph/graph/templates/cycle_graph.rb,
lib/abstract_graph/graph/templates/complete_graph.rb,
lib/abstract_graph/graph/templates/petersen_graph.rb,
lib/abstract_graph/graph/templates/complete_bipartite_graph.rb

Overview

public Graph class

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

d: Initializes a graph a: Creates a vertex and edge UNC and links them to share namespace t: constant p: r: new graph



11
12
13
14
15
16
17
 
# File 'lib/abstract_graph/graph/initialize.rb', line 11

def initialize

  @vertices = UniqueNameCollection.new
  @edges = UniqueNameCollection.new
  @vertices.link @edges

end

Instance Attribute Details

#edges ⇒ Object

Returns the value of attribute edges.



12
13
14
 
# File 'lib/abstract_graph/graph.rb', line 12

def edges
  @edges
end

#vertices ⇒ Object

Returns the value of attribute vertices.



11
12
13
 
# File 'lib/abstract_graph/graph.rb', line 11

def vertices
  @vertices
end

Class Method Details

.complete_bipartite_graph(n, m) ⇒ Object

d: Create a complete bipartite graph K(n,m). a: It first adds the vertices, then adds the edges. The vertices are named “v(2^i)” from

the first set being i=2^0..n-1, and the second set i=2^n..m+n-1. The edges are sums "e(i)"
where i=sum of two vertices

t: n * m * t(add_edge) + max(n,m) * t(add_vertex) p: n is the number of vertices in the first set, m is number of vertices in second set r: a complete bipartite graph



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/abstract_graph/graph/templates/complete_bipartite_graph.rb', line 14

def complete_bipartite_graph n, m
  result = new

  # add the vertices to the graph
  vertexN = (0..n-1).map do |i|
    vName = 2**i
    result.add_vertex "v#{vName}"
    vName
  end
  vertexM = (0..m-1).map do |i|
    vName = 2**(n+i)
    result.add_vertex "v#{vName}"
    vName
  end

  # add the edges to the graph, and make sure they're
  # connected to the other set
  vertexN.each do |vn|
    vertexM.each do |vm|
      result.add_edge "e#{vn + vm}", "v#{vn}", "v#{vm}"
    end
  end

  result
end

.complete_graph(n) ⇒ Object

d: Create a complete graph K(n). a: It adds n vertices, named “v(i)”, i=2^0..n-1. Then adds the edges, the name being sum

"e(i)" where i is sum of two connecting vertices.

t: n * t(add_vertex) + C(n,2) * t(add_edge) p: n is number of vertices r: a complete graph



13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/abstract_graph/graph/templates/complete_graph.rb', line 13

def complete_graph n
  result = new
  vertexNames = n.times.collect { |i| 2**i }
  vertexNames.each do |i|
    result.add_vertex "v#{i}"
  end
  vertexNames.combination(2).each do |i,j|
    result.add_edge( "e#{i+j}", "v#{i}", "v#{j}" )
  end
  result
end

.cycle_graph(n) ⇒ Object

d: Create a cycle graph a: Create the vertices and edges at the same time. The naming scheme is power of two for

vertices and the sum of vertices for edges.

t: n * (t(add_vertex) + t(add_edge)) p: n is the number of vertices r: a cycle graph



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/abstract_graph/graph/templates/cycle_graph.rb', line 13

def cycle_graph n
  result = new
  vertexNames = (n-1).times.collect { |i| 2**(i + 1) }
  lastVertex  = 2**(n-1)

  # insert first vertex
  result.add_vertex "v1"
  vertexNames.each do |i|
    # insert the rest of the vertices
    result.add_vertex "v#{i}"
    # insert the edge with the previous vertex
    result.add_edge "e#{i + i/2}", "v#{i}", "v#{i/2}"
  end

  #insert the closing loop
  result.add_edge "e#{1 + lastVertex}", "v1", "v#{lastVertex}"

  result
end

.path_graph(n) ⇒ Object

d: Returns a path. a: It creates a path.by adding vertices and edges at the same time, vertices named “v(i)”

i=2^0..n-1, and edges "e(i)" where i is sum of vertices adjacent.

t: n * (t(add_vertex) + t(add_edge)) p: n is the number of vertices r: a path graph



13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/abstract_graph/graph/templates/path_graph.rb', line 13

def path_graph n
  result = new

  # add the first vertex
  result.add_vertex "v1"
  (1..n-1).each do |i|
    # add the rest of them
    result.add_vertex "v#{2**i}"
    result.add_edge "e#{2**i + 2**(i-1)}", "v#{2**i}", "v#{2**(i-1)}"
  end

  result
end

.petersen_graph ⇒ Object

d: Create a peterson graph. a: It adds 10 vertices “v(i)”, i=2^0..9. Then adds the specified edges, according to the

specified edges array.

t: constant p: none r: a peterson graph create a petersen graph. ie, a 3 regular graph with 10 vertices and 15 edges



15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/abstract_graph/graph/templates/petersen_graph.rb', line 15

def petersen_graph
  result = new

  vertexNames = []
  # add all the vertices
  10.times do |i|
    vName = 2**i
    vertexNames << vName
    result.add_vertex "v#{vName}"
  end

  specifiedEdges = [
  [0, 1], [0, 5], [0, 4],
  [1, 2], [2, 3], [3, 4],
  [1, 6], [2, 7], [3, 8],
  [4, 9], [5, 8], [5, 7],
  [6, 9], [7, 9], [6, 8]]

  specifiedEdges.each do |edge1, edge2|
    result.add_edge "e#{vertexNames[edge1] + vertexNames[edge2]}", "v#{vertexNames[edge1]}", "v#{vertexNames[edge2]}"
  end

  result
end

Instance Method Details

#add_edge(s, v1, v2) ⇒ Object

d: Add an edge to graph. a: Ensure the two vertices exist, then add the edge and check it’s not coincident with any

other edge.

t: |edges| p: s is name of edge, v1 and v2 are names of the two vertices r: returns the graph itself

Raises:

  • (Exception) 


12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/abstract_graph/graph/add_edge.rb', line 12

def add_edge( s, v1, v2 )
  v1 = @vertices.find(v1) or return nil
  v2 = @vertices.find(v2) or return nil

  raise Exception.new( "AddEdge: Same vertices passed, #{v1.name}" ) if v1 == v2

  # create the edge
  edge = Edge.new s, v1, v2

  # check if it's an multiple edge
  @edges.each do |e|
    raise Exception.new( "AddEdge: Multiple edge being added between #{v1.name}, #{v2.name}" ) if e.is_coincident? edge
  end

  @edges.add edge
  self
end

#add_vertex(s) ⇒ Object

d: Add a vertex to graph. a: Adds the new vertex. t: constant p: s is the name of the vertex r: returns the graph itself



11
12
13
14
15
16
 
# File 'lib/abstract_graph/graph/add_vertex.rb', line 11

def add_vertex( s )
  # create the vertex
  vertex = Vertex.new s
  @vertices.add vertex
  self
end

#adjacency_list(s) ⇒ Object

d: Return adjacent vertices a: Go through the edges and collect all the vertex names, subtracting our own. Thus, only the

'vertices' tuples that have one vertex left are adjacent since the other vertex got deleted.
Then, we can use the remaining array and return it.

t: |edges| p: s is the name of vertex r: returns nil if nothing, returns array of adjacent vertices’ names



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/abstract_graph/graph/adjacency_list.rb', line 13

def adjacency_list( s )
  # this collects all the edges at first
  result = @edges.collect do |e|
    e.vertices.collect do |v|
      v.name
    end - [s]
  end.delete_if do |adj|
    # and deletes the ones with only one remaining tracked
    adj.size == 2
  end.flatten

  # return nil if result is empty
  if result.size == 0
    return nil
  else
    return result
  end
end

#change_edge_name(s, snew) ⇒ Object

d: Change the name of an edge a: Changes the name of an edge by checking existing names and then adding our own t: t(rename), which is |edges + vertex| p: s is current name of edge, snew is requested name of edge r: returns graph if everything goes well, nil if it failed



11
12
13
14
 
# File 'lib/abstract_graph/graph/change_edge_name.rb', line 11

def change_edge_name( s, snew )
  return nil unless @edges.rename(s, snew)
  self
end

#change_vertex_name(s, snew) ⇒ Object

d: Change the name of an vertex a: Changes the name of an vertex by checking existing names and then adding our own t: t(rename), which is |edges + vertex| p: s is current name of vertex, snew is requested name of vertex r: returns graph if everything goes well, nil if it failed



11
12
13
14
 
# File 'lib/abstract_graph/graph/change_vertex_name.rb', line 11

def change_vertex_name( s, snew )
  return nil if @vertices.rename(s, snew).nil?
  self
end

#connected? ⇒ Boolean

d: Check if graph is connected a: Do a depth first search. So we push the first vertex, and then keep trying to go to adjacent

vertices until all of them are seen. In the end, check if the list of seen vertices is the
same as the complete vertex list.

t: |vertices| * t(adjacency_list) which is |vertices| * |edges| p: none r: returns true if graph is connected, false otherwise

Returns:

  • (Boolean) 


13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
# File 'lib/abstract_graph/graph/connected.rb', line 13

def connected?
  return true if @vertices.empty?
  seen = []
  toSee = [@vertices.first.name]

  # go through vertices and if we seen them, don't inspect them
  # essentially does a depth first search
  while !toSee.empty? do
    inspect = toSee.pop
    seen << inspect

    adjacentVertices = adjacency_list( inspect )
    break if adjacentVertices.nil?

    # add adjacent vertices if they're not in any of the seen lists
    adjacentVertices.each do |v|
      toSee << v if !seen.include?( v ) && !toSee.include?( v )
    end
  end
  seen.size == @vertices.size
end

#delete_edge(s) ⇒ Object

d: Delete an edge. a: Deletes the edge. t: constant p: s is the edge name r: graph itself



11
12
13
14
 
# File 'lib/abstract_graph/graph/delete_edge.rb', line 11

def delete_edge( s )
  other = self.dup
  other.delete_edge! s
end

#delete_edge!(s) ⇒ Object 



16
17
18
19
 
# File 'lib/abstract_graph/graph/delete_edge.rb', line 16

def delete_edge!( s )
  @edges.delete s
  self
end

#delete_vertex(s) ⇒ Object

d: Delete an vertex. a: Deletes the vertex. t: constant p: s is the vertex name r: graph itself



11
12
13
14
 
# File 'lib/abstract_graph/graph/delete_vertex.rb', line 11

def delete_vertex( s )
  other = self.dup
  other.delete_vertex! s
end

#delete_vertex!(s) ⇒ Object 



16
17
18
19
 
# File 'lib/abstract_graph/graph/delete_vertex.rb', line 16

def delete_vertex!( s )
  @vertices.delete s
  self
end

#dup ⇒ Object

d: Copies the graph. a: Does a deep copy, but does not dup vertex/edge so modifying them will affect both graphs.

Copies vertices then edges.

t: |vertices| + |edges| p: none r: returns the copy graph



12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/abstract_graph/graph/dup.rb', line 12

def dup
  other = self.class.new
  # cannot call UniqueNameCollection#dup because we'll lose
  # link data
  @vertices.each do |v|
    other.vertices.add v
  end
  @edges.each do |e|
    other.edges.add e
  end
  other
end

#get_edge_name(v1, v2) ⇒ Object

d: Returns the edge name given two vertex names. a: Goes through all the edges and see if any of them have the same vertices as

the ones we are requesting.

t: |edges| p: the names of the two vertices r: nil if edge if nothing, name of edge(string) if found



12
13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/abstract_graph/graph/get_edge_name.rb', line 12

def get_edge_name( v1, v2 )
  vertices = [v1, v2].sort!

  @edges.each do |e|
    eVertices = e.vertices.map do |v|
      v.name
    end.sort

    return e.name if eVertices == vertices
  end

  nil
end

#has_edge?(s) ⇒ Boolean

d: Checks if graph has the edge. a: Run find on @edges and existance it. t: constant p: name of edge r: true/false depending if edge with name s exists

Returns:

  • (Boolean) 


11
12
13
 
# File 'lib/abstract_graph/graph/has_edge.rb', line 11

def has_edge?( s )
  !(@edges.find s).nil?
end

#has_vertex?(s) ⇒ Boolean

d: Checks if the graph has the vertex. a: Run find on @vertices and existance it. t: constant p: name of vertex r: true/false depending if vertex with name s exists

Returns:

  • (Boolean) 


11
12
13
 
# File 'lib/abstract_graph/graph/has_vertex.rb', line 11

def has_vertex?( s )
  !(@vertices.find s).nil?
end

#is_adjacent?(v1, v2) ⇒ Boolean

d: Check if two vertices are adjacent. a: Go through the edges and check if any of the edges have the same vertices as the

two query vertices

t: |edges| p: v1 and v2 are the names of the vertices r: true if the vertices are adjacent, false otherwise

Returns:

  • (Boolean) 


12
13
14
15
16
17
18
19
 
# File 'lib/abstract_graph/graph/is_adjacent.rb', line 12

def is_adjacent?( v1, v2 )
  vertices = [v1, v2].sort!

  # note find is overridden on uniqueNameCollection
  ( @edges.each.find do |e|
    vertices == e.vertices.map(&:name).sort
  end && true ) || false
end

#merge_vertices(*args) ⇒ Object

d: Merges vertices together so that any edges are connected to merged vertex a: First create a list of all edges within the vertices, they will be deleted.

Next create a list of edges to create which will be connected to the final
vertex. This is done by finding the remaining edges connected to the vertices.
Finally, delete the vertices, add the new vertex, and add the edges.

t: |vertices| * |edges| p: (Array, String)

array is the string names of vertices to merge together
string is the name of the final vertex
 (String, String, String)
first two strings are the vertices to merge together
last string is the name of the merged vertex

r: the graph itself *: the edges prioritize v1 to v2 if there are any conflicts



20
21
22
23
 
# File 'lib/abstract_graph/graph/merge_vertices.rb', line 20

def merge_vertices( *args )
  other = self.dup
  other.merge_vertices!( *args )
end

#merge_vertices!(*args) ⇒ Object

same as before except operates on the current graph



26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/abstract_graph/graph/merge_vertices.rb', line 26

def merge_vertices!( *args )
  # create a list of vertices we want to merge
  mergeV = []
  if args[0].class == Array
    mergeV = args[0]
  else
    mergeV << args[0] << args[1]
  end

  # first construct an array of edges in between vertices
  edgesInBetween = []
  if ( args.size == 3 )
    # do not need to go through the array of vertices
    edgesInBetween << get_edge_name( args[0], args[1] )
  else
    edgesInBetween = @edges.collect do |e|
      e.name if ( e.vertices.map do |v|
        v.name
      end & mergeV ).count == 2
    end
  end

  # delete the edges in between vertices
  edgesInBetween.each do |e|
    delete_edge!( e ) if e
  end

  # get the list of connections we want vmerged to be merged with
  finalConnections = {}
  mergeV.reverse.each do |vCheck|
    @edges.each do |e|
      [0,1].each do |edgeVId|

        # check if the edge contains our vertex
        if e.vertices[edgeVId].name == vCheck
          otherVertex = e.vertices[(edgeVId+1)%2].name
          # track the vertex with the edge name
          finalConnections[otherVertex] = e.name 
          delete_edge! e.name 
        end

      end
    end
  end

  # delete the vertices we want to merge
  mergeV.each do |v|
    delete_vertex! v
  end

  # add vmerged and connect it to adjacent vertices
  add_vertex args.last
  finalConnections.each do | vertexName, name |
    add_edge name, vertexName, args.last
  end

  self
end

#split_vertex(s) ⇒ Object

d: Split a vertex into two and assign adjacent to each of the vertices. a: Gathers a list of adjacent vertices by going through the edges, then

deletes the vertex and all the adjacent edges. Then goes back, creates
two vertices, and recreates all the adjacent edges.

t: |edges| p: name of vertex to split r: graph itself



13
14
15
16
17
 
# File 'lib/abstract_graph/graph/split_vertex.rb', line 13

def split_vertex( s )
  other = self.dup
  other.split_vertex!( s )
  other
end

#split_vertex!(s) ⇒ Object

same as before except operates on the current graph



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/abstract_graph/graph/split_vertex.rb', line 20

def split_vertex!( s )
  adjacentVertices = @edges.dup.keep_if do |e|
    e.vertices.collect(&:name).include? s
  end.collect do |e|
    [ e.name, ( e.vertices.collect(&:name) - [s] )[0] ]
  end

  delete_vertex! s
  adjacentVertices.each do |e|
    delete_edge! e[0]
  end

  add_vertex "#{s}-1"
  add_vertex "#{s}-2"
  adjacentVertices.each do |e|
    add_edge "#{e[0]}-1",  "#{s}-1", e[1]
    add_edge "#{e[0]}-2",  "#{s}-2", e[1]
  end

  self
end