From: "Horst Duchêne" <duchene@...>
Date: 2002-02-20T10:18:09+09:00
Subject: [ANN] RGL (Ruby Graph Library) 0.1

Hello,

I have prepared the first public release of RGL.  This
release, V0.1, is alpha fairly rudimentary in what it does.  Troubleshooting
reports and comments are very welcome.

The RAA Entry: http://www.ruby-lang.org/en/raa-list.rhtml?name=RGL

-- Horst

Here are the first lines of the README:

= Ruby Graph Library (RGL)

RGL is a framework for graph datastructures 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
http://www.boost.org/libs/graph/doc for further links and documentation on
graph
datastructures and algorithms and the design rationals of BGL.

== 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
(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 datastructures 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 implementated using standard iterators with blocks or using the
Stream modul. The third one is no issue since Ruby is dynamicly 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
machinary.
.....