UPDATE With some pointers from current RGL maintainer javanthropus it finally dawned on me that my approach to using RGL was, if not completely wrong, kludgy and inelegant.
The secret lies in RGL::ImplicitGraph.
ImplicitGraph is a bit more mysterious then the more straightforward RGL::AdjacencyGraph.
Where RGL::AdjacencyGraph is built from a defined set of edges like so dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6] setting up ImplicitGraph is done by defining the set of vertices, and the algorithm for determing the adjacencies of a give vertex. Below is an example from the example/examples directory in the RGL gem. I’ve just changed blocks from the {} format to do-end format.
def cycle (n) RGL::ImplicitGraph.new do |g| g.vertex_iterator do |b| 0.upto(n-1,&b) end g.adjacent_iterator do |x, b| b.call((x+1)%n) end g.directed = true end end
In this example, the method cycle will return a directed cyclic graph of length n. For example:
cycle(3) #=> [(0-1), (1-2), (2-0)].
Let’s step through what’s happening. Upon initialization, RGL::ImplicitGraph takes a block, as opposed to the Array used by RGL::AdjacencyGraph. Looking at the initialization source code:
def initialize @directed = false @vertex_iterator = EMPTY_VERTEX_ITERATOR @adjacent_iterator = EMPTY_NEIGHBOR_ITERATOR yield self if block_given? # Let client overwrite defaults. end
We see that we are yielding self to the block passed in. So the |g| of the block passed in for initialization is a fresh out of the oven ImplicitGraph object. Next, there are two additional blocks that are required in order to have a useful graph object. The first is the block passed into #vertex_iterator, and the second is the block passed into #adjacent_iterator. These two methods work in tandem to create our graph. A quick dive into the source code shows us:
def each_vertex (&block) # :nodoc: @vertex_iterator.call(block) end def each_adjacent (v, &block) # :nodoc: @adjacent_iterator.call(v, block) end
So in other words, the block we pass into vertex_iterator will be called whenever the ImplicitGraphs #each_vertex method is called (with a block as a parameter), likewise, the block passed into adjacent_iterator will be called whenever the ImplicitGraph’s #each_adjacent is called.
In the cycle example, the block passed into vertex_iterator is: { |b| 0.upto(n-1,&b) }
or rewriting a bit to illustrate what’s going on.
g.vertex_interator do |b| 0.upto(n-1) do |i| b.call(i) end end
So we iterate up to n-1 and have the block run against each iteration. But what is the block passed as |b|? That’s a bit more tricky. It gets called when you need to do something with the graph. In the #cycle example, it’s not actually ever invoked. But let’s say we wanted to inspect g by doing: p g that will invoke the #to_s method, which will in turn eventually invoke the #each_edge method, which looks like this:
def each_edge (&block) if directed? each_vertex { |u| each_adjacent(u) { |v| yield u,v } } else each_edge_aux(&block) # concrete graphs should to this better end end
And here we can see the block for #each_vertex:
each_vertex { |u| each_adjacent(u) { |v| yield u,v } }
which is calling #each_adjacent with the block:
{ |v| yield u,v }
So, for each vertex u, we iterate over each of its adjacencies, and yield the vertex and that particular adjacency to the block passed to each_adjacent which was (from way back up there):
g.adjacent_iterator do |x, b| b.call((x+1)%n) end
Stepping through our example v( x in adjacent_iterator) is the vertex (initially 0) and b is the block {|v| yield u,v } So we have b.call((0+1)%3) -> b.call(1) -> 0,1
This is yielded to each_vertex which iterates to v (x in adjacent_iterator) to 1. Which is passed into the block and b.call(2%3)=2 results in 1,2
2 is then the next vertex and is passed into b.call(3%3)=0 results in 2,0. 0 as a vertex is not iterated over because it’s already a vertex that has been interated over.
Whew, that was pretty elegant, but awfully complicated. So how to use it?
Using it is actually quite easy. Notice that we have two blocks to pass. One that identifies the vertices, the second that identifies the adjacencies to those vertices. So in #vertex_iterator you would provide a function to iterate over the vertices of interest, and in #adjacent_iterator would go a function that provided the adjacencies for the vertices of interest.
A contrived example would be to create the graph [(0-1) (1-2) (1-3) (2-4) (3-4)]
vertices=[0,1,2,3,4] children= {0=>[1], 1=>[2,3], 2=>[4], 3=>[4], 4=>[]}
Then:
RGL::ImplicitGraph.new { |g| g.vertex_iterator { |b| vertices.each(&b) } g.adjacent_iterator { |x, b| children[x].each{ |y| b.call(y)} } }
would lazily create the graph.
Now for adding custom modules
module FancyStuff def invert_vertices self.vertices.reverse end end g = RGL::ImplicitGraph.new { |g| g.vertex_iterator { |b| vertices.each(&b) } g.adjacent_iterator { |x, b| children[x].each{ |y| b.call(y)} } } g.extend FancyStuff p g.invert_vertices [4, 3, 2, 1, 0]
So all the mixins below can be kept in their own module and added as needed via normal ruby mixin approaches.
The original rake file has been converted to the jeweler format. Several of the operations in the original rake file are handled by the default by jeweler, and this change brings rgl up to date with current gem management practices. Some rake tasks have not been ported (converting to tar/zip, counting code lines,
cvs tasks) as the utility for them seems to have lessened.
Nested arrays can be used to initialize a graph
RGL::DirectedAdjacencyGraph[ [1,2], [2,3], [2,4], [4,5] ].edges_to_a.to_s #=> "(1-2)(2-3)(2-4)(4-5)"
-
Ability to alias nils in the graph. #alias_nils(nil_term = :zzznull) will replace any nils in the graph with a user provided term (default is :zzznull for alphabetical reasons)
-
overrides #hash and #eql? so that #eql? will return true if two graphs have identical set of edges.
-
provides an #in_degree method. Its a bit of a hack, as it essentially reverses the graph and then calculates #out_degree on the reversed graph. I’m fairly certain this results in a correct answer for directed graphs, but not 100% positive.
-
#roots method to find vertices with no sources (i.e., no parents or equivalently an in degree of 0)
-
#best_top_vertices method to find the vertices with the most descendants. Its vertices, not vertex because multiple vertices could be tied for the number of descendants.
-
#edge_array returns an array of edges interestingly enough
-
#source_vertices returns the parent vertices of the current vertex
-
#connected_to? determines if the current graph (self) has any vertices in common with another graph.
-
#merge will merge the current directed graph with another directed graph.
-
connected_edges? A test to determine if edges connect to each other. For Example edge [:a, :b] is connected to [:b, ;c].
-
#atomic_graphs returns an array of digraphs that are formed by the edges of the current graph (i.e. each digraph returned has two vertices and one edge). I wish I could have thought of a better name (atomic has multiple meanins)
-
#find_connected_graphs will find all connected graphs and merge them together into a common graph. Returns an array of unique graphs.
RGL is a framework for graph data structures and algorithms.
The design of the library is much influenced by the Boost Graph Library (BGL) which is written in C++ heavily using its template mechanism. Refer to www.boost.org/libs/graph/doc for further links and documentation on graph data structures and algorithms and the design rationales of BGL.
A comprehensive summary of graph terminology can be found in the the graph section of the Dictionary of Algorithms and Data Structures at www.nist.gov/dads/HTML/graph.html.
This document concentrates on the special issues of the implementation in Ruby. The main design goals directly taken from the BGL design are:
-
An interface for how the structure of a graph can be accessed using a generic interface that hides the details of the graph data structure implementation. This interface is defined by the module Graph, which should be included in concrete classes.
-
A standardized generic interface for traversing graphs (RGL::GraphIterator)
RGL provides some general purpose graph classes that conform to this interface, but they are not meant to be the only graph classes. As in BGL I believe that the main contribution of the RGL is the formulation of this interface.
The BGL graph interface and graph components are generic in the sense of the C++ Standard Template Library (STL). In Ruby other techniques are available to express the generic character of the algorithms and data structures mainly using mixins and iterators. The BGL documentation mentions three means to achieve genericity:
-
Algorithm/Data-Structure Interoperability
-
Extension through Function Objects and Visitors
-
Element Type Parameterization
-
Vertex and Edge Property Multi-Parameterization
The first is easily achieved in RGL using mixins, which of course is not as efficient than C++ templates (but much more readable :-). The second one is even more easily implemented using standard iterators with blocks or using the Stream module. The third one is no issue since Ruby is dynamically typed: Each object can be a graph vertex. There is no need for a vertex (or even edge type). In the current version of RGL properties of vertices are simply attached using hashes. At first there seems to be not much need for the graph property machinery.
The first version of RGL only contains a core set of algorithm patterns:
-
Breadth First Search (RGL::BFSIterator)
-
Depth First Search (RGL::DFSIterator)
The algorithm patterns by themselves do not compute any meaningful quantities over graphs, they are merely building blocks for constructing graph algorithms. The graph algorithms in RGL currently include:
-
Topological Sort (RGL::TopsortIterator)
-
Connected Components (RGL::Graph#each_connected_component)
-
Strongly Connected Components (RGL::Graph#strongly_connected_components)
-
Transitive Closure (RGL::Graph#transitive_closure)
RGL currently provides two graph classes that implement a generalized adjacency list and an edge list adaptor.
-
RGL::AdjacencyGraph
-
RGL::ImplicitGraph
The AdjacencyGraph class is the general purpose *swiss army knife* of graph classes. It is highly parameterized so that it can be optimized for different situations: the graph is directed or undirected, allow or disallow parallel edges, efficient access to just the out-edges, fast vertex insertion and removal at the cost of extra space overhead, etc.
The concepts of IncidenceGraph, AdjacencyGraph and VertexListGraph (see www.boost.org/libs/graph/doc/IncidenceGraph.html) are here bundled in the base graph module. Most methods of IncidenceGraph should be standard in the base module Graph. The complexity guarantees can not necessarily provided. See www.boost.org/libs/graph/doc/graph_concepts.html.
RGL is depended on the stream library which can also be downloaded from rubyforge.org/frs/?group_id=110. If you use gem to install RGL the stream library will be installed as a prerequisite.
Download the GEM file and install it with ..
% gem install rgl-VERSION.gem
or directly with
% gem install rgl
Use the correct version number for VERSION (e.g. 0.2.x). You may need root privileges to install.
RGL comes with a Rakefile which automatically runs the tests. Goto the installation directory and start rake:
% gem env
Rubygems Environment:
- VERSION: 0.9.0 (0.9.0)
- INSTALLATION DIRECTORY: /usr/lib/ruby/gems/1.8
- GEM PATH:
- /usr/lib/ruby/gems/1.8
- REMOTE SOURCES:
- http://gems.rubyforge.org
% cd /usr/lib/ruby/gems/1.8/gems/rgl-0.3.0/
% rake
(in /usr/lib/ruby/gems/1.8/gems/rgl-0.3.0)
/usr/bin/ruby1.8 -Ilib:tests "/usr/lib/ruby/gems/1.8/gems/rake-0.7.3/lib/rake/rake_test_loader.rb" "tests/TestTransitiveClosure.rb" "tests/TestComponents.rb" "tests/TestCycles.rb" "tests/TestDirectedGraph.rb" "tests/TestEdge.rb" "tests/TestGraph.rb" "tests/TestGraphXML.rb" "tests/TestImplicit.rb" "tests/TestUnDirectedGraph.rb" "tests/TestTraversal.rb" "tests/TestDot.rb" "tests/TestRdot.rb"
Loaded suite /usr/lib/ruby/gems/1.8/gems/rake-0.7.3/lib/rake/rake_test_loader
Started
......................................................................................................................................................
Finished in 0.750958 seconds.
86 tests, 625 assertions, 0 failures, 0 errors
Running rcov on the test suite generates this result.
You have to install stream library before. You can than install RGL with the following command:
% ruby install.rb
from its distribution directory. To uninstall it use
% ruby install.rb -u
irb> require 'rgl/adjacency'
irb> dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6]
# Use DOT to visualize this graph:
irb> require 'rgl/dot'
irb> dg.write_to_graphic_file('jpg')
"graph.jpg"
The result: 
irb> dg.directed? true irb> dg.vertices [5, 6, 1, 2, 3, 4] irb> dg.has_vertex? 4 true
Every object could be a vertex (there is no class Vertex), even the class object Object:
irb> dg.has_vertex? Object false irb> dg.edges.sort.to_s "(1-2)(1-6)(2-3)(2-4)(4-5)(6-4)" irb> dg.to_undirected.edges.sort.to_s "(1=2)(1=6)(2=3)(2=4)(5=4)(6=4)"
Add inverse edge (4-2) to directed graph:
irb> dg.add_edge 4,2
(4-2) == (2-4) in the undirected graph:
irb> dg.to_undirected.edges.sort.to_s "(1=2)(1=6)(2=3)(2=4)(5=4)(6=4)"
(4-2) != (2-4) in directed graphs:
irb> dg.edges.sort.to_s "(1-2)(1-6)(2-3)(2-4)(4-2)(4-5)(6-4)" irb> dg.remove_edge 4,2 true
Topological sort is realized with as iterator:
require 'rgl/topsort' irb> dg.topsort_iterator.to_a [1, 2, 3, 6, 4, 5]
A more elaborated example showing implicit graphs:
def module_graph
RGL::ImplicitGraph.new { |g| g.vertex_iterator { |b| ObjectSpace.each_object(Module, &b) } g.adjacent_iterator { |x, b| x.ancestors.each { |y| b.call(y) unless x == y || y == Kernel || y == Object } } g.directed = true }
end
This function creates a directed graph, with vertices being all loaded modules:
g = module_graph
We only want to see the ancestors of RGL::AdjacencyGraph:
tree = bfs_search_tree_from(g,RGL::AdjacencyGraph)
Now we want to visualize this component of g with DOT. We therefore create a subgraph of the original graph, using a filtered graph:
g = g.vertices_filtered_by {|v| tree.has_vertex? v}
Create the graphics with DOT:
g.write_to_graphic_file
produces module_graph.jpg: 
Look for more in the examples directory (i.e. examples.rb).
I collect some links to stuff around RGL at del.icio.us/monora/rgl. I registered RGL at SWiK.
Many thanks to Robert Feldt which also worked on a graph library (rockit.sf.net/subprojects/graphr) who pointed me to BGL and many other graph resources.
Robert kindly allowed to integrate his work on graphr, which I did not yet succeed. Especially his work to output graphs for GraphViz is much more elaborated than the minimal support in dot.rb.
Jeremy Siek one of the authors of the nice book “The Boost Graph Library (BGL)” (www.boost.org/libs/graph/doc) kindly allowed to use the BGL documentation as a cheap reference for RGL. He and Robert also gave feedback and many ideas for RGL.
Dave Thomas for RDoc which generated what you read and matz for Ruby. Dave included in the latest version of RDoc (alpha9) the module dot/dot.rb which I use instead of Roberts module to visualize graphs (see rgl/dot.rb).
Jeremy Bopp, John Carter, Sascha Doerdelmann and Shawn Garbett for contributing additions, test cases and bugfixes.
RGL is Copyright © 2002,2004,2005,2008 by Horst Duchene. It is free software, and may be redistributed under the terms specified in the README file of the Ruby distribution.
Please contact me at monora@gmail.com with bug reports suggestions, and other comments. If you send patches, it would help if they were in-line (not attachments) and generated using “diff -u”.