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