Homepage of CP(Graph), CP(Map) and related software
CP(Graph) - Graph variables for constraint programming
CP(Graph) 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.
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 :
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.
Building from sources
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
Authors and contact
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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
Copyright and license
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:
Copyright (c) 2005, Grégoire Dooms and Stéphane Zampelli ( Université catholique de Louvain )
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
Neither the name of the Université catholique de Louvain nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.