Module: RGL::Graph
 Includes:
 Enumerable, Edge
 Included in:
 BidirectionalGraph, ImplicitGraph, MutableGraph
 Defined in:
 lib/rgl/base.rb,
lib/rgl/dot.rb,
lib/rgl/path.rb,
lib/rgl/prim.rb,
lib/rgl/topsort.rb,
lib/rgl/dijkstra.rb,
lib/rgl/implicit.rb,
lib/rgl/adjacency.rb,
lib/rgl/bipartite.rb,
lib/rgl/traversal.rb,
lib/rgl/traversal.rb,
lib/rgl/bellman_ford.rb,
lib/rgl/condensation.rb,
lib/rgl/edmonds_karp.rb,
lib/rgl/transitivity.rb,
lib/rgl/connected_components.rb
Overview
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.
Defined Under Namespace
Classes: TarjanSccVisitor
Instance Method Summary collapse

#acyclic? ⇒ Boolean
Returns true if the graph contains no cycles.

#adjacent_vertices(v) ⇒ Array
Of vertices adjacent to vertex
v
. 
#bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) ⇒ Hash[Object,Array]
Finds the shortest paths from the source to each vertex of the graph.

#bfs_iterator(v = self.detect { x true }) ⇒ BFSIterator
Starting at vertex v.

#bfs_search_tree_from(v) ⇒ DirectedAdjacencyGraph
This method uses the
tree_edge_event
of BFSIterator to record all tree edges of the search tree in the result. 
#bipartite? ⇒ Boolean
Returns true if the graph is bipartite.

#bipartite_sets ⇒ Array
Separates graph’s vertices into two disjoint sets so that every edge of the graph connects vertices from different sets.

#condensation_graph ⇒ Object
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.

#depth_first_search(vis = DFSVisitor.new(self), &b) ⇒ Object
Do a recursive DFS search on the whole graph.

#depth_first_visit(u, vis = DFSVisitor.new(self), &b) ⇒ Object
Start a depth first search at vertex u.

#dfs_iterator(v = self.detect { x true }) ⇒ DFSIterator
Staring at vertex v.

#dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) ⇒ Object
Finds the shortest path from the source to the target in the graph.

#dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) ⇒ Object
Finds the shortest paths from the source to each vertex of the graph.

#directed? ⇒ Boolean
Is the graph directed? The default returns false.

#dotty(params = {}) ⇒ Object
Call dotty for the graph which is written to the file ‘graph.dot’ in the current directory.

#each(&block) ⇒ Object
Vertices get enumerated.

#each_adjacent(v, &block) ⇒ Object
The
each_adjacent
iterator defines the out edges of vertexv
. 
#each_connected_component {comp ... } ⇒ Object
Compute the connected components of an undirected graph, using a DFS (Depthfirst search)based approach.

#each_edge(&block) ⇒ Object
The
each_edge
iterator should provide efficient access to all edges of the graph. 
#each_vertex(&block) ⇒ Object
The
each_vertex
iterator defines the set of vertices of the graph. 
#edge_class ⇒ Class
The class for edges: Edge::DirectedEdge or Edge::UnDirectedEdge.

#edges ⇒ Array
It uses #each_edge to compute the edges.

#edges_filtered_by(&filter) ⇒ ImplicitGraph
Returns a new ImplicitGraph which has as edges all edges of the receiver which satisfy the predicate filter (a block with two parameters).

#empty? ⇒ Boolean
Returns true if the graph has no vertices, i.e.

