In BGL terminology the module Graph defines the graph concept (see www.boost.org/libs/graph/doc/graph_concepts.html). 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. num_vertices or num_edges.

Each graph is an enumerable of vertices.

- ==
- acyclic?
- adjacent_vertices
- bfs_iterator
- bfs_search_tree_from
- condensation_graph
- depth_first_search
- depth_first_visit
- dfs_iterator
- directed?
- dotty
- each
- each_adjacent
- each_connected_component
- each_edge
- each_vertex
- edge_class
- edges
- edges_filtered_by
- empty?
- eql?
- has_vertex?
- implicit_graph
- num_edges
- num_vertices
- out_degree
- print_dotted_on
- reverse
- size
- strongly_connected_components
- to_adjacency
- to_dot_graph
- to_s
- to_undirected
- topsort_iterator
- transitive_closure
- transitive_reduction
- vertices
- vertices_filtered_by
- write_to_graphic_file

Returns true if the graph contains no cycles. This is only meaningful for directed graphs. Returns false for undirected graphs.

[ show source ]

# File lib/rgl/topsort.rb, line 67 67: def acyclic? 68: topsort_iterator.length == num_vertices 69: end

Returns an array of vertices adjacent to
vertex *v*.

[ show source ]

# File lib/rgl/base.rb, line 168 168: def adjacent_vertices (v) 169: r = [] 170: each_adjacent(v) {|u| r << u} 171: r 172: end

Returns a BFSIterator, starting at vertex
*v*.

[ show source ]

# File lib/rgl/traversal.rb, line 230 230: def bfs_iterator (v = self.detect { |x| true}) 231: BFSIterator.new(self, v) 232: end

Returns a DirectedAdjacencyGraph,
which represents a BFS search tree starting at *v*. This method uses
the tree_edge_event of BFSIterator to record
all tree edges of the search tree in the
result.

[ show source ]

# File lib/rgl/traversal.rb, line 238 238: def bfs_search_tree_from (v) 239: require 'rgl/adjacency' 240: bfs = bfs_iterator(v) 241: tree = DirectedAdjacencyGraph.new 242: bfs.set_tree_edge_event_handler { |from, to| 243: tree.add_edge(from, to) 244: } 245: bfs.set_to_end # does the search 246: tree 247: end

Returns an RGL::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 RGL::NotDirectedError if run on an undirected graph.

[ show source ]

# File lib/rgl/condensation.rb, line 13 13: def condensation_graph 14: raise NotDirectedError, 15: "condensation_graph only supported for directed graphs" unless directed? 16: 17: # Get the component map for the strongly connected components. 18: comp_map = strongly_connected_components.comp_map 19: # Invert the map such that for any number, n, in the component map a Set 20: # instance is created containing all of the nodes which map to n. The Set 21: # instances will be used to map to the number, n, with which the elements 22: # of the set are associated. 23: inv_comp_map = {} 24: comp_map.each { |v, n| (inv_comp_map[n] ||= Set.new) << v } 25: 26: # Create an ImplicitGraph where the nodes are the strongly connected 27: # components of this graph and the edges are the edges of this graph which 28: # cross between the strongly connected components. 29: ImplicitGraph.new do |g| 30: g.vertex_iterator do |b| 31: inv_comp_map.each_value(&b) 32: end 33: g.adjacent_iterator do |scc, b| 34: scc.each do |v| 35: each_adjacent(v) do |w| 36: # Do not make the cluster reference itself in the graph. 37: if comp_map[v] != comp_map[w] then 38: b.call(inv_comp_map[comp_map[w]]) 39: end 40: end 41: end 42: end 43: g.directed = true 44: end 45: end

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.

[ show source ]

# File lib/rgl/traversal.rb, line 300 300: def depth_first_search (vis = DFSVisitor.new(self), &b) 301: each_vertex do |u| 302: unless vis.finished_vertex?(u) 303: vis.handle_start_vertex(u) 304: depth_first_visit(u, vis, &b) 305: end 306: end 307: end

Start a depth first search at vertex *u*. The block *b* is
called on each finish_vertex event.

[ show source ]

# File lib/rgl/traversal.rb, line 312 312: def depth_first_visit (u, vis = DFSVisitor.new(self), &b) 313: vis.color_map[u] = :GRAY 314: vis.handle_examine_vertex(u) 315: each_adjacent(u) { |v| 316: vis.handle_examine_edge(u, v) 317: if vis.follow_edge?(u, v) # (u,v) is a tree edge 318: vis.handle_tree_edge(u, v) # also discovers v 319: vis.color_map[v] = :GRAY # color of v was :WHITE 320: depth_first_visit(v, vis, &b) 321: else # (u,v) is a non tree edge 322: if vis.color_map[v] == :GRAY 323: vis.handle_back_edge(u, v) # (u,v) has gray target 324: else 325: vis.handle_forward_edge(u, v) # (u,v) is a cross or forward edge 326: end 327: end 328: } 329: vis.color_map[u] = :BLACK 330: vis.handle_finish_vertex(u) # finish vertex 331: b.call(u) 332: end

