GRAph Theory in Ruby (GRATR)

GRATR is a framework for graph data structures and algorithms.

This project is a fork of Horst Duchene’s RGL library.

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.

There are two Arc classes, GRATR::Arc and GRATR::Edge.

GRATR::Digraph and it’s pseudonym GRATR::DirectedGraph are classes that have single directed edges between vertices and loops are forbidden. GRATR::DirectedPseudoGraph allows for multiple directed edges between vertices and loops are forbidden. GRATR::DirectedMultiGraph allows for multiple directed edges between vertices and loops on vertices.

GRATR::UndirectedGraph, GRATR::UndirectedPseudoGraph and GRATR::UndirectedMultiGraph are similar but all edges are undirected.

These classes are all available with a require 'gratr' statement in your Ruby code. If one wishes to pull the classes into the current namespace, i.e. drop the GRATR:: from all class statements and use require 'gratr/import' instead.

Design principles

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 using standard Ruby block iterators.
Implementation is separated from interface, and hidden from the average user. An advanced user could also easily override the internals with a different implementation if need be.

GRATR 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 GRATR 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 Arc Property Multi-Parameterization

The first is easily achieved in GRATR 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. The third one is no issue since Ruby is dynamically typed: Each object can be a graph vertex (even nil!). There is no need for a vertex (or even edge type). A label interface is provided for end users as well. One could simply use a hash externally, but the future development of network graphs will require a weight or capacity property to be accessible.

Algorithms

This version of GRATR contains a core set of algorithm patterns:

Breadth First Search Graph.bfs => [1, 2, 3, 4, 5]
Depth First Search Graph.dfs => [1, 2, 5, 3, 4]
A* Search
Lexicographic Search
Dijkstra’s Algorithm
Floyd-Warshall
Triangulation and Comparability detection

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 GRATR currently include:

Topological Sort (topsort)
Strongly Connected Components (strong_connect)
Transitive Closure (transitive_closure)

Data Structures

GRATR currently provides one graph module that implement a generalized adjacency list and an edge list adaptor.

GRATR::AdjacencyGraph

The GRATR::Digraph class is the general purpose *swiss army knife* of graph classes, most of the other classes are just modifications to this class. It is optimized for efficient access to just the out-edges, fast vertex insertion and removal at the cost of extra space overhead, etc.

GEM Installation

Download the GEM file and install it with ..

% gem install gratr-VERSION.gem

or directly with

% gem install gratr

Use the correct version number for VERSION (e.g. 0.2.x). You may need root privileges to install.

Running tests

GRATR comes with a Rakefile which automatically runs the tests. Goto the installation directory and start rake:

% gem env
Rubygems Environment:
 - VERSION: 0.8.3 (0.8.3)
 - 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/gratr-0.2.2/
% r40> rake
 (in /usr/lib/ruby/gems/1.8/gems/gratr-0.2.2)
 ruby1.8 -Ilib:tests -e0  -rtests/TestGraphXML  -rtests/TestComponents  -rtests/TestDirectedGraph  -rtests/TestArc  -rtests/TestImplicit  -rtests/TestTransitiveClosure  -rtests/TestTraversal  -rtests/TestUnDirectedGraph
Loaded suite -e
Started
........................................................................................................
Finished in 0.736444 seconds.

40 tests, 421 assertions, 0 failures, 0 errors

Normal Installation

You have to install stream library before. You can than install GRATR with the following command:

% ruby install.rb

from its distribution directory. To uninstall it use

% ruby install.rb -u

The rdoc is useful as well:

% rake rdoc

Example irb session with GRATR

irb> require 'gratr/import'
=> true
irb> dg = Digraph[1,2, 2,3, 2,4, 4,5, 6,4, 1,6]
=> GRATR::Digraph[[2, 3], [1, 6], [2, 4], [4, 5], [1, 2], [6, 4]]

A few properties of the graph

irb> dg.directed?
=> true
irb> dg.vertex?(4)
=> true
irb> dg.edge?(2,4)
=> true
irb> dg.edge?(4,2)
=> false
irb> dg.vertices
=> [5, 6, 1, 2, 3, 4]

Every object could be a vertex (there is no class Vertex), even the class object Object:

irb> dg.vertex? Object
=> false
irb> UndirectedGraph.new(dg).edges.sort.to_s
=> "(1=2)(2=3)(2=4)(4=5)(1=6)(4=6)"

Add inverse edge (4-2) to directed graph:

irb> dg.add_edge! 4,2
=> GRATR::Digraph[[2, 3], [1, 6], [4, 2], [2, 4], [4, 5], [1, 2], [6, 4]]

(4-2) == (2-4) in the undirected graph:

irb> UndirectedGraph.new(dg).edges.sort.to_s
=> "(1=2)(2=3)(2=4)(4=5)(1=6)(4=6)"

(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
=> GRATR::Digraph[[2, 3], [1, 6], [2, 4], [4, 5], [1, 2], [6, 4]]

Topological sort is realized with as iterator:

irb> dg.topsort         
=> [1, 2, 3, 6, 4, 5]
irb> y=0; dg.topsort {|v| y+=v}; y
=> 21

  # Use DOT to visualize this graph:
  irb> require 'gratr/dot'
  irb> dg.write_to_graphic_file('jpg','visualize')
  "graph.jpg"

The result:

Here’s an example showing the module inheritance hierarchy:

module_graph=Digraph.new
ObjectSpace.each_object(Module) do |m|
  m.ancestors.each {|a| module_graph.add_edge!(m,a) if m != a} 
end

gv = module_graph.vertices.select {|v| v.to_s.match(/GRATR/)}
module_graph.induced_subgraph(gv).write_to_graphic_file('jpg','module_graph')

The result:

Look for more in the examples directory.

Credits

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. Manuel Simoni found a subtle bug in a preliminary version announced at rubygarden.com/ruby?RubyAlgorithmPackage/Graph.

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 GRATR. He and Robert also gave feedback and many ideas for GRATR.

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 gratr/dot.rb).

Horst Duchene for RGL which provided the basis for this library and his vision.

Rick Bradley who reworked the library and added many graph theoretic constructs.

Known Bugs

Some of the digraph distance algorithms need reworked to work for pseudo and multi graphs.

To Do

Primal Dual for combinatorial optimization problems
Min-Max Flow
Near optimal traveling salesman problem
Orientation of undirected graphs

Release Notes

The core interface is about to be updated to allow for cleaner dependency injects. Luke Kanies has also contributed several optimizations for speed and logged some bugs. This will result in a 0.5 release coming soon.

0.4.3

Fixed bug in dot output dependency.
Changed method.call to send in a couple places.
Fixed bug in unconnected vertices for reversal. Ticket #7237
Fixed bugs in A* Search. Ticket #7250.

0.4.2

Fixed bug in parallel edge adjacency detection.
Fix to allow symbols to be passed through to dot for labels.
Changed naming to use Arcs for Digraphs and Edges for Undirected Graphs.
Added a gem release.

0.4.1

Got reflection working for graphs
Fixed major bugs in multi and pseudo graph handling

0.4.0

Initial release of fork from RGL library.

Copying

Jeremy Siek was one of the principal developers of the Boost Graph library. Since this work is derivative, his name is included in the copyright list.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice(s),
  this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
* Neither the name of the Shawn Garbett nor the names of its contributors
  may be used to endorse or promote products derived from this software
  without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Support

Please contact me at [email protected] with bug reports suggestions, and other comments. If you send patches, it would help if they were generated using “diff -u”.