4.3.3. Using the database of invariants

The purpose of this section is to provide a set of graph invariants, each invariant relating a given set of graph parameters. Once we have these graph invariants we can use them systematically by applying the following steps:

  • For a given graph constraint we extract all the graph parameters occurring in its description. This can be done automatically by scanning the corresponding graph properties. Let 𝒒𝒫 denote this subset of graph parameters. For each graph parameter 𝑔𝑝 of 𝒒𝒫 we check if we have a graph property of the form 𝑔𝑝=π‘£π‘Žπ‘Ÿ where π‘£π‘Žπ‘Ÿ is a domain variable. If this is the case we record the pair (𝑔𝑝,π‘£π‘Žπ‘Ÿ); if not, we create a new domain variable π‘£π‘Žπ‘Ÿ and also record the pair (𝑔𝑝,π‘£π‘Žπ‘Ÿ).

  • We then search for all groups of graph invariants involving a subset of the previous graph parameters 𝒒𝒫. For each selected group we filter out those graph invariants for which the preconditions are not compatible with the graph class of the graph constraint under consideration. In each group we finally keep those invariants that have the maximum number of preconditions (i.e., the most specialised graph invariants).

  • Finally we state all the previous collected graph invariants as implied constraints. This is achieved by using the variables associated with each graph parameter.

EXAMPLE: We continue with the example of the πšπš›πš˜πšžπš™ constraint and its first graph constraint. The steps for creating the implied constraints are: