= GRAph Theory in Ruby (GRATR)

NOTES ON THIS FORK (https://github.com/jdleesmiller/gratr):
- This isn't an official fork.
- I just needed to fix a few things to make it work with 1.9.
- It also now works with bundler (gemspec in a separate file).
- All of the test cases that are important to me now pass. HOWEVER, there are
  still some that fail (in particular in the chromatic number calcs).
- See also this fork:
  https://github.com/bruce/graphy
  which seems to have been developed a bit more after GRATR development stopped.
END OF NOTES

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 <em>Dictionary of Algorithms and Data Structures</em> 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 <tt>require 'gratr'</tt> statement in your Ruby code. If one wishes
to pull the classes into the current namespace, i.e. drop the <tt>GRATR::</tt> from all
class statements and use <tt>require 'gratr/import'</tt> 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]] 

<em>Topological sort</em> 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
* Undirected graphs from ActiveRecord

== Release Notes

== 0.5.1

* Full rework of internals to have dual dependencies, first upon an implementation (ActiveRecord, Adjancency Lists, external libraries, ...) and secondly an algorithmic category, i.e. directed graph, undirected graph, hypergraph, etc. Now advanced algorithms are fully decoupled from implementation and algorithmic category. 
* Full integration with acts_as_graph plugin for Rails. Undirected Graphs from ActiveRecord not working yet.
* Minor bug fixes.

=== 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) 2007,2006 Shawn Patrick Garbett

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

Copyright (c) 2000,2001  Jeremy Siek, Indiana University ([email protected]) 

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