module RGL::MutableGraph
A MutableGraph
can be changed via the addition or removal of edges and vertices.
Public Instance Methods
Source
# File lib/rgl/mutable.rb 29 def add_edge(u, v) 30 raise NotImplementedError 31 end
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.
Source
# File lib/rgl/mutable.rb 43 def add_edges(*edges) 44 edges.each { |edge| add_edge(edge[0], edge[1]) } 45 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 {Edge::DirectedEdge} or {Edge::UnDirectedEdge}.
Source
# File lib/rgl/mutable.rb 17 def add_vertex(v) 18 raise NotImplementedError 19 end
Add a new vertex v to the graph. If the vertex is already in the graph (tested via eql?), the method does nothing.
Source
# File lib/rgl/mutable.rb 35 def add_vertices(*a) 36 a.each { |v| add_vertex v } 37 end
Add all objects in a to the vertex set.
Source
# 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
@return [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.
Source
# File lib/rgl/mutable.rb 78 def cycles_with_vertex(vertex) 79 cycles_with_vertex_helper(vertex, vertex, []) 80 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. @return [Array]
Source
# 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
Initializes an RGL
graph from a subset of the GraphML format given in source
(see graphml.graphdrawing.org/).
Source
# File lib/rgl/mutable.rb 63 def remove_edge(u, v) 64 raise NotImplementedError 65 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.
Source
# File lib/rgl/mutable.rb 53 def remove_vertex(v) 54 raise NotImplementedError 55 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.
Source
# File lib/rgl/mutable.rb 70 def remove_vertices(*a) 71 a.each { |v| remove_vertex v } 72 end
Remove all vertices specified by the array a from the graph by calling {#remove_vertex}.
Protected Instance Methods
Source
# File lib/rgl/mutable.rb 84 def cycles_with_vertex_helper(vertex, start, visited) 85 adjacent_vertices(start).reject { |x| visited.include?(x) }.inject([]) do |acc, adj| 86 local_visited = Array.new(visited) << adj 87 acc << local_visited if (adj==vertex) 88 acc = acc + cycles_with_vertex_helper(vertex, adj, local_visited) 89 end 90 end