DragonBreath
An Optimization Engine based on Constraint Programming and Local Search


[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Internal Structure]

  [General Approach]   [Docking Graph]   [Test Graph]   [Graph Repair]


Test Graph

The test graphs check whether a given CSP graph fulfills the structural constraints or not. With the docking graphs we can find structural constraint instances. These represent the places in the CSP graph where the docking graph could be found.

The docking graph can be seen as the precondition of an implication:

DockingGraph => TestGraph1 ^ TestGraph2 ^ TestGraph3

We now have to check wheter the test graphs can also be found. Again we need to find an subgraph isomorphism. From the test graph to the CSP graph.

In the end we do not only want to find out which structural constraints are fulfilled, but also repair the wrong ones in order to solve the SCSP. As the repair is about fulfilling the test graphs they should be included in the decision of how to repair the graph.

Structural Error
Finding a Test Graph
Customizing the Matching
    Test Graph Parts that are Connected to Docking Graph
    Test Graph Parts that are not Connected
    Combining the Parts
    Finding Partial Matches
    Unconnected Parts
    Broken Graphs

Structural Error

As described in the general section the correct CSP graph should be found via a local search. The local changes should be done by a gradient descent algorithm. Therefore we need a greedy criteria. That means a criteria that can help as a kind of guide through the local search. We are searching for a series of structural changes of the graph that leads in the end to a structurally correct CSP graph. The greedy criteria should be able to differenciate between more or less correct graphs.

If a constraint instance has errors depends on whether one of the test graphs could be found or not. The easiest way of implementing a structural error function is by assigning 0 to a correct and 1 to an erroneous graph. But that would render all changes that improve the CSP graph, but not completely, invisible to the greedy criteria. Therefore we need a more differenciated measure. The similarity of the test graph and parts of the CSP graph should be expressed with a number.

The measure we use a metric that is similar to the Zelinka distance measure for graphs.

dZelinka(G1, G2) = max(|V1|, |V2|) - |VU|

With two graphs Gi = (Vi, Ei); i = 1, 2 with the vertices Vi and the edges Ei. The graph GU = (VU, EU) is the biggest common subgraph of the two.

But the Zelinka distance will only in very rare cases reach zero, as the CSP graph is normally a lot bigger then any test graph. So a bigger Zelinka distance does not allways imply a smaller error of the CSP graph.

But with a little change the metric can be used. We use instead of max(|V1|, |V2|) allways the size of the test graph. Then the error is zero as soon as found subgraph is identical with the test graph. Additionally the error can at most be as big as the test graph.

As not only missing nodes but also missing edges create an error of the test graph we change the formular to:

d(GTG, GCSP) =def |VTG| + |ETG| - ( VU| + EU| )

Finally the errors introduced by NACs (there are no test graph PACs) have to be registered. If NACs can be found the error should increase. But the test graph match is allready valid if one single node or edge of the NAC is missing. Therefore we can use the binary error measure from before.

