class AbstractGraph::Graph
public Graph
class
Attributes
Public Class Methods
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
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
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
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
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
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
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
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
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
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
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
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
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
# File lib/abstract_graph/graph/delete_edge.rb, line 16 def delete_edge!( s ) @edges.delete s self end
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
# File lib/abstract_graph/graph/delete_vertex.rb, line 16 def delete_vertex!( s ) @vertices.delete s self end
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
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
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
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
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
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
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
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
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