CPGraph

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).


References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Castaño, Fabian; Bourreau, Eric; Velasco, Nubia; Rossi, André; Sevaux, Marc: Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks (2015)
  2. Zulkoski, Edward; Ganesh, Vijay; Czarnecki, Krzysztof: MathCheck: a math assistant via a combination of computer algebra systems and SAT solvers (2015)
  3. Zampelli, Stéphane; Deville, Yves; Solnon, Christine: Solving subgraph isomorphism problems with constraint programming (2010)
  4. Viegas, Ruben Duarte; Azevedo, Francisco: Lazy constraint imposing for improving the path constraint (2009)
  5. Viegas, Ruben Duarte; Azevedo, Francisco: Lazy constraint imposing for improving the path constraint (2009)
  6. Beldiceanu, Nicolas; Flener, Pierre; Lorca, Xavier: Combining tree partitioning, precedence, and incomparability constraints (2008)
  7. Deville, Yves; Dooms, Grégoire; Zampelli, Stéphane: Combining two structured domains for modeling various graph matching problems (2008)
  8. Vismara, Philippe; Valery, Beno{^i}t: Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms (2008)
  9. Beldiceanu, Nicolas; Carlsson, Mats; Demassey, Sophie; Petit, Thierry: Global constraint catalogue: past, present and future (2007)
  10. Beldiceanu, Nicolas; Petit, Thierry; Rochart, Guillaume: Bounds of graph parameters for global constraints (2006)
  11. Dooms, Gregoire; Deville, Yves; Dupont, Pierre: CP(Graph): Introducing a graph computation domain in constraint programming (2005)