module RGL::Graph
In BGL terminology the module Graph
defines the graph concept (see Graph Concepts). We however do not distinguish between the IncidenceGraph, EdgeListGraph and VertexListGraph concepts, which would complicate the interface too much. These concepts are defined in BGL to differentiate between efficient access to edges and vertices.
The RGL
Graph
concept contains only a few requirements that are common to all the graph concepts. These include, especially, the iterators defining the sets of vertices and edges (see {#each_vertex} and {#each_adjacent}). Most other functions are derived from these fundamental iterators, i.e. {#each_edge}, {#num_vertices} or {#num_edges}.
Each graph is an enumerable of vertices.
Public Instance Methods
Returns true if the graph contains no cycles. This is only meaningful for directed graphs. Returns false for undirected graphs.
# File lib/rgl/topsort.rb 75 def acyclic? 76 topsort_iterator.length == num_vertices 77 end
@return [Array] of vertices adjacent to vertex v
. @param (see each_adjacent
)
# File lib/rgl/base.rb 230 def adjacent_vertices(v) 231 r = [] 232 each_adjacent(v) { |u| r << u } 233 r 234 end
Finds the shortest paths from the source to each vertex of the graph.
Returns a Hash that maps each vertex of the graph to an Array of vertices that represents the shortest path from the source to the vertex. If the path doesn’t exist, the corresponding hash value is nil. For the source vertex returned hash contains a trivial one-vertex path - [source].
Unlike Dijkstra algorithm, Bellman-Ford shortest paths algorithm works with negative edge weights.
Raises ArgumentError if an edge weight is undefined.
Raises ArgumentError or the graph has negative-weight cycles. This behavior can be overridden my a custom handler for visitor’s edge_not_minimized event. @return [Hash]
# File lib/rgl/bellman_ford.rb 109 def bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) 110 BellmanFordAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source) 111 end
@return [BFSIterator] starting at vertex v.
# File lib/rgl/traversal.rb 111 def bfs_iterator(v = self.detect { |x| true }) 112 BFSIterator.new(self, v) 113 end
This method uses the tree_edge_event
of BFSIterator
to record all tree edges of the search tree in the result.
@return [DirectedAdjacencyGraph] which represents a BFS search tree starting at v.
# File lib/rgl/traversal.rb 119 def bfs_search_tree_from(v) 120 unless defined?(DirectedAdjacencyGraph) 121 require 'rgl/adjacency' 122 end 123 bfs = bfs_iterator(v) 124 tree = DirectedAdjacencyGraph.new 125 126 bfs.set_tree_edge_event_handler do |from, to| 127 tree.add_edge(from, to) 128 end 129 130 bfs.set_to_end # does the search 131 tree 132 end
Returns true if the graph is bipartite. Otherwise returns false.
# File lib/rgl/bipartite.rb 38 def bipartite? 39 !bipartite_sets.nil? 40 end
Separates graph’s vertices into two disjoint sets so that every edge of the graph connects vertices from different sets. If it’s possible, the graph is bipartite.
Returns an array of two disjoint vertices sets (represented as arrays) if the graph is bipartite. Otherwise, returns nil. @return [Array]
# File lib/rgl/bipartite.rb 14 def bipartite_sets 15 raise NotUndirectedError.new('bipartite sets can only be found for an undirected graph') if directed? 16 17 bfs = BipartiteBFSIterator.new(self) 18 19 # if necessary, we start BFS from each vertex to make sure 20 # that all connected components of the graph are processed 21 each_vertex do |u| 22 next if bfs.finished_vertex?(u) 23 24 bfs.reset_start(u) 25 bfs.move_forward_until { bfs.found_odd_cycle } 26 27 return if bfs.found_odd_cycle 28 end 29 30 bfs.bipartite_sets_map.inject([[], []]) do |sets, (vertex, set)| 31 sets[set] << vertex 32 sets 33 end 34 end
Returns an {ImplicitGraph} where the strongly connected components of this graph are condensed into single nodes represented by Set instances containing the members of each strongly connected component. Edges between the different strongly connected components are preserved while edges within strongly connected components are omitted.
Raises {NotDirectedError} if run on an undirected graph. @return ImplicitGraph
# File lib/rgl/condensation.rb 17 def condensation_graph 18 raise NotDirectedError, 19 "condensation_graph only supported for directed graphs" unless directed? 20 21 # Get the component map for the strongly connected components. 22 comp_map = strongly_connected_components.comp_map 23 24 # Invert the map such that for any number, n, in the component map a Set 25 # instance is created containing all of the nodes which map to n. The Set 26 # instances will be used to map to the number, n, with which the elements 27 # of the set are associated. 28 inv_comp_map = {} 29 comp_map.each { |v, n| (inv_comp_map[n] ||= Set.new) << v } 30 31 # Create an ImplicitGraph where the nodes are the strongly connected 32 # components of this graph and the edges are the edges of this graph which 33 # cross between the strongly connected components. 34 ImplicitGraph.new do |g| 35 g.vertex_iterator do |b| 36 inv_comp_map.each_value(&b) 37 end 38 39 g.adjacent_iterator do |scc, b| 40 scc.each do |v| 41 each_adjacent(v) do |w| 42 # Do not make the cluster reference itself in the graph. 43 if comp_map[v] != comp_map[w] 44 b.call(inv_comp_map[comp_map[w]]) 45 end 46 end 47 end 48 end 49 50 g.directed = true 51 end 52 end
Do a recursive DFS search on the whole graph. If a block is passed, it is called on each finish_vertex
event. See {Graph#strongly_connected_components} for an example usage.
Note that this traversal does not garantee, that roots are at the top of each spanning subtree induced by the DFS search on a directed graph (see also the discussion in issue #20). @see DFSVisitor
# File lib/rgl/traversal.rb 183 def depth_first_search(vis = DFSVisitor.new(self), &b) 184 each_vertex do |u| 185 unless vis.finished_vertex?(u) 186 vis.handle_start_vertex(u) 187 depth_first_visit(u, vis, &b) 188 end 189 end 190 end
Start a depth first search at vertex u. The block b is called on each finish_vertex
event. @see DFSVisitor
# File lib/rgl/traversal.rb 195 def depth_first_visit(u, vis = DFSVisitor.new(self), &b) 196 vis.color_map[u] = :GRAY 197 vis.handle_examine_vertex(u) 198 199 each_adjacent(u) do |v| 200 vis.handle_examine_edge(u, v) 201 202 if vis.follow_edge?(u, v) # (u,v) is a tree edge 203 vis.handle_tree_edge(u, v) # also discovers v 204 # color of v was :WHITE. Will be marked :GRAY in recursion 205 depth_first_visit(v, vis, &b) 206 else # (u,v) is a non tree edge 207 if vis.color_map[v] == :GRAY 208 vis.handle_back_edge(u, v) # (u,v) has gray target 209 else 210 vis.handle_forward_edge(u, v) # (u,v) is a cross or forward edge 211 end 212 end 213 end 214 215 vis.color_map[u] = :BLACK 216 vis.handle_finish_vertex(u) # finish vertex 217 b.call(u) 218 end
@return [DFSIterator] staring at vertex v.
# File lib/rgl/traversal.rb 171 def dfs_iterator(v = self.detect { |x| true }) 172 DFSIterator.new(self, v) 173 end
Finds the shortest path from the source to the target in the graph.
If the path exists, returns it as an Array of vertices. Otherwise, returns nil.
Raises ArgumentError if edge weight is negative or undefined.
# File lib/rgl/dijkstra.rb 116 def dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) 117 DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_path(source, target) 118 end
Finds the shortest paths from the source to each vertex of the graph.
Returns a Hash that maps each vertex of the graph to an Array of vertices that represents the shortest path from the source to the vertex. If the path doesn’t exist, the corresponding hash value is nil. For the source vertex returned hash contains a trivial one-vertex path - [source].
Raises ArgumentError if edge weight is negative or undefined.
# File lib/rgl/dijkstra.rb 128 def dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) 129 DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source) 130 end
Is the graph directed? The default returns false.
# File lib/rgl/base.rb 180 def directed? 181 false 182 end
Call dotty for the graph which is written to the file ‘graph.dot’ in the current directory.
# File lib/rgl/dot.rb 103 def dotty(params = {}) 104 dotfile = "graph.dot" 105 File.open(dotfile, "w") do |f| 106 print_dotted_on(params, f) 107 end 108 unless system("dotty", dotfile) 109 raise "Error executing dotty. Did you install GraphViz?" 110 end 111 end
Vertices get enumerated. A graph is thus an enumerable of vertices.
# File lib/rgl/base.rb 175 def each(&block) 176 each_vertex(&block) 177 end
The each_adjacent
iterator defines the out edges of vertex v
. This method must be defined by concrete graph classes. Its defines the BGL IncidenceGraph concept. @param v a vertex of the graph
# File lib/rgl/base.rb 152 def each_adjacent(v, &block) # :yields: v 153 raise NotImplementedError 154 end
Compute the connected components of an undirected graph, using a DFS (Depth-first search)-based approach. A _connected component_ of an undirected graph is a set of vertices that are all reachable from each other.
The function is implemented as an iterator which calls the client with an array of vertices for each component.
It raises an exception if the graph is directed.
# File lib/rgl/connected_components.rb 23 def each_connected_component 24 raise NotUndirectedError, 25 "each_connected_component only works " + 26 "for undirected graphs." if directed? 27 28 comp = [] 29 vis = DFSVisitor.new(self) 30 vis.set_finish_vertex_event_handler { |v| comp << v } 31 32 vis.set_start_vertex_event_handler do |v| 33 yield comp unless comp.empty? 34 comp = [] 35 end 36 37 depth_first_search(vis) { |v| } 38 yield comp unless comp.empty? 39 end
The each_edge
iterator should provide efficient access to all edges of the graph. Its defines the BGL EdgeListGraph concept.
This method must not be defined by concrete graph classes, because it can be implemented using {#each_vertex} and {#each_adjacent}. However for undirected graphs the function is inefficient because we must not yield (v,u) if we already visited edge (u,v).
# File lib/rgl/base.rb 163 def each_edge(&block) 164 if directed? 165 each_vertex do |u| 166 each_adjacent(u) { |v| yield u, v } 167 end 168 else 169 each_edge_aux(&block) # concrete graphs should to this better 170 end 171 end
The each_vertex
iterator defines the set of vertices of the graph. This method must be defined by concrete graph classes. It defines the BGL VertexListGraph concept.
# File lib/rgl/base.rb 143 def each_vertex(&block) # :yields: v 144 raise NotImplementedError 145 end
@return [Class] the class for edges: {Edge::DirectedEdge} or {Edge::UnDirectedEdge}.
# File lib/rgl/base.rb 215 def edge_class 216 directed? ? DirectedEdge : UnDirectedEdge 217 end
@return [Array] of edges (DirectedEdge or UnDirectedEdge) of the graph It uses {#each_edge} to compute the edges
# File lib/rgl/base.rb 221 def edges 222 result = [] 223 c = edge_class 224 each_edge { |u, v| result << c.new(u, v) } 225 result 226 end
Returns a new {ImplicitGraph} which has as edges all edges of the receiver which satisfy the predicate filter (a block with two parameters).
@example
g = complete(7).edges_filtered_by { |u,v| u+v == 7 } g.to_s => "(1=6)(2=5)(3=4)" g.vertices => [1, 2, 3, 4, 5, 6, 7]
@return [ImplicitGraph]
# File lib/rgl/implicit.rb 146 def edges_filtered_by(&filter) 147 implicit_graph do |g| 148 g.adjacent_iterator do |v, b| 149 self.each_adjacent(v) do |u| 150 b.call(u) if filter.call(v, u) 151 end 152 end 153 154 g.edge_iterator do |b| 155 self.each_edge { |u, v| b.call(u, v) if filter.call(u, v) } 156 end 157 end 158 end
Returns true if the graph has no vertices, i.e. num_vertices
== 0.
# File lib/rgl/base.rb 203 def empty? 204 num_vertices.zero? 205 end
Two graphs are equal iff they have equal directed? property as well as vertices and edges sets. @param [Graph] other
# File lib/rgl/base.rb 271 def eql?(other) 272 equal?(other) || eql_graph?(other) 273 end
Returns true if +(u, v)+ is an edge of the graph. @param (see each_edge
)
# File lib/rgl/base.rb 194 def has_edge?(u, v) 195 each_adjacent(u) do |w| 196 return true if v == w 197 end 198 return false 199 end
Returns true if v
is a vertex of the graph. Same as include? inherited from Enumerable. Complexity is O(num_vertices
) by default. Concrete graph may be better here (see AdjacencyGraph
). @param (see each_adjacent
)
# File lib/rgl/base.rb 188 def has_vertex?(v) 189 include?(v) # inherited from enumerable 190 end
Return a new {ImplicitGraph} which is isomorphic (i.e. has same edges and vertices) to the receiver. It is a shortcut, also used by {#edges_filtered_by} and {#vertices_filtered_by}. @return [ImplicitGraph]
# File lib/rgl/implicit.rb 164 def implicit_graph 165 result = ImplicitGraph.new do |g| 166 g.vertex_iterator { |b| self.each_vertex(&b) } 167 g.adjacent_iterator { |v, b| self.each_adjacent(v, &b) } 168 g.directed = self.directed? 169 end 170 171 yield result if block_given? # let client overwrite defaults 172 result 173 end
Finds the maximum flow from the source to the sink in the graph.
Returns flows map as a hash that maps each edge of the graph to a flow through that edge that is required to reach the maximum total flow.
For the method to work, the graph should be first altered so that for each directed edge (u, v) it contains reverse edge (u, v). Capacities of the primary edges should be non-negative, while reverse edges should have zero capacity.
Raises ArgumentError if the graph is not directed.
Raises ArgumentError if a reverse edge is missing, edge capacity is missing, an edge has negative capacity, or a reverse edge has positive capacity.
@return [Hash]
# File lib/rgl/edmonds_karp.rb 136 def maximum_flow(edge_capacities_map, source, sink) 137 EdmondsKarpAlgorithm.new(self, edge_capacities_map).maximum_flow(source, sink) 138 end
@return [int] the number of edges
# File lib/rgl/base.rb 256 def num_edges 257 r = 0 258 each_edge { |u, v| r +=1 } 259 r 260 end
Returns the number of out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v
. @return [int] @param (see each_adjacent
)
# File lib/rgl/base.rb 240 def out_degree(v) 241 r = 0 242 each_adjacent(v) { |u| r += 1 } 243 r 244 end
Checks whether a path exists between source and target vertices in the graph.
# File lib/rgl/path.rb 10 def path?(source, target) 11 return false unless has_vertex?(source) 12 13 bfs_iterator = bfs_iterator(source) 14 bfs_iterator.include?(target) 15 end
Finds the minimum spanning tree of the graph.
Returns an {AdjacencyGraph} that represents the minimum spanning tree of the graph’s connectivity component that contains the starting vertex. The algorithm starts from an arbitrary vertex if the start_vertex is not given. Since the implementation relies on the Dijkstra’s algorithm, Prim’s algorithm uses the same visitor class and emits the same events.
Raises ArgumentError if edge weight is undefined.
# File lib/rgl/prim.rb 49 def prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) 50 PrimAlgorithm.new(self, edge_weights_map, visitor).minimum_spanning_tree(start_vertex) 51 end
Output the DOT-graph to stream s.
# File lib/rgl/dot.rb 96 def print_dotted_on(params = {}, s = $stdout) 97 s << to_dot_graph(params).to_s << "\n" 98 end
Return a new DirectedAdjacencyGraph
which has the same set of vertices. If (u,v) is an edge of the graph, then (v,u) is an edge of the result.
If the graph is undirected, the result is self. @return [DirectedAdjacencyGraph]
# File lib/rgl/adjacency.rb 182 def reverse 183 return self unless directed? 184 result = DirectedAdjacencyGraph.new 185 each_vertex { |v| result.add_vertex v } 186 each_edge { |u, v| result.add_edge(v, u) } 187 result 188 end
Set the configuration values for the given edge
# File lib/rgl/dot.rb 34 def set_edge_options(u, v, **options) 35 edge = edge_class.new(u, v) 36 @edge_options ||= {} 37 @edge_options[edge] ||= {} 38 39 RGL::DOT::EDGE_OPTS.each do |opt| 40 @edge_options[edge][:"#{opt}"] = options[:"#{opt}"] if options.key?(:"#{opt}") 41 end 42 end
Set the configuration values for the given vertex
# File lib/rgl/dot.rb 24 def set_vertex_options(vertex, **options) 25 @vertex_options ||= {} 26 @vertex_options[vertex] ||= {} 27 28 RGL::DOT::NODE_OPTS.each do |opt| 29 @vertex_options[vertex][:"#{opt}"] = options[:"#{opt}"] if options.key?(:"#{opt}") 30 end 31 end
@return [int] the number of vertices
# File lib/rgl/base.rb 248 def size # Why not in Enumerable? 249 inject(0) { |n, v| n + 1 } 250 end
This is Tarjan’s algorithm for strongly connected components, from his paper “Depth first search and linear graph algorithms”. It calculates the components in a single application of DFS. We implement the algorithm with the help of the {DFSVisitor} {TarjanSccVisitor}.
Definition¶ ↑
A _strongly connected component_ of a directed graph G=(V,E) is a maximal set of vertices U which is in V, such that for every pair of vertices u and v in U, we have both a path from u to v and a path from v to u. That is to say, u and v are reachable from each other.
@Article!{Tarjan:1972:DFS,
author = "R. E. Tarjan", key = "Tarjan", title = "Depth First Search and Linear Graph Algorithms", journal = "SIAM Journal on Computing", volume = "1", number = "2", pages = "146--160", month = jun, year = "1972", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 09:56:44 1997", bibsource = "Parallel/Multi.bib, Misc/Reverse.eng.bib",
}
The output of the algorithm is recorded in a {TarjanSccVisitor} vis. vis.comp_map
will contain numbers giving the component ID assigned to each vertex. The number of components is vis.num_comp
. @return [TarjanSccVisitor]
# File lib/rgl/connected_components.rb 135 def strongly_connected_components 136 raise NotDirectedError, 137 "strong_components only works for directed graphs." unless directed? 138 139 vis = TarjanSccVisitor.new(self) 140 depth_first_search(vis) { |v| } 141 vis 142 end
Convert a general graph to an AdjacencyGraph
. If the graph is directed, returns a {DirectedAdjacencyGraph}; otherwise, returns an {AdjacencyGraph}. @return {DirectedAdjacencyGraph} or {AdjacencyGraph}
# File lib/rgl/adjacency.rb 170 def to_adjacency 171 result = (directed? ? DirectedAdjacencyGraph : AdjacencyGraph).new 172 each_vertex { |v| result.add_vertex(v) } 173 each_edge { |u, v| result.add_edge(u, v) } 174 result 175 end
Return a {DOT::Digraph} for directed graphs or a {DOT::Graph} for an undirected {Graph}. params can contain any graph property specified in rdot.rb.
# File lib/rgl/dot.rb 48 def to_dot_graph(params = {}) 49 params['name'] ||= self.class.name.gsub(/:/, '_') 50 fontsize = params['fontsize'] ? params['fontsize'] : '8' 51 graph = (directed? ? DOT::Digraph : DOT::Graph).new(params) 52 edge_class = directed? ? DOT::DirectedEdge : DOT::Edge 53 54 each_vertex do |v| 55 default_vertex_options = { 56 'name' => vertex_id(v), 57 'fontsize' => fontsize, 58 'label' => vertex_label(v) 59 } 60 each_vertex_options = default_vertex_options 61 62 if @vertex_options && @vertex_options[v] 63 RGL::DOT::NODE_OPTS.each do |opt| 64 if @vertex_options[v].key?(:"#{opt}") 65 each_vertex_options["#{opt}"] = @vertex_options[v].fetch(:"#{opt}") 66 end 67 end 68 end 69 graph << DOT::Node.new(each_vertex_options) 70 end 71 72 edges.each do |edge| 73 default_edge_options = { 74 'from' => edge.source, 75 'to' => edge.target, 76 'fontsize' => fontsize 77 } 78 79 each_edge_options = default_edge_options 80 81 if @edge_options && @edge_options[edge] 82 RGL::DOT::EDGE_OPTS.each do |opt| 83 if @edge_options[edge].key?(:"#{opt}") 84 each_edge_options["#{opt}"] = @edge_options[edge].fetch(:"#{opt}") 85 end 86 end 87 end 88 graph << edge_class.new(each_edge_options) 89 end 90 91 graph 92 end
Utility method to show a string representation of the edges of the graph. @return [String]
# File lib/rgl/base.rb 264 def to_s 265 edges.collect {|e| e.to_s}.sort.join 266 end
Return a new {AdjacencyGraph} which has the same set of vertices. If (u,v) is an edge of the graph, then (u,v) and (v,u) (which are the same edges) are edges of the result.
If the graph is undirected, the result is self
. @return [AdjacencyGraph]
# File lib/rgl/adjacency.rb 196 def to_undirected 197 return self unless directed? 198 AdjacencyGraph.new(Set, self) 199 end
@return [TopsortIterator] for the graph.
# File lib/rgl/topsort.rb 68 def topsort_iterator 69 TopsortIterator.new(self) 70 end
Returns an {DirectedAdjacencyGraph} which is the transitive closure of this graph. Meaning, for each path u -> … -> v in this graph, the path is copied and the edge u -> v is added. This method supports working with cyclic graphs by ensuring that edges are created between every pair of vertices in the cycle, including self-referencing edges.
This method should run in O(|V||E|) time, where |V| and |E| are the number of vertices and edges respectively.
Raises {NotDirectedError} if run on an undirected graph. @return DirectedAdjacencyGraph
# File lib/rgl/transitivity.rb 20 def transitive_closure 21 raise NotDirectedError, 22 "transitive_closure only supported for directed graphs" unless directed? 23 24 # Compute a condensation graph in order to hide cycles. 25 cg = condensation_graph 26 27 # Use a depth first search to calculate the transitive closure over the 28 # condensation graph. This ensures that as we traverse up the graph we 29 # know the transitive closure of each subgraph rooted at each node 30 # starting at the leaves. Subsequent root nodes which consume these 31 # subgraphs by way of the nodes' immediate successors can then immediately 32 # add edges to the roots of the subgraphs and to every successor of those 33 # roots. 34 tc_cg = DirectedAdjacencyGraph.new 35 cg.depth_first_search do |v| 36 # For each vertex v, w, and x where the edges v -> w and w -> x exist in 37 # the source graph, add edges v -> w and v -> x to the target graph. 38 cg.each_adjacent(v) do |w| 39 tc_cg.add_edge(v, w) 40 tc_cg.each_adjacent(w) do |x| 41 tc_cg.add_edge(v, x) 42 end 43 end 44 # Ensure that a vertex with no in or out edges is added to the graph. 45 tc_cg.add_vertex(v) 46 end 47 48 # Expand the condensed transitive closure. 49 # 50 # For each trivial strongly connected component in the condensed graph, 51 # add the single node it contains to the new graph and add edges for each 52 # edge the node begins in the original graph. 53 # For each NON-trivial strongly connected component in the condensed 54 # graph, add each node it contains to the new graph and add edges to 55 # every node in the strongly connected component, including self 56 # referential edges. Then for each edge of the original graph from any 57 # of the contained nodes, add edges from each of the contained nodes to 58 # all the edge targets. 59 g = DirectedAdjacencyGraph.new 60 tc_cg.each_vertex do |scc| 61 scc.each do |v| 62 # Add edges between all members of non-trivial strongly connected 63 # components (size > 1) and ensure that self referential edges are 64 # added when necessary for trivial strongly connected components. 65 if scc.size > 1 || has_edge?(v, v) 66 scc.each do |w| 67 g.add_edge(v, w) 68 end 69 end 70 # Ensure that a vertex with no in or out edges is added to the graph. 71 g.add_vertex(v) 72 end 73 # Add an edge from every member of a strongly connected component to 74 # every member of each strongly connected component to which the former 75 # points. 76 tc_cg.each_adjacent(scc) do |scc2| 77 scc.each do |v| 78 scc2.each do |w| 79 g.add_edge(v, w) 80 end 81 end 82 end 83 end 84 85 # Finally, the transitive closure... 86 g 87 end
Returns an {DirectedAdjacencyGraph} which is the transitive reduction of this graph. Meaning, that each edge u -> v is omitted if path u -> … -> v exists. This method supports working with cyclic graphs; however, cycles are arbitrarily simplified which may lead to variant, although equally valid, results on equivalent graphs.
This method should run in O(|V||E|) time, where |V| and |E| are the number of vertices and edges respectively.
Raises {NotDirectedError} if run on an undirected graph. @return DirectedAdjacencyGraph
# File lib/rgl/transitivity.rb 100 def transitive_reduction 101 raise NotDirectedError, 102 "transitive_reduction only supported for directed graphs" unless directed? 103 104 # Compute a condensation graph in order to hide cycles. 105 cg = condensation_graph 106 107 # Use a depth first search to compute the transitive reduction over the 108 # condensed graph. This is similar to the computation of the transitive 109 # closure over the graph in that for any node of the graph all nodes 110 # reachable from the node are tracked. Using a depth first search ensures 111 # that all nodes reachable from a target node are known when considering 112 # whether or not to add an edge pointing to that target. 113 tr_cg = DirectedAdjacencyGraph.new 114 paths_from = {} 115 cg.depth_first_search do |v| 116 paths_from[v] = Set.new 117 cg.each_adjacent(v) do |w| 118 # Only add the edge v -> w if there is no other edge v -> x such that 119 # w is reachable from x. Make sure to completely skip the case where 120 # x == w. 121 unless cg.to_enum(:each_adjacent, v).any? { |x| x != w && paths_from[x].include?(w) } 122 tr_cg.add_edge(v, w) 123 124 # For each vertex v, track all nodes reachable from v by adding node 125 # w to the list as well as all the nodes readable from w. 126 paths_from[v] << w 127 paths_from[v].merge(paths_from[w]) 128 end 129 end 130 # Ensure that a vertex with no in or out edges is added to the graph. 131 tr_cg.add_vertex(v) 132 end 133 134 # Expand the condensed transitive reduction. 135 # 136 # For each trivial strongly connected component in the condensed graph, 137 # add the single node it contains to the new graph and add edges for each 138 # edge the node begins in the original graph. 139 # For each NON-trivial strongly connected component in the condensed 140 # graph, add each node it contains to the new graph and add arbitrary 141 # edges between the nodes to form a simple cycle. Then for each strongly 142 # connected component adjacent to the current one, find and add the first 143 # edge which exists in the original graph, starts in the first strongly 144 # connected component, and ends in the second strongly connected 145 # component. 146 g = DirectedAdjacencyGraph.new 147 tr_cg.each_vertex do |scc| 148 # Make a cycle of the contents of non-trivial strongly connected 149 # components. 150 scc_arr = scc.to_a 151 if scc.size > 1 || has_edge?(scc_arr.first, scc_arr.first) 152 0.upto(scc_arr.size - 2) do |idx| 153 g.add_edge(scc_arr[idx], scc_arr[idx + 1]) 154 end 155 g.add_edge(scc_arr.last, scc_arr.first) 156 end 157 158 # Choose a single edge between the members of two different strongly 159 # connected component to add to the graph. 160 edges = self.to_enum(:each_edge) 161 tr_cg.each_adjacent(scc) do |scc2| 162 g.add_edge( 163 *edges.find do |v, w| 164 scc.member?(v) && scc2.member?(w) 165 end 166 ) 167 end 168 169 # Ensure that a vertex with no in or out edges is added to the graph. 170 scc.each do |v| 171 g.add_vertex(v) 172 end 173 end 174 175 # Finally, the transitive reduction... 176 g 177 end
# File lib/rgl/dot.rb 19 def vertex_id(v) 20 v 21 end
Returns a label for vertex v. Default is v.to_s
# File lib/rgl/dot.rb 15 def vertex_label(v) 16 v.to_s 17 end
Synonym for to_a inherited by Enumerable. @return [Array] of vertices
# File lib/rgl/base.rb 209 def vertices 210 to_a 211 end
Returns a new {ImplicitGraph} which has as vertices all vertices of the receiver which satisfy the predicate filter.
The methods provides similar functionality as {www.boost.org/doc/libs/1_36_0/libs/graph/doc/filtered_graph.html BGLs Filtered Graph}
@example
def complete (n) set = n.integer? ? (1..n) : n RGL::ImplicitGraph.new do |g| g.vertex_iterator { |b| set.each(&b) } g.adjacent_iterator do |x, b| set.each { |y| b.call(y) unless x == y } end end end complete(4).to_s # => "(1=2)(1=3)(1=4)(2=3)(2=4)(3=4)" complete(4).vertices_filtered_by { |v| v != 4 }.to_s # => "(1=2)(1=3)(2=3)"
@return [ImplicitGraph]
# File lib/rgl/implicit.rb 125 def vertices_filtered_by(&filter) 126 implicit_graph do |g| 127 g.vertex_iterator do |b| 128 self.each_vertex { |v| b.call(v) if filter.call(v) } 129 end 130 131 g.adjacent_iterator do |v, b| 132 self.each_adjacent(v) { |u| b.call(u) if filter.call(u) } 133 end 134 end 135 end
Use dot to create a graphical representation of the graph. Returns the filename of the graphics file.
# File lib/rgl/dot.rb 116 def write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {}) 117 src = dotfile + ".dot" 118 dot = dotfile + "." + fmt 119 120 File.open(src, 'w') do |f| 121 f << self.to_dot_graph(options).to_s << "\n" 122 end 123 124 unless system("dot -T#{fmt} #{src} -o #{dot}") 125 raise "Error executing dot. Did you install GraphViz?" 126 end 127 dot 128 end
Private Instance Methods
# File lib/rgl/base.rb 311 def each_edge_aux 312 # needed in each_edge 313 visited = Hash.new 314 315 each_vertex do |u| 316 each_adjacent(u) do |v| 317 edge = UnDirectedEdge.new(u, v) 318 319 unless visited.has_key?(edge) 320 visited[edge] = true 321 yield u, v 322 end 323 end 324 end 325 end
# File lib/rgl/base.rb 297 def eql_edges_set?(other) 298 other_num_edges = 0 299 300 other.each_edge do |u, v| 301 if has_edge?(u, v) 302 other_num_edges += 1 303 else 304 return false 305 end 306 end 307 308 other_num_edges == num_edges 309 end
# File lib/rgl/base.rb 279 def eql_graph?(other) 280 other.is_a?(Graph) && directed? == other.directed? && eql_vertices_set?(other) && eql_edges_set?(other) 281 end
# File lib/rgl/base.rb 283 def eql_vertices_set?(other) 284 other_num_vertices = 0 285 286 other.each_vertex do |v| 287 if has_vertex?(v) 288 other_num_vertices += 1 289 else 290 return false 291 end 292 end 293 294 other_num_vertices == num_vertices 295 end