Returns a DFSIterator staring at vertex
*v*.

[ show source ]

# File lib/rgl/traversal.rb, line 292 292: def dfs_iterator (v = self.detect { |x| true }) 293: DFSIterator.new(self, v) 294: end

Is the graph directed? The default returns false.

[ show source ]

# File lib/rgl/base.rb, line 140 140: def directed?; false; end

Call dotty for the graph which is written to the file ‘graph.dot’ in the # current directory.

[ show source ]

# File lib/rgl/dot.rb, line 47 47: def dotty (params = {}) 48: dotfile = "graph.dot" 49: File.open(dotfile, "w") {|f| 50: print_dotted_on(params, f) 51: } 52: system("dotty", dotfile) 53: end

[ show source ]

# File lib/rgl/base.rb, line 137 137: def each(&block); each_vertex(&block); 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.

[ show source ]

# File lib/rgl/base.rb, line 113 113: def each_adjacent (v) # :yields: v 114: raise NotImplementedError 115: 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.

[ show source ]

# File lib/rgl/connected_components.rb, line 23 23: def each_connected_component 24: raise NotUndirectedError, 25: "each_connected_component only works " + 26: "for undirected graphs." if directed? 27: comp = [] 28: vis = DFSVisitor.new(self) 29: vis.set_finish_vertex_event_handler { |v| comp << v } 30: vis.set_start_vertex_event_handler { |v| 31: yield comp unless comp.empty? 32: comp = [] 33: } 34: depth_first_search(vis) { |v| } 35: yield comp unless comp.empty? 36: end

The each_edge iterator should provide efficient access to all edges of the graph. Its defines the 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
graph the function is inefficient because we must not yield (v,u) if we
already visited edge (u,v).

[ show source ]

# File lib/rgl/base.rb, line 124 124: def each_edge (&block) 125: if directed? 126: each_vertex { |u| 127: each_adjacent(u) { |v| yield u,v } 128: } 129: else 130: each_edge_aux(&block) # concrete graphs should to this better 131: end 132: end

The each_vertex iterator defines the set of vertices. This method must be defined by concrete graph classes. It defines the BGL VertexListGraph concept.

[ show source ]

# File lib/rgl/base.rb, line 106 106: def each_vertex () # :yields: v 107: raise NotImplementedError 108: end

Returns the class for edges: DirectedEdge or UnDirectedEdge.

[ show source ]

# File lib/rgl/base.rb, line 156 156: def edge_class; directed? ? DirectedEdge : UnDirectedEdge; end

Return the array of edges (DirectedEdge or UnDirectedEdge) of the graph using each_edge, depending whether the graph is directed or not.

[ show source ]

# File lib/rgl/base.rb, line 160 160: def edges 161: result = [] 162: c = edge_class 163: each_edge { |u,v| result << c.new(u,v) } 164: result 165: end

Return 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]

[ show source ]

# File lib/rgl/implicit.rb, line 146 146: def edges_filtered_by (&filter) 147: implicit_graph { |g| 148: g.adjacent_iterator { |v, b| 149: self.each_adjacent(v) { |u| 150: b.call(u) if filter.call(v, u) 151: } 152: } 153: g.edge_iterator { |b| 154: self.each_edge { |u,v| b.call(u, v) if filter.call(u, v) } 155: } 156: } 157: end

[ show source ]

# File lib/rgl/base.rb, line 150 150: def empty?; num_vertices.zero?; end

[ show source ]

# File lib/rgl/base.rb, line 197 197: def eql?(g) 198: equal?(g) or 199: begin 200: g.is_a?(Graph) and directed? == g.directed? and 201: g.inject(0) { |n, v| has_vertex?(v) or return false; n+1} == 202: num_vertices and begin 203: ng = 0 204: g.each_edge {|u,v| has_edge? u,v or return false; ng += 1} 205: ng == num_edges 206: end 207: end 208: 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).

[ show source ]

# File lib/rgl/base.rb, line 145 145: def has_vertex?(v); include?(v); 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.

[ show source ]

# File lib/rgl/implicit.rb, line 163 163: def implicit_graph 164: result = ImplicitGraph.new { |g| 165: g.vertex_iterator { |b| self.each_vertex(&b) } 166: g.adjacent_iterator { |v, b| self.each_adjacent(v, &b) } 167: g.directed = self.directed? 168: } 169: yield result if block_given? # let client overwrite defaults 170: result 171: end

