module RGL::MutableGraph
A MutableGraph
can be changed via the addition or removal of edges and vertices.
Public Instance Methods
Inserts the edge (u,v) into the graph.
Note that for undirected graphs, (u,v) is the same edge as (v,u), so after a call to the function add_edge
(), this implies that edge (u,v) will appear in the out-edges of u and (u,v) (or equivalently (v,u)) will appear in the out-edges of v. Put another way, v will be adjacent to u and u will be adjacent to v.
# File lib/rgl/mutable.rb 29 def add_edge(u, v) 30 raise NotImplementedError 31 end
Add all edges in the edges array to the edge set. Elements of the array can be both two-element arrays or instances of DirectedEdge or UnDirectedEdge.
# File lib/rgl/mutable.rb 43 def add_edges(*edges) 44 edges.each { |edge| add_edge(edge[0], edge[1]) } 45 end
Add a new vertex v to the graph. If the vertex is already in the graph (tested via eql?), the method does nothing.
# File lib/rgl/mutable.rb 17 def add_vertex(v) 18 raise NotImplementedError 19 end
Add all objects in a to the vertex set.
# File lib/rgl/mutable.rb 35 def add_vertices(*a) 36 a.each { |v| add_vertex v } 37 end
Returns an array of all minimum cycles in a graph
This is not an efficient implementation O(n^4) and could be done using Minimum Spanning Trees. Hint. Hint.
# File lib/rgl/mutable.rb 99 def cycles 100 g = self.clone 101 self.inject([]) do |acc, v| 102 acc = acc.concat(g.cycles_with_vertex(v)) 103 g.remove_vertex(v); acc 104 end 105 end
Returns all minimum cycles that pass through a give vertex. The format is an Array of cycles, with each cycle being an Array of vertices in the cycle.
# File lib/rgl/mutable.rb 78 def cycles_with_vertex(vertex) 79 cycles_with_vertex_helper(vertex, vertex, []) 80 end
Initializes an RGL
graph from a subset of the GraphML format given in source
(see graphml.graphdrawing.org/).
# File lib/rgl/graphxml.rb 53 def from_graphxml(source) 54 listener = MutableGraphParser.new(self) 55 REXML::Document.parse_stream(source, listener) 56 self 57 end
Remove the edge (u,v) from the graph. If the graph allows parallel edges, this removes all occurrences of (u,v).
Precondition: u and v are vertices in the graph. Postcondition: (u,v) is no longer in the edge set for g.
# File lib/rgl/mutable.rb 63 def remove_edge(u, v) 64 raise NotImplementedError 65 end
Remove u from the vertex set of the graph. All edges whose target is v are also removed from the edge set of the graph.
Postcondition: num_vertices is one less, v no longer appears in the vertex set of the graph, and there no edge with source or target v.
# File lib/rgl/mutable.rb 53 def remove_vertex(v) 54 raise NotImplementedError 55 end
Remove all vertices specified by the array a from the graph by calling remove_vertex.
# File lib/rgl/mutable.rb 70 def remove_vertices(*a) 71 a.each { |v| remove_vertex v } 72 end