gratr19

= GRAph Theory in Ruby (GRATR)

link:../gratr.jpg 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 http://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 http://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[1,2,1,3,1,4,2,5].bfs => [1, 2, 3, 4, 5]
• Depth First Search Graph[1,2,1,3,1,4,2,5].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: link:../examples/visualize.jpg

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: link:../examples/module_graph.jpg

Look for more in the examples directory.

== Credits

Many thanks to Robert Feldt which also worked on a graph library (http://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 http://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[http://www.research.att.com/sw/tools/graphviz/download.html] 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)" (http://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[http://rdoc.sourceforge.net] 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

Copyright (c) 2006 Shawn Patrick Garbett

Copyright (c) 2002,2004,2005 by Horst Duchene

Copyright (c) 2000,2001 Jeremy Siek, Indiana University ([e-mail])

All rights reserved.

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 mailto:[e-mail] with bug reports suggestions, and other comments. If you send patches, it would help if they were generated using "diff -u".