Returns the number of edges.

[ show source ]

# File lib/rgl/base.rb, line 189 189: def num_edges; r = 0; each_edge {|u,v| r +=1}; r; end

Alias for size

Returns the number of out-edges (for
directed graphs) or the number of incident edges (for undirected graphs) of vertex
*v*.

[ show source ]

# File lib/rgl/base.rb, line 176 176: def out_degree (v) 177: r = 0 178: each_adjacent(v) { |u| r += 1} 179: r 180: end

Output the DOT-graph to stream *s*.

[ show source ]

# File lib/rgl/dot.rb, line 40 40: def print_dotted_on (params = {}, s = $stdout) 41: s << to_dot_graph(params).to_s << "\n" 42: 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.

[ show source ]

# File lib/rgl/adjacency.rb, line 186 186: def reverse 187: return self unless directed? 188: result = DirectedAdjacencyGraph.new 189: each_vertex { |v| result.add_vertex v } 190: each_edge { |u,v| result.add_edge(v, u) } 191: result 192: end

Returns the number of vertices.

[ show source ]

# File lib/rgl/base.rb, line 183 183: def size() # Why not in Enumerable? 184: inject(0) { |n, v| n + 1 } 185: 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.

[ show source ]

# File lib/rgl/connected_components.rb, line 129 129: def strongly_connected_components 130: raise NotDirectedError, 131: "strong_components only works for directed graphs." unless directed? 132: vis = TarjanSccVisitor.new(self) 133: depth_first_search(vis) { |v| } 134: vis 135: end

Convert a general graph to an AdjacencyGraph. If the graph is directed, returns a DirectedAdjacencyGraph; otherwise, returns an AdjacencyGraph.

[ show source ]

# File lib/rgl/adjacency.rb, line 174 174: def to_adjacency 175: result = (directed? ? DirectedAdjacencyGraph : AdjacencyGraph).new 176: each_vertex { |v| result.add_vertex(v) } 177: each_edge { |u,v| result.add_edge(u, v) } 178: result 179: end

Return a RGL::DOT::Digraph for directed
graphs or a DOT::Subgraph for an undirected
Graph. *params* can contain any graph
property specified in rdot.rb.

[ show source ]

# File lib/rgl/dot.rb, line 19 19: def to_dot_graph (params = {}) 20: params['name'] ||= self.class.name.gsub(/:/,'_') 21: fontsize = params['fontsize'] ? params['fontsize'] : '8' 22: graph = (directed? ? DOT::Digraph : DOT::Subgraph).new(params) 23: edge_class = directed? ? DOT::DirectedEdge : DOT::Edge 24: each_vertex do |v| 25: name = v.to_s 26: graph << DOT::Node.new('name' => name, 27: 'fontsize' => fontsize, 28: 'label' => name) 29: end 30: each_edge do |u,v| 31: graph << edge_class.new('from' => u.to_s, 32: 'to' => v.to_s, 33: 'fontsize' => fontsize) 34: end 35: graph 36: end

Utility method to show a string representation of the edges of the graph.

[ show source ]

# File lib/rgl/base.rb, line 192 192: def to_s 193: edges.sort.to_s 194: 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.

[ show source ]

# File lib/rgl/adjacency.rb, line 200 200: def to_undirected 201: return self unless directed? 202: AdjacencyGraph.new(Set, self) 203: end

Returns a TopsortIterator.

[ show source ]

# File lib/rgl/topsort.rb, line 60 60: def topsort_iterator 61: TopsortIterator.new(self) 62: end

Returns an RGL::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 RGL::NotDirectedError if run on an undirected graph.

[ show source ]

