Homepage of CP(Graph), CP(Map) and related software

CP(Graph) - Graph variables for constraint programming

CP(Graph)[1] defines a new computation domain in constraint programming : graph domain variables and constraints over these variables. A reference implementation of graph variables and constraints is released as a contribution package of the generic constraint development environment Gecode.

The purpose of this release is to bring to the constraint community an open and reusable framework suitable for the design and implementation of graph property constraints and graph-based constraint models.

The current version of the software is a first step towards a complete graph variables framework. It should be considered beta software. The graph variables are currently implemented with set variables using the "view" concept of Gecode. One view implements a graph as a set of nodes and a set of arcs, the other view uses a set of nodes and N sets of adjacent nodes. Some constraints are also provided. The current constraints are Complement(G1,G2), Path(G,n1,n2) and Path(G,n1,n2,I,w) (see below). Constraints of monomorphism using graph variables and map variables are also provided in an other contribution (see below).

A few tests/examples are provided and can serve as a model for future work see the examples section of the documentation.

Ongoing and future work include:

• The design of a dedicated datastructure implementing the graph domains.
• The design of several new graph propagators.
• The benchmarking and comparison of the choices involved in these designs.

The next release is under construction. It should be out during Summer 2006. It will include the preceding items of future work.

CP(Map) - Map variable for constraint programming

CP(Map) introduces function variables directly in a CP language. CP(Map) allows map variables as well as map constraints. We provide a package for the Gecode constraint programming library including a map variable implementation and basic constraints.

Constrained Path Finding

The first global graph propagators in CP(Graph) are propagators for the "simple path" constraint. Two versions are available: a "straight" global path constraint and an optimization constraint

• Path(G,n1,n2) holds if G is a simple path from n1 to n2.
• Path(G,n1,n2,I,w) holds if G is a simple path from n1 to n2 which total weight is I under the weight function w. This is a simplified version of the constraint using the upper bound of I to prune the upper bound of G.

The latter is called an optimization constraint because it is best suited to be used together with branch and bound in constrained shortest path problems. Such constraints can be used in constrained path finding problems such as transportation, routing, network design, ...

Constrained Graph Matching

Graph matching is a central application in many fields. We propose graph matching global constraints able to handle :

1. Graph isomorphism
2. Subgraph matching (isomorphism and monomorphism)
3. Maximum common subgraph matching
4. Approximate graph matching

Those global constraints find a map variable M between two graph variables P and T. Additional constraints can be posted either on M, P or T. We provide an implementation of those global constraints for the Gecode constraint programming library.

• CP(Graph) documentation
• CP(Map) documentation

Anonymous svn access

The source code is distribued in the Gecode source package, which can be downloaded via anonymous access to the Gecode subversion repository at the following URL : https://svn.gecode.org/svn/trunk/gecode

To get started, simply check out the current revision of Gecode using the command

svn --username anonymous checkout https://svn.gecode.org/svn/gecode/tags/release-1.0.0

Use anonymous as the login and your email address as the password.

If it does not work, check the instructions provided by Gecode.

To learn more about subversion, please consult the subversion homepage or have a look at the online version of the book Version Control with Subversion.

Once you have a fresh download of the Gecode source code, you will be able to find the sources for this software in the subdirectories contribs/graph and contribs/map.

The installation instructions are provided in the README file of these directories. For those which don't read manuals: You need the Boost Graph Library, autoconf and make.

apt-get install autoconf make g++-4.0 libboost-graph-dev
make -f Makefile.contribs
./configure 
make 
make install

The authors of this work are Grégoire Dooms, Stéphane Zampelli, Yves Deville and Pierre Dupont. For questions / comments about the software please contact the software authors:

• Grégoire Dooms < dooms at info dot ucl dot ac dot be >
• Stéphane Zampelli < sz at info dot ucl dot ac dot be >

This release dates from Nov. 2005. A second release should be available during Summer 2006. It includes "true" graph variables and new constraints. If you plan on using the framework, don't hesitate to contact the authors for further information or a pre-release of the next version.

[1] G. Dooms, Y. Deville and P. Dupont, CP(Graph): Introducing a Graph Computation Domain in Constraint Programming, Lecture Notes in Computer Science, No. 3709, Springer-Verlag, 11th International Conference on Principles and Practice of Constraint Programming, Sitges, Barcelona, Spain, pp. 211-225, 2005.

[2] Y. Deville, G. Dooms, S. Zampelli and P. Dupont, CP(Graph+Map) for Approximate Graph Matching, 1st International Workshop on Constraint Programming Beyond Finite Integer Domains, Sitges (Barcelona), Spain, October 1, pp. 31-47, 2005.

[3] G. Dooms, Y. Deville and P. Dupont, Constrained Path Finding in Biochemical Networks: a Constraint Programming Approach, 5th Open Days in Biology, Computer Science and Mathematics (JOBIM), Montreal, Canada, JO-40, 2004.

[4] S. Zampelli, Y. Deville and P. Dupont, Declarative Approximate Graph Matching Using a Constraint Approach, Second International Workshop on Constraint Propagation and Implementation, Sitges (Barcelona), Spain, October 1, Vol. 1, pp. 109-124, 2005.

[5] S. Zampelli, Y. Deville and P. Dupont, Approximate Constrained Subgraph Matching, Lecture Notes in Computer Science, No. 3709, Springer-Verlag, 11th International Conference on Principles and Practice of Constraint Programming, Sitges, Barcelona, Spain, pp. 832-836, 2005.

[6] G. Dooms, Y. Deville, P. Dupont, Constrained metabolic network analysis: discovering pathways using CP(Graph), Workshop on Constraint Based Methods for Bioinformatics, Sitges (Barcelona), Spain, October 5, pp. 29-35, 2005.

[7] G. Dooms, Y. Deville and P. Dupont, A Mozart implementation of CP(BioNet), Lecture Notes in Artficial Intelligence, No. 3389, Springer-Verlag, 2nd International Mozart/Oz Conference, pp. 237-250, 2005.

[8] G. Dooms, Y. Deville and P. Dupont, Recherche de chemins contraints dans les réseaux biochimiques, Treizièmes Journées Francophones de Programmation en Logique et de Programmation par Contraintes (JFPLC), Angers, France, pp. 109-128, June 2004.

This software is Copyright Grégoire Dooms, 2005 (UCLouvain) for the graph part and Copyright Stéphane Zampelli, 2005 (UCLouvain) for the map and graph matching part.

This software is released under the BSD license: