Perl extension for LEMON, a combinatorial optimization and graph library
========================================================================

LEMON (Library of Efficient Models and Optimization in Networks) is a "C++"
graph template library aimed at combinatorial optimization tasks, especially
those working with graphs and networks. See http://lemon.cs.elte.hu/ for
more details. It is efficient, flexible and open source, which calls for a
Perl interface.  "Lemon::Graph" is positioned to provide this.

The main features that are currently supported by "Lemon::Graph" are the
creation and deletion of directed graphs (limited to LEMON ListDigraphs),
adding, deleting arcs and nodes. Node and arc iterators are tied arrays,
while nodemaps and arcmaps are tied hashes.  The good news is that you can
store basically anything in these maps that can be put into Perl scalars:
integers, doubles, strings, or even objects, file handles or complete array
and hash references. "Lemon::Graph" assures that whatever you put into these
maps, all graph algorithms will automagically just work. Some of LEMON's
graph algorithms are also available, especially Dijkstra's shortest path
algorithm, the breadth-first-search and depth-first-search graph search
algorithms, the Goldberg-Tarjan maximum flow algorithm, and the
widest-shotest path (WSP) and the shortest-widest path (SWP) algorithms. More
support is on the way.

An exceptionally useful feature of LEMON is the concept of graph adaptors, a
tool for inserting special wrapper layers above LEMON graphs that, in some
way, change the structure or the behavior of the underlying graph. For
example, you can reverse the arcs of the graph (using the
"Lemon::ReverseGraph" class), filter out some of the nodes and/or arcs of a
graph to create a specific subgraph (using the "Lemon::SubGraph" class) or
even create a complete flow residual graph (by the "Lemon::ResidualGraph"
class). These adaptors are fully supported by Lemon::Graph. You can even run
the graph algorithms over these adaptors too, just like with simple graphs.

The philosophy behind the design of "Lemon::Graph" is to always make
available the original LEMON API as rigidly as possible, but to also provide
more convenient Perlish abstractions wherever plausible. This involves a full
internal reference counting based management of LEMON objects inside
Lemon::Graph.


EXAMPLE

The code below computes the diameter of a directed Erdos-Renyi random graph.

    use Lemon::Graph;
    use List::Util qw(max);

    # create a directed Erdos-Renyi random graph G(N,p)
    $N = 300;
    $p = .03;

    $g = Lemon::Graph->new;
    $g->addNode for 1..$N;

    for $i ($g->nodeList) {
        for $j ($g->nodeList) {
            $i == $j and next;
            $g->addArc($i, $j) if rand(1) <= $p;
        }
    }

    # compute the diameter
    for $i (@{ $g->nodeIt }) {
        $bfs = Lemon::Bfs->new($g);
        $bfs->run($i);
        $diameter = max($diameter,
                        max map {$bfs->dist($_)}
                            grep {$bfs->reached($_)}
                                $g->nodeList);
    }

    print "Graph diameter is $diameter\n";


INSTALLATION

To install this module type the following:

   perl Makefile.PL
   make
   make test
   make install

The distribution comes with a semi-complete list of graph adaptors
(ReverseGraph, SubGraph and ResidualGraph) and a read-only map
ResidualCapacity. The default is that all these features are compiled in,
which puts a very heavy memory and CPU burden on the compiler. If you do not
want to use some of the features because you now that you will never use
them, you can configure which features go in by setting the '$build' variable
in the 'Makefile.PL' file according to your taste. E.g., adding the
'-DUSE_REV_GRAPH_ADAPTOR' to the '$build' variable will cause the
ReverseGraph class to compile into your Lemon::Graph module and all the
algorithms over this adaptor will be instantiated and become available. Set
the '$build' variable accordingly and just type the usual

   perl Makefile.PL
   make
   make test
   make install

and enjoy!

If you need more from LEMON, you can easily add them. First, you have to add
the new adaptors to 'lemon_graph.conf', especially, the name, the constructor
and the XS bindings for your new adaptors. The syntax should be
straightforward from the existing examples in that file. Then, you have to
generate the appropriate template instantiations, constructors, and the XS
bindings. Here is how you do that:

   contrib/gen_blesser.pl

Then, as usual:

   perl Makefile.PL
   make
   make test
   make install

Note that you might need to add some wrappers in Graph.pm for the conversion
of maps to work. See the new() method of the Lemon::SubGraph class on how to
do that.


DEPENDENCIES

The only dependence of this module is the LEMON library. LEMON comes in the
form of C++ header files. To install Lemon::Graph, put the LEMON headers
anywhere, where the compiler finds them. The best fit seems to be
'/usr/local/include', but your mileage may vary. If your LEMON headers live
at an unconventional place, don't forget to set the 'INC' directive in
Makefile.PL accordingly.

Also, you will need a fairly new g++ to compile the module. This means
g++-4.3 or higher. Lemon::Graph uses heavy templating, and earlier versions
often miscompile some of the graph adaptors. However, if you do not intend to
use adaptors, any g++-3.* will work.


COPYRIGHT AND LICENSE

Copyright (c) 2005-2010, Gabor Retvari. All rights reserved.  This program is
free software; you can redistribute and/or modify it under the terms of the
GNU General Public License as published by the Free Software Foundation;
either version 2 of the License, or (at your option) any later version

Consult the LEMON documentation for copyright information on the LEMON
library.




Download Lemon::Graph

Back