Graphs.hpp File Reference

Plans regarding installation of tools related to graph theory. More...

Go to the source code of this file.

Detailed Description

Plans regarding installation of tools related to graph theory.

General C++ graph libraries
  • Not so much happens with the Boost graph library, so we need to look out for additional or alternative libraries.
  • Goblin http://www.math.uni-augsburg.de/~fremuth/goblin.html
    1. Seems to be more or less a completed project (last update of webpages is from November 2007). Problematic that they only speak about "gcc compatibility" with versions 3.4.x --- on the other hand, it's seems to be rather basic C/C++ code, so perhaps there aren't big issues.
    2. Includes also graph layout.
    3. Focus on "network programming problems", in the context of optimisaton problems. Though very strong on matching problems etc.
  • Lemon http://lemon.cs.elte.hu/trac/lemon
    1. Perhaps this has a wider scope. Though the list of algorithms is smaller than that of Goblin. It seems to aim at a broader scope, using more general methods, but currently only basics are provided.
    2. Most recent version from January 2009.
    3. Seems to be based on the notion of a "concept", closer to generic programming, while Goblin is object-oriented (even situated between C and C++).
Graph isomorphism
  • nauty http://cs.anu.edu.au/~bdm/nauty
    1. Manual installation:
      builds/Graphs/Nauty> tar -xzf ../../../sources/Graphs/nauty22.tar.gz
      raphs/Nauty> cd nauty22
      nauty22> ./configure
      nauty22> make all
      nauty22> make checks
      looks all fine.
    2. Apparently it is a library, and the main application (providing input and output) is "dreadnaut".
    3. And there is "dreadnautB", which can handle graphs with more than 32765 vertices.
    4. And some utilities, including the "gtools".
  • saucy http://vlsicad.eecs.umich.edu/BK/SAUCY/
Graph drawing
  • Overview on open-source implementations?
  • For the hypergraph extensions see the homepage of Georg Gottlob.
Travelling salesman
Graph colouring
  • "Cliquer"
    1. http://users.tkk.fi/~pat/cliquer.html
    2. Manual: [Niskanen, Oestergard: Cliquer user's guide, version 1.0; Technical Report T48, Communications Laboratory, Helsinki University of Technology, 2003]. Included in our sources.
    3. Is open source, and ready to be installed.
Hamiltonian cycles and paths

Definition in file Graphs.hpp.