2.3.2.4. Graph properties
We represent a global constraint as the search of a subgraph (i.e., a final graph) of a known initial graph, so that this final graph satisfies a given set of graph properties and possibly belongs to a specific graph class. Most graph properties have the form or the form , where is a graph parameterΒ [Berge70],Β [GondranMinoux84], is one of the comparison operators , , , , , , and , , are expressions that can be evaluated to an integer. Before defining each graph parameter, let's first introduce some basic vocabulary on graphs.
Graph terminology and notations
A digraph is a pair where is a finite set, called the set of vertices, and where is a set of ordered pairs of vertices, called the set of arcs. The arc, path, circuit and strongly connected component of a graph correspond to oriented concepts, while the edge, chain, cycle and connected component are non-oriented concepts. However, as reported inΒ [Berge70] an undirected graph can be seen as a digraph where to each edge we associate the corresponding two arcs. PartsΒ (A) andΒ (B) of FigureΒ 2.3.5 respectively illustrate the terms for undirected graphs and digraphs.
Figure 2.3.5. Graph terminology for an undirected graph and a digraph (similar concepts are outlined with the same colour)
We say that is a successor of if there exists an arc that starts from and ends at . In the same way, we say that is a predecessor of if there exists an arc that starts from and ends at .
A vertex of that does not have any predecessor is called a source. A vertex of that does not have any successor is called a sink.
A sequence of edges of such that each edge has a common vertex with the previous edge, and the other vertex common to the next edge is called a chain of length . A chain where all vertices are distinct is called an elementary chain. Each equivalence class of the relation β is equal to or there exists a chain between and β is a connected component of the graph .
A sequence of arcs of such that, for each arc the end of is equal to the start of the arc , is called a path of length . A path where all vertices are distinct is called an elementary path. Each equivalence class of the relation β is equal to or there exists a path between and β is a strongly connected component of the graph .
A chain of is called a cycle if the same edge does not occur more than once in the chain and if the two extremities of the chain coincide. A cycle of is called a circuit if for each edge , the end of is equal to the start of the edge .
Given a graph , we define the reduced graph of as follows: to each strongly connected component of corresponds a vertex of ; to each arc of that connects different strongly connected components corresponds an arc in (multiple arcs between the same pair of vertices are merged).
The rank function associated with the vertices of a graph that does not contain any circuit is defined in the following way:
The rank of the vertices that do not have any predecessor (i.e., the sources) is equal to 0,
The rank of a vertex that is not a source is the length of longest path such that the start of the arc is a source and the end of arc is the vertex .
We now present the different notations used in the catalogue:
corresponds to for any positive integer.
Given a set , is the number of its elements.
Given two sets and , denotes the union of the two sets when they are disjoint.
Given a digraph and , and .
Given a digraph and a subset of , the sub-digraph of induced by is the digraph where and . By aim of simplicity, we denote by . Moreover, if , we use instead of .
Given two digraph and such that , denotes the graph whose vertices set is and whose arcs set is .
Given a graph parameter , a digraph and an integer , is the number of connected components (respectively strongly connected components) of with cardinal .
Given a graph parameter, for instance the number of connected components, will denote the number of connected components of the initial graph (i.e., the graph induced by the constraint under consideration), will denote the number of connected components of the final graph (i.e., a subgraph of the initial graph). The use of will denote the number of connected components of the digraph .
Given a global constraint , and a graph parameter used in the description of , (respectively ) denotes a lower bound (respectively upper bound) of among all possible final graphs compatible with the current status of .
Graph parameters
We list in alphabetic order the different graph parameters we consider for a final graph associated with a global constraint and give an example of constraint where they are used:
: largest distance between sources and sinks in the reduced graph associated with (adjacent vertices are at a distance of 1).
: number of predecessors of the vertex of that has the maximum number of predecessors without counting an arc from a vertex to itself.
: number of vertices of the largest connected component of .
: number of vertices of the largest strongly connected component of .
: number of successors of the vertex of that has the maximum number of successors without counting an arc from a vertex to itself.
: smallest distance between sources and sinks in the reduced graph associated with (adjacent vertices are at a distance of 1).
: number of predecessors of the vertex of that has the minimum number of predecessors without counting an arc from a vertex to itself.
: number of vertices of the smallest connected component of .
: number of vertices of the smallest strongly connected component of .
EXAMPLE: The constraint forces covering a digraph with one circuit visiting once all its vertices. The graph-property forces that the smallest strongly connected component of contain vertices. Since also corresponds to the number of vertices of the initial graph this means that is a strongly connected component involving all the vertices. This is clearly a necessary conditionOf course, this is not enough, and the description of the constraint asks for some other properties. for having a circuit visiting once all vertices.
: number of successors of the vertex of that has the minimum number of successors without counting an arc from a vertex to itself.
: cardinality of the set .
EXAMPLE: The constraint forces that each variable of the collection take a value that is distinct from all the values assigned to the variables of the collection .
This is imposed by creating an arc from each variable of to each variable of . To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. Finally, the graph property forces to be empty so that no value is both assigned to a variable of as well as to a variable of .
: cardinality of the set without considering the arcs linking the same vertex (i.e., a loop).
: number of connected components of .
: number of strongly connected components of .
: number of vertices of that do not have any successor.
EXAMPLE: The forces that the variables of the collection correspond to the variables of the collection according to a permutation.
We first create an arc from each variable of to each variable of . To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. We use the graph-property in order to express the fact that each value assigned to a variable of should also be assigned to a variable of .
: sum over the different connected components of of the minimum of the number of sinks and the number of sources of a connected component.
EXAMPLE: The constraint forces to be the minimum number of values to change in the and the collections of variablesBoth collections have the same number of variables., so that the variables of correspond to the variables of according to a permutation.
A connected component of the final graph corresponds to all variables that are assigned to the same value : the sources and the sinks of respectively correspond to the variables of and to the variables of that are assigned to . For a connected component, the minimum of the number of sources and sinks expresses the number of variables for which we do not need to make any change. Therefore we use the graph-property for encoding the meaning of the constraint.
: number of vertices of that do not have any predecessor.
EXAMPLE: The forces that the variables of the collection correspond to the variables of the collection according to a permutation.
We first create an arc from each variable of to each variable of . To each arc corresponds an equality constraint involving the variables associated with the extremities of the arc. We use the graph-property in order to express the fact that each value assigned to a variable of should also be assigned to a variable of .
: number of vertices of that do not belong to any circuit and for which at least one successor belongs to a circuit. Such vertices can be interpreted as root nodes of a tree.
: cardinality of the set .
EXAMPLE: The constraint considers a digraph with vertices described by the collection. It forces that the subset of kept vertices of cardinality and their corresponding arcs form a graph without a circuit. It uses the graph-property for enforcing that the final graph contain the required number of vertices.
: difference between the largest distance between sources and sinks in the reduced graph associated with and the smallest distance between sources and sinks in the reduced graph associated with .
: difference between the number of vertices of the largest connected component of and the number of vertices of the smallest connected component of .
: difference between the number of vertices of the largest strongly connected component of and the number of vertices of the smallest strongly connected component of .
EXAMPLE: The constraint forces to be equal to the difference between the number of occurrences of the value that occurs the most and the value that occurs the least within the collection of variables . Each strongly connected component of corresponds to the variables that are assigned to the same value. The graph property allows for expressing this definition.
is an integer or an argument of type integer of the global constraint,
is an integer,
is an attribute corresponding to an integer or to a domain variable that occurs in all the collections that were used for generating the vertices of the initial graph.
We explain what is the value associated with . Let denote the vertices of rank of from which we remove any loops.
When is not empty, it corresponds to the values of attribute of the items associated with the vertices of ,
Otherwise, when is empty, it corresponds to the default value .
-
is an attribute corresponding to an integer that occurs in all the collections that were used for generating the vertices of the initial graph,
is an integer or an argument of type integer of the global constraint,
is an integer or an argument of type integer of the global constraint.
Let (respectively ) denote the vertices of such that is equal to (respectively ). is equal to 1 if there exists a path between each vertex of and each vertex of , and 0 if there exists no path between a vertex of and a vertex of .
-
is an attribute corresponding to an integer that occurs in all the collections that were used for generating the vertices of the initial graph,
is an attribute corresponding to an integer or to a set of integers that occurs in all the collections that were used for generating the vertices of the initial graph,
is an attribute corresponding to an integer or to a set of integers that occurs in all the collections that were used for generating the vertices of the initial graph,
For each vertex of let:
the set of vertices for which the value of the attribute is equal to the attribute (or is included within the attribute when it corresponds to a set of integers).
the set of vertices for which the value of the attribute is equal to the attribute (or is included within the attribute when it corresponds to a set of integers).
is equal to
1 if for each vertex of there exists a path between each vertex of and each vertex of .
0 if for a vertex of there is no path between a vertex of and a vertex of .
-
is a collection that was used for generating the vertices of the initial graph,
is an attribute corresponding to an integer or to a domain variable of the collection .
Let be the set of vertices of that were generated from the items of the collection .
If is not empty, corresponds to the product of the values of attribute associated with the vertices of ,
Otherwise, if is empty, is equal to 1.
EXAMPLE: The constraint forces the product of the variables of the collection to be equal, less than or equal, ... to a given domain variable .
To each variable of corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the arc generator together with the arc constraint. Finally, expresses the required condition. In this expression and respectively corresponds to the attribute of the collection (a domain variable) and to the condition we want to enforce. Since the final graph contains all the vertices of the initial graph, the expression corresponds to the product of the variables of the collection.
is a collection that was used for generating the vertices of the initial graph,
is an attribute corresponding to an integer or to a domain variable of the collection .
Let be the set of vertices of that were generated from the items of the collection .
If is not empty, corresponds to the difference between the maximum and the minimum values of attribute associated with the vertices of ,
Otherwise, if is empty, is equal to 0.
EXAMPLE: The constraint forces the difference between the maximum value and the minimum value of the variables of the collection to be equal, less than or equal, ... to a given domain variable .
To each variable of corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the arc generator together with the arc constraint. Finally, expresses the required condition. In this expression and respectively corresponds to the attribute of the collection (a domain variable) and to the condition we want to enforce. Since the final graph contains all the vertices of the initial graph, the expression corresponds to the difference between the maximum value and the minimum value of the variables of the collection.
is a collection that was used for generating the vertices of the initial graph,
is an attribute corresponding to an integer or to a domain variable of the collection .
Let be the set of vertices of that were generated from the items of the collection .
If is not empty, corresponds to the sum of the values of attribute associated with the vertices of ,
Otherwise, if is empty, is equal to 0.
EXAMPLE: The constraint forces the sum of the variables of the collection to be equal, less than or equal, ... to a given domain variable .
To each variable of corresponds a vertex of the initial graph. Since we want to keep all the vertices of the initial graph we use the arc generator together with the arc constraint. Finally, expresses the required condition. In this expression and respectively correspond to the attribute of the collection (a domain variable) and to the condition we want to enforce. Since the final graph contains all the vertices of the initial graph, the expression corresponds to the sum of the variables of the collection.
is an arithmetic expression. For each arc of , let denote the value of . is equal to . The value of usually depends on the attributes of the items located at the extremities of an arc.
EXAMPLE: The constraint forces that each value be assigned to exactly variables of the collection. In addition the of an assignment is equal to the sum of the elementary costs associated with the fact that we assign the variable of the collection to the value of the collection. These elementary costs are given by the collection.
The graph-property expresses that the variable is equal to the sum of the elementary costs associated with each variable-value assignment. All these elementary costs are recorded in the collection. More precisely, the cost is recorded in the attribute of the entry of the collection.
A last graph parameter, , is computed on two final graphs and that have the same set of vertices and the sets and of arcs. This graph parameter is the cardinality of the set . This corresponds to the number of arcs that belong to but not to , plus the number of arcs that are in but not in .
Graph class
For a given global constraint, a graph class specifies a general property that holds on its final digraph. We list the different graph classes and, for each of them, we point to some global constraints that fit in that class. Finding all the global constraints corresponding to a given graph class can be done by looking into the list of keywords (see SectionΒ 3.7 on page 3.7).
: the final graph does not have any circuit.
: the final graph is bipartite.
: denotes that the graph constraint of a global constraint uses only the and the arc generators and that the final graph does not contain consecutive vertices that have a loop and that are not connected together by an arc.
: the final graph is reflexive, symmetric and transitive.
: the final graph does not have any loop.
: the vertices of the initial graph belong to the final graph and all vertices of the final graph have exactly one successor.
: the final graph is symmetric. A digraph is symmetric if and only if, if there is an arc from a vertex to a vertex , there is also an arc from to .