class AbstractGraph::Graph

public Graph class

Attributes

edges[RW]
vertices[RW]

Public Class Methods

complete_bipartite_graph(n, m) click to toggle source

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

# 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) click to toggle source

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

# 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) click to toggle source

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

# 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
new() click to toggle source

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

# File lib/abstract_graph/graph/initialize.rb, line 11
def initialize

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

end
path_graph(n) click to toggle source

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

# 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() click to toggle source

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

# 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

Public Instance Methods

add_edge( s, v1, v2 ) click to toggle source

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

# 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 ) click to toggle source

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

# 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 ) click to toggle source

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

# 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 ) click to toggle source

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

# 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 ) click to toggle source

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

# 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?() click to toggle source

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

# 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 ) click to toggle source

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

# 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 ) click to toggle source
# File lib/abstract_graph/graph/delete_edge.rb, line 16
def delete_edge!( s )
  @edges.delete s
  self
end
delete_vertex( s ) click to toggle source

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

# 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 ) click to toggle source
# File lib/abstract_graph/graph/delete_vertex.rb, line 16
def delete_vertex!( s )
  @vertices.delete s
  self
end
dup() click to toggle source

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

# 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 ) click to toggle source

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

# 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 ) click to toggle source

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

# File lib/abstract_graph/graph/has_edge.rb, line 11
def has_edge?( s )
  !(@edges.find s).nil?
end
has_vertex?( s ) click to toggle source

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

# File lib/abstract_graph/graph/has_vertex.rb, line 11
def has_vertex?( s )
  !(@vertices.find s).nil?
end
is_adjacent?( v1, v2 ) click to toggle source

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

# 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 ) click to toggle source

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

# 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 ) click to toggle source

same as before except operates on the current graph

# 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 ) click to toggle source

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

# 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 ) click to toggle source

same as before except operates on the current graph

# 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