# File lib/rgl/transitivity.rb, line 19 19: def transitive_closure 20: raise NotDirectedError, 21: "transitive_closure only supported for directed graphs" unless directed? 22: 23: # Compute a condensation graph in order to hide cycles. 24: cg = condensation_graph 25: 26: # Use a depth first search to calculate the transitive closure over the 27: # condensation graph. This ensures that as we traverse up the graph we 28: # know the transitive closure of each subgraph rooted at each node 29: # starting at the leaves. Subsequent root nodes which consume these 30: # subgraphs by way of the nodes' immediate successors can then immediately 31: # add edges to the roots of the subgraphs and to every successor of those 32: # roots. 33: tc_cg = DirectedAdjacencyGraph.new 34: cg.depth_first_search do |v| 35: # For each vertex v, w, and x where the edges v -> w and w -> x exist in 36: # the source graph, add edges v -> w and v -> x to the target graph. 37: cg.each_adjacent(v) do |w| 38: tc_cg.add_edge(v, w) 39: tc_cg.each_adjacent(w) do |x| 40: tc_cg.add_edge(v, x) 41: end 42: end 43: # Ensure that a vertex with no in or out edges is added to the graph. 44: tc_cg.add_vertex(v) 45: end 46: 47: # Expand the condensed transitive closure. 48: # 49: # For each trivial strongly connected component in the condensed graph, 50: # add the single node it contains to the new graph and add edges for each 51: # edge the node begins in the original graph. 52: # For each NON-trivial strongly connected component in the condensed 53: # graph, add each node it contains to the new graph and add edges to 54: # every node in the strongly connected component, including self 55: # referential edges. Then for each edge of the original graph from any 56: # of the contained nodes, add edges from each of the contained nodes to 57: # all the edge targets. 58: g = DirectedAdjacencyGraph.new 59: tc_cg.each_vertex do |scc| 60: scc.each do |v| 61: # Add edges between all members of non-trivial strongly connected 62: # components (size > 1) and ensure that self referential edges are 63: # added when necessary for trivial strongly connected components. 64: if scc.size > 1 || has_edge?(v, v) then 65: scc.each do |w| 66: g.add_edge(v, w) 67: end 68: end 69: # Ensure that a vertex with no in or out edges is added to the graph. 70: g.add_vertex(v) 71: end 72: # Add an edge from every member of a strongly connected component to 73: # every member of each strongly connected component to which the former 74: # points. 75: tc_cg.each_adjacent(scc) do |scc2| 76: scc.each do |v| 77: scc2.each do |w| 78: g.add_edge(v, w) 79: end 80: end 81: end 82: end 83: 84: # Finally, the transitive closure... 85: g 86: end

Returns an RGL::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 RGL::NotDirectedError if run on an undirected graph.

[ show source ]

# File lib/rgl/transitivity.rb, line 98 98: def transitive_reduction 99: raise NotDirectedError, 100: "transitive_reduction only supported for directed graphs" unless directed? 101: 102: # Compute a condensation graph in order to hide cycles. 103: cg = condensation_graph 104: 105: # Use a depth first search to compute the transitive reduction over the 106: # condensed graph. This is similar to the computation of the transitive 107: # closure over the graph in that for any node of the graph all nodes 108: # reachable from the node are tracked. Using a depth first search ensures 109: # that all nodes reachable from a target node are known when considering 110: # whether or not to add an edge pointing to that target. 111: tr_cg = DirectedAdjacencyGraph.new 112: paths_from = {} 113: cg.depth_first_search do |v| 114: paths_from[v] = Set.new 115: cg.each_adjacent(v) do |w| 116: # Only add the edge v -> w if there is no other edge v -> x such that 117: # w is reachable from x. Make sure to completely skip the case where 118: # x == w. 119: unless Enumerable::Enumerator.new(cg, :each_adjacent, v).any? do |x| 120: x != w && paths_from[x].include?(w) 121: end then 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) then 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 = Enumerable::Enumerator.new(self, :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

Return the array of vertices. Synonym for to_a inherited by Enumerable.

[ show source ]

# File lib/rgl/base.rb, line 153 153: def vertices; to_a; end

### Graph adaptors

Return a new ImplicitGraph which has as vertices all vertices of the receiver which satisfy the
predicate *filter*.

The methods provides similar functionaty as the BGL graph adapter filtered_graph (see BOOST_DOC/filtered_graph.html).

#### Example

def complete (n) set = n.integer? ? (1..n) : n RGL::ImplicitGraph.new { |g| g.vertex_iterator { |b| set.each(&b) } g.adjacent_iterator { |x, b| set.each { |y| b.call(y) unless x == y } } } 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)"

[ show source ]

# File lib/rgl/implicit.rb, line 126 126: def vertices_filtered_by (&filter) 127: implicit_graph { |g| 128: g.vertex_iterator { |b| 129: self.each_vertex { |v| b.call(v) if filter.call(v) } 130: } 131: g.adjacent_iterator { |v, b| 132: self.each_adjacent(v) { |u| b.call(u) if filter.call(u) } 133: } 134: } 135: end

Use dot to create a graphical representation of the graph. Returns the filename of the graphics file.

[ show source ]

# File lib/rgl/dot.rb, line 58 58: def write_to_graphic_file (fmt='png', dotfile="graph") 59: src = dotfile + ".dot" 60: dot = dotfile + "." + fmt 61: 62: File.open(src, 'w') do |f| 63: f << self.to_dot_graph.to_s << "\n" 64: end 65: 66: system( "dot -T#{fmt} #{src} -o #{dot}" ) 67: dot 68: end