ENAC =def { 1, not found
0, found

Together the structural error is:

EStruct =def d(GTG, GCSP) + ENAC

To realize this error function it is not sufficient to simply test whether a test graph can be found or not. The biggest common subgraph of the test graph and the CSP graph also has to be found.

Finding a Test Graph

The problem of finding a test graph is similar to the one of finding the docking grpah. But during the search for a test graph we have to be able to distinguish between different degrees of matches.

The algorithm from the docking graph uses the feature that contiguous graphs can easily be found. But a partial match of a tests graph can consist of two not connected parts. In the next figure such a case can be seen.

testGraph Broken

So the existing algorithm is at the first look not suitable to find partial matches. We could use an existing algorithm for subgraph isomorphisms which would also find partial matches.

But that would not lead to a correct solution either. Because for a complete subgraph matching algorithm a node can participate in a match if the node's attributes are correct. But the meaning of a node to the graph depends on it's adjacency. In the next figure the biggest match found has three nodes, but the sum constraint is found in two incompatible contextes. So the found solution does not reflect a correct solution either.

A real solution for this problem does not exist, as every constraint and every variable would have to be fixed in their meaning before the search starts. And that is just what we want to do with structural constraints.

Due to these insecurities at matching we have to accept a certain divergency at the computation of the structural error. Structural constraints have to be created in such a way that they can resolve these ambiguities.

The existing matching algorithm only finds contiguous graph parts. So it is not able to allways find the biggest match possible, but as the found match is contiguous the nodes are rather in the right context then not. And by constraining the searched matches to contiguous ones the number of possible matches is much much smaller then in the general case. And that leads to a speed up in the search process, which we can use to better fulfill the performance requirement.

For the given reasons we change the existing algorithm instead of using a new approach to the isomorphism problem.

Customizing the Matching

As the algorithm from the docking graph is reused the general idea is the same. Starting with one node-interpretation pair a contiguous match is searched. The whole test graph is then created by combining the found parts.

In the following sections the crucial differences and the resulting changes be are beeing described.

Test Graph Parts that are Connected to Docking Graph

The first difference is that test graphs often share interpretations with the docking graph. In the following figure the node :1 is shared by both, the docking and the test graph. The parts that share a node with the docking graph do not allways have to be searched, as their position is known.

Shared Nodes

Two nodes have to be guaranteed to have the same interpretation. At the places the docking graph was sliced into contiguous graphparts, there was the same situation. We can use the same mechanism to implement the links between the test and the docking graph.

But when the test graph is searched, that is done with general test graph data, stored in the structural constraint type. That is done for not having to douplicate the test graphs for each new instance. And once a correct match is found a copy of the match is stored with the instance.

So the links between the test graphs and the docking graph have to be between the special docking graph of the instance and the general testgraphs. Only the special docking graph instances contain the match for the constraint instance. But we do not allways want to change the links in the test graphs to the actual docking graph instance.

To solve this problem the links in the test graphs go to the docking graph of the constraint type. And the interpretation of the instance docking graph is copied to the type docking graph before test graph search starts. But of course not all the interpretations of the instance docking graph have to be copied. That would cost much too much time. We only need to copy the intepretations that are linked from a test graph. That is exactly what a GraphPartFrame does. So we store with each constraint instance a GraphPartFrames of the graph parts of the type docking graph.

Test Graph Parts that are not Connected

There are also parts of test graphs that are not connnected to the docking graph. For these we have to search for matches with each CSP graph change, as for docking graph parts. But when we find such a match, nothing follows, as the matches are only used, when a new instance has to be checked for a correct test graph, or an existing instance got it's test graph destroyed. This general search for test graph parts is done by the constraint type, as the matches can be used by all instances.

The two types of mainParts of the test graph are reflected in the class structure. And all the mainParts are stored together in a MovableSubgraph so they can be freely arranged to fit.

testGraph Classes

Combining the Parts

As described before the testgraphs can be moved freely to find the one necessary match.

For the ACs we could use both ways of finding a valid interpretation, the fast way and the complete search. But if a test graph has a NAC only the complete search is possible, we have to try each possible combination of the graph part matches until we find one that does not result in a match of the NAC. So if there is a NAC the complete search via backtracking is used.

Finding Partial Matches

It is not only importend if, but also to what extent a structural constraint is satisfied. What parts of the docking graph matching algorithm have to be changed to comply with this requirement? The search for complete parts as described before is doing backtracking if the actual assignment can not lead to a match, or a match was found allready. For test graphs we have to store the actual partial match and it's size before each backtracking. In case we don't find any match we can use the biggest stored partial match to classify the structural error.

For this functionallity there is a special function, boolean StructuralConstraintGraphParts.findBiggestEmbedding() which returns the biggest embedding that can be found. If it returns true a complete embedding could be found and findNextEmbedding() can be used. To realize the partial search the way SCNodes compute their environment has to be changed. So there are new functions SCNode.setInterpretationBiggestEmbedding() and SCNode.getAdjacencyBiggestEmbedding() too.

Unconnected Parts

For unconnected parts of a docking graph the positions were only saved if a match was found. But for test graphs we also want to find partial matchse. Therefore we do not only save the positions of complete matches, but also of partial matches.

At first sight only one, the biggest, match would be sufficient, as it could be used for all test graphs. But that one saved match could be deleted or overlapping with other parts of the test graph. So we need not only one partial match but several. But we do not want to save all of them, as that could be much too many. So only the biggest x are saved. For the size of x the number of nodes of the graph part is taken.

Broken Graphs

Broken graphs pose a problem. In the figure above such a situation can be seen. The biggest contiguous match that can be found with the developed algorithm has two nodes. The biggest existing submatch has only one missing edge.

In such a case our algorithm will not find a correct solution! We accepted this type of error to be able to find matches faster.


[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Internal Structure]

  [General Approach]   [Docking Graph]   [Test Graph]   [Graph Repair]



For questions, comments or suggestions, please visit our feedback forum.

Last update:
August 21, 2002 by Alexander Nareyek