The New User Solver

This web is incomplete. We are working on it!'''''

The Current Solver

The function of the current Solver is divided into three stages: the analyzer, the selector and the constructor. Each stage has a different target to construct from a problem and some assignations, a possible correct solution.

Each stage is implemented in a different Java class, and class Solver incorporates a private instance of each, in his collection of attributes.

The most important function that the Solver class implement is resolve(), that with a problem and some assignations returns a data structure if it has been possible to construct a solution.

Normally, the parameters that the function resolve() receive are: a SelectorInput, a Problem and some assignations. The schema of this function is simple and explained below with a block diagram:

The Analyzer catch the problem and try to create a construction plan and an information structure of the tree decomposition of the problem.

With the construction plan obtained previously and the SelectorInput, the Selector generates a IndexAssig, to the new solution.

Now the constructor catch the ParametersAssigs, the construction plan and the IndexAssig, and will create the structure of the solution.

The New Solver

The new Solver function is a little bit different now. The new solver can always find a solution to the problem, without to have all the necessary constraints. So we always try that the Analyzer can build a construction plan, since the problem created by the user, and a complete set of !parametersAssig. We can see in the following diagram the small change that incorporates the function:

AddExtraConstraints is the function that complete the problem, adding the necessaries constraints. When the Analayzer can not build the construction plan, returns a decomposition tree of the problem, we can travel it and see where are the erroneous nodes and that kind are, no decomposable or incomplete. Since that is where our new function will add new restrictions to the problem until that the Analyzer can decompose it completely and can create a construction plan.

Our new feature addExtraConstraints() first obtains a list of nodes no decomposable, as these nodes create a conflict. One way to break this conflict is to choose any point and add the distances constraints to the rest of the lines.

When we ensure that there is no longer any conflict, we get the incomplete nodes and we add a constraint on node type:

  • If the node are two points, add distance between two points.
  • If the node are two lines, add angle between lines (if these are not parallel).
  • If the node is a point and a line, add the distance between point and line.

The algorithm that is used for this functionality is written in simplified form below:

function boolean AddExtraConstraints(TreeDecompositor tree){
   List incompleteNodes = new List();
   List noDecomposablesNodes = new List();
   
   getIncompletsNodesAndNoDecomposableNodes(tree.getRoot(), incompleteNodes, noDecomposablesNodes);

   while (exists(noDecomposablesNodes)){
      tree = repairConflictiveSets();
      List incompletsNodes = new List();
      List noDecomposablesNodes = new List();
      getIncompletsNodesAndNoDecomposableNodes(tree.getRoot(), incompleteNodes, noDecomposablesNodes);
   }

   while (exists(incompleteNodes)){
      TDNode node = incompleteNodes.getNextNode();
      List vertexs = node.getGraph().getVertexs();
      if(exists(vertexs)){
         if(vertexs == {Point, Point}) addExtraConstraint(vertexs.getPoint1(),vertexs.getPoint2());
         else if(vertexs == {Line, Line}) addExtraConstraint(vertexs.getLine1(),vertexs.getLine2());
         else if(vertexs == {Line,Point}) addExtraConstraint(vertexs.getLine1(),vertexs.getPoint2());
      }
   }
}

The getIncompletsNodesAndNoDecomposableNodes is the function that goes in search of nodes no decomposable or incomplete.

The repairConflictiveSets is the function that break all conflictive sets found, as explained above.

The addExtraConstraint is the function that add the correct constraint in the new ParametersAssigs List, and updating a new complete problem.

We can see an example of how works the new algorithm, using the old solver:

  1. We built the next problem and we see that exists a conflictive set:
  2. The new algorithm will choose a random point and add the distances with the lines of the conflictive set, and we transform the conflictive set in the incomplete nodes, where the Analyzer gives us his suggestions:
  3. Finally we add the restrictions depending on the suggerencia, and you have the problem resolved!

Attachments