#eql?(other) ⇒ Boolean
(also: #==)
Two graphs are equal iff they have equal directed? property as well as vertices and edges sets.

#has_edge?(u, v) ⇒ Boolean
Returns true if (u, v) is an edge of the graph.

#has_vertex?(v) ⇒ Boolean
Returns true if
v
is a vertex of the graph. 
#implicit_graph {result ... } ⇒ ImplicitGraph
Return a new ImplicitGraph which is isomorphic (i.e. has same edges and vertices) to the receiver.

#maximum_flow(edge_capacities_map, source, sink) ⇒ Hash
Finds the maximum flow from the source to the sink in the graph.

#num_edges ⇒ int
The number of edges.

#out_degree(v) ⇒ int
Returns the number of outedges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex
v
. 
#path?(source, target) ⇒ Boolean
Checks whether a path exists between source and target vertices in the graph.

#prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) ⇒ Object
Finds the minimum spanning tree of the graph.

#print_dotted_on(params = {}, s = $stdout) ⇒ Object
Output the DOTgraph to stream s.

#reverse ⇒ DirectedAdjacencyGraph
Return a new DirectedAdjacencyGraph which has the same set of vertices.

#set_edge_options(u, v, **options) ⇒ Object
Set the configuration values for the given edge.

#set_vertex_options(vertex, **options) ⇒ Object
Set the configuration values for the given vertex.

#size ⇒ int
(also: #num_vertices)
The number of vertices.

#strongly_connected_components ⇒ TarjanSccVisitor
This is Tarjan’s algorithm for strongly connected components, from his paper “Depth first search and linear graph algorithms”.

#to_adjacency ⇒ DirectedAdjacencyGraph
Convert a general graph to an AdjacencyGraph.

#to_dot_graph(params = {}) ⇒ Object
Return a DOT::Digraph for directed graphs or a DOT::Graph for an undirected Graph.

#to_s ⇒ String
Utility method to show a string representation of the edges of the graph.

#to_undirected ⇒ AdjacencyGraph
Return a new AdjacencyGraph which has the same set of vertices.

#topsort_iterator ⇒ TopsortIterator
For the graph.

#transitive_closure ⇒ Object
Returns an DirectedAdjacencyGraph which is the transitive closure of this graph.

#transitive_reduction ⇒ Object
Returns an DirectedAdjacencyGraph which is the transitive reduction of this graph.
 #vertex_id(v) ⇒ Object

#vertex_label(v) ⇒ Object
Returns a label for vertex v.

#vertices ⇒ Array
Synonym for #to_a inherited by Enumerable.

#vertices_filtered_by(&filter) ⇒ ImplicitGraph
Returns a new ImplicitGraph which has as vertices all vertices of the receiver which satisfy the predicate filter.

#write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {}) ⇒ Object
Use dot to create a graphical representation of the graph.
Instance Method Details
#acyclic? ⇒ Boolean
Returns true if the graph contains no cycles. This is only meaningful for directed graphs. Returns false for undirected graphs.
75 76 77 
# File 'lib/rgl/topsort.rb', line 75 def acyclic? topsort_iterator.length == num_vertices end 
#adjacent_vertices(v) ⇒ Array
Returns of vertices adjacent to vertex v
.
230 231 232 233 234 
# File 'lib/rgl/base.rb', line 230 def adjacent_vertices(v) r = [] each_adjacent(v) { u r << u } r end 
#bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) ⇒ Hash[Object,Array]
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 onevertex path  [source].
Unlike Dijkstra algorithm, BellmanFord shortest paths algorithm works with negative edge weights.
Raises ArgumentError if an edge weight is undefined.
Raises ArgumentError or the graph has negativeweight cycles. This behavior can be overridden my a custom handler for visitor’s edge_not_minimized event.
109 110 111 
# File 'lib/rgl/bellman_ford.rb', line 109 def bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) BellmanFordAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source) end 
#bfs_iterator(v = self.detect { x true }) ⇒ BFSIterator
Returns starting at vertex v.
111 112 113 
# File 'lib/rgl/traversal.rb', line 111 def bfs_iterator(v = self.detect { x true }) BFSIterator.new(self, v) end 
#bfs_search_tree_from(v) ⇒ DirectedAdjacencyGraph
This method uses the tree_edge_event
of BFSIterator to record all tree edges of the search tree in the result.
119 120 121 122 123 124 125 126 127 128 129 130 131 132 
# File 'lib/rgl/traversal.rb', line 119 def bfs_search_tree_from(v) unless defined?(DirectedAdjacencyGraph) require 'rgl/adjacency' end bfs = bfs_iterator(v) tree = DirectedAdjacencyGraph.new bfs.set_tree_edge_event_handler do from, to tree.add_edge(from, to) end bfs.set_to_end # does the search tree end 
#bipartite? ⇒ Boolean
Returns true if the graph is bipartite. Otherwise returns false.
38 39 40 
# File 'lib/rgl/bipartite.rb', line 38 def bipartite? !bipartite_sets.nil? end 
#bipartite_sets ⇒ Array
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.
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
# File 'lib/rgl/bipartite.rb', line 14 def bipartite_sets raise NotUndirectedError.new('bipartite sets can only be found for an undirected graph') if directed? bfs = BipartiteBFSIterator.new(self) # if necessary, we start BFS from each vertex to make sure # that all connected components of the graph are processed each_vertex do u next if bfs.finished_vertex?(u) bfs.reset_start(u) bfs.move_forward_until { bfs.found_odd_cycle } return if bfs.found_odd_cycle end bfs.bipartite_sets_map.inject([[], []]) do sets, (vertex, set) sets[set] << vertex sets end end 
#condensation_graph ⇒ Object
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.
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 
# File 'lib/rgl/condensation.rb', line 17 def condensation_graph raise NotDirectedError, "condensation_graph only supported for directed graphs" unless directed? # Get the component map for the strongly connected components. comp_map = strongly_connected_components.comp_map # Invert the map such that for any number, n, in the component map a Set # instance is created containing all of the nodes which map to n. The Set # instances will be used to map to the number, n, with which the elements # of the set are associated. inv_comp_map = {} comp_map.each { v, n (inv_comp_map[n] = Set.new) << v } # Create an ImplicitGraph where the nodes are the strongly connected # components of this graph and the edges are the edges of this graph which # cross between the strongly connected components. ImplicitGraph.new do g g.vertex_iterator do b inv_comp_map.each_value(&b) end g.adjacent_iterator do scc, b scc.each do v each_adjacent(v) do w # Do not make the cluster reference itself in the graph. if comp_map[v] != comp_map[w] b.call(inv_comp_map[comp_map[w]]) end end end end g.directed = true end end 
#depth_first_search(vis = DFSVisitor.new(self), &b) ⇒ Object
Do a recursive DFS search on the whole graph. If a block is passed, it is called on each finish_vertex
event. See #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).
183 184 185 186 187 188 189 190 
# File 'lib/rgl/traversal.rb', line 183 def depth_first_search(vis = DFSVisitor.new(self), &b) each_vertex do u unless vis.finished_vertex?(u) vis.handle_start_vertex(u) depth_first_visit(u, vis, &b) end end end 
#depth_first_visit(u, vis = DFSVisitor.new(self), &b) ⇒ Object
Start a depth first search at vertex u. The block b is called on each finish_vertex
event.
195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 
# File 'lib/rgl/traversal.rb', line 195 def depth_first_visit(u, vis = DFSVisitor.new(self), &b) vis.color_map[u] = :GRAY vis.handle_examine_vertex(u) each_adjacent(u) do v vis.handle_examine_edge(u, v) if vis.follow_edge?(u, v) # (u,v) is a tree edge vis.handle_tree_edge(u, v) # also discovers v # color of v was :WHITE. Will be marked :GRAY in recursion depth_first_visit(v, vis, &b) else # (u,v) is a non tree edge if vis.color_map[v] == :GRAY vis.handle_back_edge(u, v) # (u,v) has gray target else vis.handle_forward_edge(u, v) # (u,v) is a cross or forward edge end end end vis.color_map[u] = :BLACK vis.handle_finish_vertex(u) # finish vertex b.call(u) end 
#dfs_iterator(v = self.detect { x true }) ⇒ DFSIterator
Returns staring at vertex v.
171 172 173 
# File 'lib/rgl/traversal.rb', line 171 def dfs_iterator(v = self.detect { x true }) DFSIterator.new(self, v) end 
#dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) ⇒ Object
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.
116 117 118 
# File 'lib/rgl/dijkstra.rb', line 116 def dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_path(source, target) end 
#dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) ⇒ Object
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 onevertex path  [source].
Raises ArgumentError if edge weight is negative or undefined.
128 129 130 
# File 'lib/rgl/dijkstra.rb', line 128 def dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source) end 
#directed? ⇒ Boolean
Is the graph directed? The default returns false.
180 181 182 
# File 'lib/rgl/base.rb', line 180 def directed? false end 
#dotty(params = {}) ⇒ Object
Call dotty for the graph which is written to the file ‘graph.dot’ in the current directory.
103 104 105 106 107 108 109 110 111 
# File 'lib/rgl/dot.rb', line 103 def dotty(params = {}) dotfile = "graph.dot" File.open(dotfile, "w") do f print_dotted_on(params, f) end unless system("dotty", dotfile) raise "Error executing dotty. Did you install GraphViz?" end end 
#each(&block) ⇒ Object
Vertices get enumerated. A graph is thus an enumerable of vertices.
175 176 177 
# File 'lib/rgl/base.rb', line 175 def each(&block) each_vertex(&block) end 
#each_adjacent(v, &block) ⇒ Object
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.
152 153 154 
# File 'lib/rgl/base.rb', line 152 def each_adjacent(v, &block) # :yields: v raise NotImplementedError end 
#each_connected_component {comp ... } ⇒ Object
Compute the connected components of an undirected graph, using a DFS (Depthfirst 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.
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 
# File 'lib/rgl/connected_components.rb', line 23 def each_connected_component raise NotUndirectedError, "each_connected_component only works " + "for undirected graphs." if directed? comp = [] vis = DFSVisitor.new(self) vis.set_finish_vertex_event_handler { v comp << v } vis.set_start_vertex_event_handler do v yield comp unless comp.empty? comp = [] end depth_first_search(vis) { v } yield comp unless comp.empty? end 
#each_edge(&block) ⇒ Object
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).
163 164 165 166 167 168 169 170 171 
# File 'lib/rgl/base.rb', line 163 def each_edge(&block) if directed? each_vertex do u each_adjacent(u) { v yield u, v } end else each_edge_aux(&block) # concrete graphs should to this better end end 
#each_vertex(&block) ⇒ Object
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.
143 144 145 
# File 'lib/rgl/base.rb', line 143 def each_vertex(&block) # :yields: v raise NotImplementedError end 
#edge_class ⇒ Class
Returns the class for edges: Edge::DirectedEdge or Edge::UnDirectedEdge.
215 216 217 
# File 'lib/rgl/base.rb', line 215 def edge_class directed? ? DirectedEdge : UnDirectedEdge end 
#edges ⇒ Array
It uses #each_edge to compute the edges
221 222 223 224 225 226 
# File 'lib/rgl/base.rb', line 221 def edges result = [] c = edge_class each_edge { u, v result << c.new(u, v) } result end 
#edges_filtered_by(&filter) ⇒ ImplicitGraph
Returns a new ImplicitGraph which has as edges all edges of the receiver which satisfy the predicate filter (a block with two parameters).
146 147 148 149 150 151 152 153 154 155 156 157 158 
# File 'lib/rgl/implicit.rb', line 146 def edges_filtered_by(&filter) implicit_graph do g g.adjacent_iterator do v, b self.each_adjacent(v) do u b.call(u) if filter.call(v, u) end end g.edge_iterator do b self.each_edge { u, v b.call(u, v) if filter.call(u, v) } end end end 
#empty? ⇒ Boolean
Returns true if the graph has no vertices, i.e. num_vertices == 0.
203 204 205 
# File 'lib/rgl/base.rb', line 203 def empty? num_vertices.zero? end 
#eql?(other) ⇒ Boolean Also known as: ==
Two graphs are equal iff they have equal directed? property as well as vertices and edges sets.
271 272 273 
# File 'lib/rgl/base.rb', line 271 def eql?(other) equal?(other)  eql_graph?(other) end 
#has_edge?(u, v) ⇒ Boolean
Returns true if (u, v) is an edge of the graph.
194 195 196 197 198 199 
# File 'lib/rgl/base.rb', line 194 def has_edge?(u, v) each_adjacent(u) do w return true if v == w end return false end 
#has_vertex?(v) ⇒ Boolean
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).
188 189 190 
# File 'lib/rgl/base.rb', line 188 def has_vertex?(v) include?(v) # inherited from enumerable end 
#implicit_graph {result ... } ⇒ ImplicitGraph
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.
164 165 166 167 168 169 170 171 172 173 
# File 'lib/rgl/implicit.rb', line 164 def implicit_graph result = ImplicitGraph.new do g g.vertex_iterator { b self.each_vertex(&b) } g.adjacent_iterator { v, b self.each_adjacent(v, &b) } g.directed = self.directed? end yield result if block_given? # let client overwrite defaults result end 
#maximum_flow(edge_capacities_map, source, sink) ⇒ Hash
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 nonnegative, 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.
136 137 138 
# File 'lib/rgl/edmonds_karp.rb', line 136 def maximum_flow(edge_capacities_map, source, sink) EdmondsKarpAlgorithm.new(self, edge_capacities_map).maximum_flow(source, sink) end 
#num_edges ⇒ int
Returns the number of edges.
256 257 258 259 260 
# File 'lib/rgl/base.rb', line 256 def num_edges r = 0 each_edge { u, v r +=1 } r end 
#out_degree(v) ⇒ int
Returns the number of outedges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v
.
240 241 242 243 244 
# File 'lib/rgl/base.rb', line 240 def out_degree(v) r = 0 each_adjacent(v) { u r += 1 } r end 
#path?(source, target) ⇒ Boolean
Checks whether a path exists between source and target vertices in the graph.
10 11 12 13 14 15 
# File 'lib/rgl/path.rb', line 10 def path?(source, target) return false unless has_vertex?(source) bfs_iterator = bfs_iterator(source) bfs_iterator.include?(target) end 
#prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) ⇒ Object
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.
49 50 51 
# File 'lib/rgl/prim.rb', line 49 def prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) PrimAlgorithm.new(self, edge_weights_map, visitor).minimum_spanning_tree(start_vertex) end 
#print_dotted_on(params = {}, s = $stdout) ⇒ Object
Output the DOTgraph to stream s.
96 97 98 
# File 'lib/rgl/dot.rb', line 96 def print_dotted_on(params = {}, s = $stdout) s << to_dot_graph(params).to_s << "\n" end 
#reverse ⇒ DirectedAdjacencyGraph
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.
182 183 184 185 186 187 188 
# File 'lib/rgl/adjacency.rb', line 182 def reverse return self unless directed? result = DirectedAdjacencyGraph.new each_vertex { v result.add_vertex v } each_edge { u, v result.add_edge(v, u) } result end 
#set_edge_options(u, v, **options) ⇒ Object
Set the configuration values for the given edge
34 35 36 37 38 39 40 41 42 
# File 'lib/rgl/dot.rb', line 34 def (u, v, **) edge = edge_class.new(u, v) @edge_options = {} @edge_options[edge] = {} RGL::DOT::EDGE_OPTS.each do opt @edge_options[edge][:"#{opt}"] = [:"#{opt}"] if .key?(:"#{opt}") end end 
#set_vertex_options(vertex, **options) ⇒ Object
Set the configuration values for the given vertex
24 25 26 27 28 29 30 31 
# File 'lib/rgl/dot.rb', line 24 def (vertex, **) @vertex_options = {} @vertex_options[vertex] = {} RGL::DOT::NODE_OPTS.each do opt @vertex_options[vertex][:"#{opt}"] = [:"#{opt}"] if .key?(:"#{opt}") end end 
#size ⇒ int Also known as: num_vertices
Returns the number of vertices.
248 249 250 
# File 'lib/rgl/base.rb', line 248 def size # Why not in Enumerable? inject(0) { n, v n + 1 } end 
#strongly_connected_components ⇒ TarjanSccVisitor
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 = "146160",
month = jun,
year = "1972",
CODEN = "SMJCAT",
ISSN = "00975397 (print), 10957111 (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
.
135 136 137 138 139 140 141 142 
# File 'lib/rgl/connected_components.rb', line 135 def strongly_connected_components raise NotDirectedError, "strong_components only works for directed graphs." unless directed? vis = TarjanSccVisitor.new(self) depth_first_search(vis) { v } vis end 
#to_adjacency ⇒ DirectedAdjacencyGraph
Convert a general graph to an AdjacencyGraph. If the graph is directed, returns a DirectedAdjacencyGraph; otherwise, returns an AdjacencyGraph.
170 171 172 173 174 175 
# File 'lib/rgl/adjacency.rb', line 170 def to_adjacency result = (directed? ? DirectedAdjacencyGraph : AdjacencyGraph).new each_vertex { v result.add_vertex(v) } each_edge { u, v result.add_edge(u, v) } result end 
#to_dot_graph(params = {}) ⇒ Object
Return a DOT::Digraph for directed graphs or a DOT::Graph for an undirected RGL::Graph. params can contain any graph property specified in rdot.rb.
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 
# File 'lib/rgl/dot.rb', line 48 def to_dot_graph(params = {}) params['name'] = self.class.name.gsub(/:/, '_') fontsize = params['fontsize'] ? params['fontsize'] : '8' graph = (directed? ? DOT::Digraph : DOT::Graph).new(params) edge_class = directed? ? DOT::DirectedEdge : DOT::Edge each_vertex do v = { 'name' => vertex_id(v), 'fontsize' => fontsize, 'label' => vertex_label(v) } = if @vertex_options && @vertex_options[v] RGL::DOT::NODE_OPTS.each do opt if @vertex_options[v].key?(:"#{opt}") ["#{opt}"] = @vertex_options[v].fetch(:"#{opt}") end end end graph << DOT::Node.new() end edges.each do edge = { 'from' => edge.source, 'to' => edge.target, 'fontsize' => fontsize } = if @edge_options && @edge_options[edge] RGL::DOT::EDGE_OPTS.each do opt if @edge_options[edge].key?(:"#{opt}") ["#{opt}"] = @edge_options[edge].fetch(:"#{opt}") end end end graph << edge_class.new() end graph end 
#to_s ⇒ String
Utility method to show a string representation of the edges of the graph.
264 265 266 
# File 'lib/rgl/base.rb', line 264 def to_s edges.collect {e e.to_s}.sort.join end 
#to_undirected ⇒ AdjacencyGraph
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
.
196 197 198 199 
# File 'lib/rgl/adjacency.rb', line 196 def to_undirected return self unless directed? AdjacencyGraph.new(Set, self) end 
#topsort_iterator ⇒ TopsortIterator
Returns for the graph.
68 69 70 
# File 'lib/rgl/topsort.rb', line 68 def topsort_iterator TopsortIterator.new(self) end 
#transitive_closure ⇒ Object
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 selfreferencing edges.
This method should run in O(VE) time, where V and E are the number of vertices and edges respectively.
Raises NotDirectedError if run on an undirected graph.
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 
# File 'lib/rgl/transitivity.rb', line 20 def transitive_closure raise NotDirectedError, "transitive_closure only supported for directed graphs" unless directed? # Compute a condensation graph in order to hide cycles. cg = condensation_graph # Use a depth first search to calculate the transitive closure over the # condensation graph. This ensures that as we traverse up the graph we # know the transitive closure of each subgraph rooted at each node # starting at the leaves. Subsequent root nodes which consume these # subgraphs by way of the nodes' immediate successors can then immediately # add edges to the roots of the subgraphs and to every successor of those # roots. tc_cg = DirectedAdjacencyGraph.new cg.depth_first_search do v # For each vertex v, w, and x where the edges v > w and w > x exist in # the source graph, add edges v > w and v > x to the target graph. cg.each_adjacent(v) do w tc_cg.add_edge(v, w) tc_cg.each_adjacent(w) do x tc_cg.add_edge(v, x) end end # Ensure that a vertex with no in or out edges is added to the graph. tc_cg.add_vertex(v) end # Expand the condensed transitive closure. # # For each trivial strongly connected component in the condensed graph, # add the single node it contains to the new graph and add edges for each # edge the node begins in the original graph. # For each NONtrivial strongly connected component in the condensed # graph, add each node it contains to the new graph and add edges to # every node in the strongly connected component, including self # referential edges. Then for each edge of the original graph from any # of the contained nodes, add edges from each of the contained nodes to # all the edge targets. g = DirectedAdjacencyGraph.new tc_cg.each_vertex do scc scc.each do v # Add edges between all members of nontrivial strongly connected # components (size > 1) and ensure that self referential edges are # added when necessary for trivial strongly connected components. if scc.size > 1  has_edge?(v, v) scc.each do w g.add_edge(v, w) end end # Ensure that a vertex with no in or out edges is added to the graph. g.add_vertex(v) end # Add an edge from every member of a strongly connected component to # every member of each strongly connected component to which the former # points. tc_cg.each_adjacent(scc) do scc2 scc.each do v scc2.each do w g.add_edge(v, w) end end end end # Finally, the transitive closure... g end 
#transitive_reduction ⇒ Object
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(VE) time, where V and E are the number of vertices and edges respectively.
Raises NotDirectedError if run on an undirected graph.
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 
# File 'lib/rgl/transitivity.rb', line 100 def transitive_reduction raise NotDirectedError, "transitive_reduction only supported for directed graphs" unless directed? # Compute a condensation graph in order to hide cycles. cg = condensation_graph # Use a depth first search to compute the transitive reduction over the # condensed graph. This is similar to the computation of the transitive # closure over the graph in that for any node of the graph all nodes # reachable from the node are tracked. Using a depth first search ensures # that all nodes reachable from a target node are known when considering # whether or not to add an edge pointing to that target. tr_cg = DirectedAdjacencyGraph.new paths_from = {} cg.depth_first_search do v paths_from[v] = Set.new cg.each_adjacent(v) do w # Only add the edge v > w if there is no other edge v > x such that # w is reachable from x. Make sure to completely skip the case where # x == w. unless cg.to_enum(:each_adjacent, v).any? { x x != w && paths_from[x].include?(w) } tr_cg.add_edge(v, w) # For each vertex v, track all nodes reachable from v by adding node # w to the list as well as all the nodes readable from w. paths_from[v] << w paths_from[v].merge(paths_from[w]) end end # Ensure that a vertex with no in or out edges is added to the graph. tr_cg.add_vertex(v) end # Expand the condensed transitive reduction. # # For each trivial strongly connected component in the condensed graph, # add the single node it contains to the new graph and add edges for each # edge the node begins in the original graph. # For each NONtrivial strongly connected component in the condensed # graph, add each node it contains to the new graph and add arbitrary # edges between the nodes to form a simple cycle. Then for each strongly # connected component adjacent to the current one, find and add the first # edge which exists in the original graph, starts in the first strongly # connected component, and ends in the second strongly connected # component. g = DirectedAdjacencyGraph.new tr_cg.each_vertex do scc # Make a cycle of the contents of nontrivial strongly connected # components. scc_arr = scc.to_a if scc.size > 1  has_edge?(scc_arr.first, scc_arr.first) 0.upto(scc_arr.size  2) do idx g.add_edge(scc_arr[idx], scc_arr[idx + 1]) end g.add_edge(scc_arr.last, scc_arr.first) end # Choose a single edge between the members of two different strongly # connected component to add to the graph. edges = self.to_enum(:each_edge) tr_cg.each_adjacent(scc) do scc2 g.add_edge( *edges.find do v, w scc.member?(v) && scc2.member?(w) end ) end # Ensure that a vertex with no in or out edges is added to the graph. scc.each do v g.add_vertex(v) end end # Finally, the transitive reduction... g end 
#vertex_id(v) ⇒ Object
19 20 21 
# File 'lib/rgl/dot.rb', line 19 def vertex_id(v) v end 
#vertex_label(v) ⇒ Object
Returns a label for vertex v. Default is v.to_s
15 16 17 
# File 'lib/rgl/dot.rb', line 15 def vertex_label(v) v.to_s end 
#vertices ⇒ Array
Synonym for #to_a inherited by Enumerable.
209 210 211 
# File 'lib/rgl/base.rb', line 209 def vertices to_a end 
#vertices_filtered_by(&filter) ⇒ ImplicitGraph
Returns a new ImplicitGraph which has as vertices all vertices of the receiver which satisfy the predicate filter.
The methods provides similar functionality as BGLs Filtered Graph
125 126 127 128 129 130 131 132 133 134 135 
# File 'lib/rgl/implicit.rb', line 125 def vertices_filtered_by(&filter) implicit_graph do g g.vertex_iterator do b self.each_vertex { v b.call(v) if filter.call(v) } end g.adjacent_iterator do v, b self.each_adjacent(v) { u b.call(u) if filter.call(u) } end end end 
#write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {}) ⇒ Object
Use dot to create a graphical representation of the graph. Returns the filename of the graphics file.
116 117 118 119 120 121 122 123 124 125 126 127 128 
# File 'lib/rgl/dot.rb', line 116 def write_to_graphic_file(fmt = 'png', dotfile = "graph", = {}) src = dotfile + ".dot" dot = dotfile + "." + fmt File.open(src, 'w') do f f << self.to_dot_graph().to_s << "\n" end unless system("dot T#{fmt} #{src} o #{dot}") raise "Error executing dot. Did you install GraphViz?" end dot end 