Implement Algorithm of Backtracking

What is Backtracking?

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight queens on a standard chessboard so that no queen attacks any other.

Why do we use Backtraking strategy

In developing the new user GUI, we change the functionally of resolve the problem, so the problem is always resolved, even if we have not all necessary restrictions.

We would add the missing constraints necessary to obtain a plan construction, so the solver can return a problem solution.

The current Decomposition Tree

The decomposition of a graph is to find a subset of its vertices that determines a partition of the initial set to generate the corresponding induced subgraphs. If we apply the decomposition recursively for each resulting subgraph, we obtain a decomposition tree. The decomposition of a branch ends when:

  • The current graph can not be broken because there is no set of vertices valid to a decomposition. An internal node is not decomposable.
  • The decomposition of the graph is simple, then we are in a sheet.

The abstract class TreeDecompositor leads the hierarchy of graphs decompositors. Invoking the method execute(Graph G), we will begin a new decomposition in the graph. Each subclass will implement this operation by setting the following criteria:

  1. The cardinality of the subset of vertices that decompose the graph to generated the corresponding induced subgraphs. This criterion determines the number of children you have a leaf.
  2. When the decomposition is valid.
  3. When we have reached a leaf node.
  4. When a leaf is complete or incomplete.

Now the class that implements TreeDecompositor is TripletTreeDecompositor, and in it we will build on the examples and explaining how to realize the strategy of backtracking

Analyzer
eval(p)
x
x
decompositor.execute(p.graph)


DecompositionInfo decomposition(Graph g)
{

DecompositionInfo info;

List vertices = g.getVertices();

if(g.numVertices == 3) return new DecompositionInfo(vertices)

else
   info = exploreVerticesDegree2(g, vertices)
   if (info!= null) return info;
   else
      DFSTree dfstree = new DFSTree(g);
      if (dfsTree.numConnectedComponents() > 1) 
         info = exploreConnectedComponents(g,dfsTree);
         if (info!= null) return info;
      else
         if (dfsTree.numArticulationPoints() > 0) 
            info = exploreArticulationPoints(g,dfsTree);
            if (info!= null) return info;
         else
            for(int i=0;(i<dfsTree.numFundamentalCycles());i++)
              List cycle = dfsTree.getFundamentalCycle(i);
              List bridges = getBridges(g,dfsTree,cycle);
              mergeBridges(bridges);
              List faces = getFaces(cycle,bridges);
              info = exploreFaces(g,faces);
              if (info!= null) return info;

if the number of vertices is three or more:
  invoke a new graph decomposition, we get a !DecompositionInfo and we do recursive calls to subgraph decomposition.
  is the decompositionInfo is null we are in a O_DECOMPOSABLE internal node

else looking for the first vertex with degree 2

else crete a DFS tree wit the graph
    if has 2 or more connected components --> getInfo

TripletTreeDecompositor

public void execute(Graph g)

Executes a new graph decomposition.

  1. If the number of vertices is three or more then
    1. Invoke a new graph decomposition, we get a DecompositionInfo with the called to the procedure decomposition(Graph g) (implemented in PlanarFacesTreeDecompositor).
    2. If the decompositionInfo is not null then we do recursive calls.
    3. Else we are in a NO_DECOMPOSABLE internal node.
  2. Else we are in a leaf and we will check if is complete or incomplete

PlanarFacesTreeDecompositor

protected DecompositionInfo decomposition(Graph g)

Executes a new decomposition step according to the specified graph (with three or more vertices).The parameter g is a graph with three or more vertices, and return if the decomposition was successful the information about the decomposition result, null otherwise

  1. If the number of vertices is three then
    1. We create a DecompositionInfo with the graph and return it.
  2. Else
    1. If the graph has four or more vertices, explore if there is a vertex of degree 2 that performs a decomposition (DecompositionInfo exploreVerticesDegree2(Graph g, List vertices)).
      1. If the decomposition was successful the information about the decomposition result.
    2. Else we construct a DFS tree and check the graph connectivity.
      1. If the graph is 0-connected, explore its components (DecompositionInfo exploreConnectedComponents(Graph g, DFSTree dfsTree)), and if the decomposition was successful the information about the decomposition result.
      2. Else
        1. If the graph is 1-connected, explore its articulation points, and if the decomposition was successful the information about the decomposition result.
        2. Else the graph is >1-connected, explore its fundamental cycles, and if the decomposition was successful the information about the decomposition result.

How we apply backtraking in the decomposition tree?

The Analyzer can get one construction plan from the tree decomposition of the problem. Our current algorithm for automatic resolution of the not complete problem, we try to complete with the suggestions of the Analyzer, but sometimes the suggestions is bad, for example, when the Analyzer has a unique suggestion and this is angle between two parallel lines (restriction that we can not resolve).

Our idea is to implement a strategy of backtracking, so if we can not build our problem because the Analyzer indicates incorrect suggestions, we will can obtain a news decomposition trees different and therefore news constructions plans.

Attachments