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/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

public constructor



7
8
9
10
11
12
13
 
# File 'lib/abstract_graph/graph/initialize.rb', line 7

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

create a connected graph with two sets of vertices where

the two sets only have vertices adjacent to the other set

p: the number of vertices in the two sets. the first set has

n vertices from 2**(0..n-1) and the second set has m
vertices from 2**(n**m+n-1)



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

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

create a variabled sized complete graph

that is, a graph where every vertex is adjacent
to every other vertex

p: the number of vertices in the desired complete graph



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

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|
    result.add_edge( "e#{i[0]+i[1]}", "v#{i[0]}", "v#{i[1]}" )
  end
  result
end

.cycle_graph(n) ⇒ Object

create a variabled sized cycle graph,

ie, a connected graph such that every vertex has
exactly two distinct paths to every other vertex

p: the number of vertices in the cycle graph

coincidently, also the number of edges



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

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

create a variable sized path graph,

ie, a connected graph with 2 end vertices and n-2 connector
vertices. Each connector vertex has two adjacent vertices

p: the number of vertices in the path, n-1 edges



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

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

create a petersen graph. ie, a 3 regular graph with 10 vertices and 15 edges



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

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 |edgePair|
    result.add_edge "e#{vertexNames[edgePair[0]] + vertexNames[edgePair[1]]}", "v#{vertexNames[edgePair[0]]}", "v#{vertexNames[edgePair[1]]}"
  end

  result
end

Instance Method Details

#add_edge(s, v1, v2) ⇒ Object

add a vertex named s to the graph joining

the vertices named v1 and v2

p: String s represents name

Vertex name v1 and v2 are the two vertices

r: errors when v1, v2 doesn’t exist, loop, or multiple edge

Raises:

  • (Exception) 


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

def add_edge( s, v1, v2 )
  v1 = @vertices[v1] or return nil
  v2 = @vertices[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_value 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

add a vertex named s to the graph p: String s represents the name of the wanted vertex



8
9
10
11
12
13
 
# File 'lib/abstract_graph/graph/add_vertex.rb', line 8

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

#adjacency_list(s) ⇒ Object

return the adjacent vertices in of a vertex p: String s represents the name of the query vertex



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/abstract_graph/graph/adjacency_list.rb', line 8

def adjacency_list( s )
  # this collects all the edges at first
  result = @edges.collect do |id,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

changes an edge name to another valid name p: String s represents the current edge we want to rename

String snew is what we want to rename the edge to



9
10
11
12
 
# File 'lib/abstract_graph/graph/change_edge_name.rb', line 9

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

#change_vertex_name(s, snew) ⇒ Object

changes a vertex name to another valid name p: String s represents the current vertex we want to rename

String snew is what we want to rename the vertex to



9
10
11
12
 
# File 'lib/abstract_graph/graph/change_vertex_name.rb', line 9

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

#delete_edge(s) ⇒ Object

delete an edge in a replicated graph p: String s represents the name of the edge



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

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

#delete_edge!(s) ⇒ Object

delete an edge in a current graph p: String s represents the name of the edge



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

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

#delete_vertex(s) ⇒ Object

delete a vertex in a new graph p: String s represents the name of the vertex



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

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

#delete_vertex!(s) ⇒ Object

delete a vertex in a current graph p: String s represents the name of the vertex



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

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

#dup ⇒ Object

does a deep copy of the graph



7
8
9
10
11
12
13
14
15
16
17
18
 
# File 'lib/abstract_graph/graph/dup.rb', line 7

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

#get_edge_name(v1, v2) ⇒ Object

returns the edge connecting v1 and v2, if there is no

edge, then it returns nil

p: String v1, v2 represents the names of the vertices



9
10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/abstract_graph/graph/get_edge_name.rb', line 9

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

  @edges.each_value 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

returns whether there exists a edge with name string p: String s represents name of edge

Returns:

  • (Boolean) 


8
9
10
 
# File 'lib/abstract_graph/graph/has_edge.rb', line 8

def has_edge?( s )
  @edges.has_key? s || false
end

#has_vertex?(s) ⇒ Boolean

returns whether there exists a vertex with name string p: String s represents name of query vertex

Returns:

  • (Boolean) 


8
9
10
 
# File 'lib/abstract_graph/graph/has_vertex.rb', line 8

def has_vertex?( s )
  @vertices.has_key? s || false
end

#is_adjacent?(v1, v2) ⇒ Boolean

returns whether or not v1 and v2 are joined by an edge p: String v1, v2 represents the names of the vertices

Returns:

  • (Boolean) 


8
9
10
11
12
13
14
15
16
17
 
# File 'lib/abstract_graph/graph/is_adjacent.rb', line 8

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

  ( @edges.each_value.find do |e|
    vertices == e.vertices.map do |v|
      v.name
    end.sort
  end && true ) || false

end

#merge_vertices(*args) ⇒ Object

returns a replicated graph where the vertices with names

v1 and v2 merge together to a vertex named vmerged and
the edges that were adjacent to v1 and v2 are now
adjacent to vmerged

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

e: the edges prioritize v1 to v2 if there are any conflicts



17
18
19
20
 
# File 'lib/abstract_graph/graph/merge_vertices.rb', line 17

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



23
24
25
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
 
# File 'lib/abstract_graph/graph/merge_vertices.rb', line 23

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.values.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 |name, 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] = name
          delete_edge! 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

returns a replicated graph where all the vertices are the same but one

gets split and all it's adjacent vertices are now connected to two replaced vertices

p: String s the name of the vertex that will be split into vertexName-1 and vertexName-2

all adjacent edges will also be split and adjacent to the correct vertex



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

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



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

def split_vertex!( s )
  adjacentVertices = @edges.dup.keep_if do |id, e|
    e.vertices.collect(&:name).include? s
  end.collect do |id, e|
    [id, ( 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