With the new approach implemented we can now lift our restriction on the input domain size. Effectively there is no need for constraining the grid domain when the algorithm works on the edges instead of grid input combinations.
The original implementation converted vertices and edges into integer representations (using index = y*size + x), but this approach is no longer applicable when the input domain is unbounded. The first step in fixing this is to refactor the model to store vertices and edges as structs instead:
public struct VertexData
{
public int x, y;
public VertexData(int x, int y)
{
this.x = x;
this.y = y;
}
}
public struct EdgeData
{
public VertexData v1, v2;
public EdgeData(VertexData from, VertexData to)
{
this.v1 = from;
this.v2 = to;
}
}
A SetContainer can take a struct, such that our definition of active vertices in the model changes to:
static SetContainer<VertexData> vertices = new SetContainer<VertexData>();
Because structs are simple data structures instead of object the SetContainer will correctly identify permutations of the same sequence as being equivalent, whereas had we used the Vertex class directly, the SetContainer would be storing object references instead of the object data and sequence would matter.
This trick works in general, if you want to use objects in your immutable containers then wrap the data of the class into a struct and store that in the containers, then you can easily reconstruct your object from the stored data by overwriting the objects internal data variable in a constructor. Here is my implementation of a Vertex class based on this approach:
public class Vertex
{
public VertexData v;
public int X { get { return v.x; } set { v.x = value; } }
public int Y { get { return v.y; } set { v.y = value; } }
public Vertex(VertexData vertex)
{
v = vertex;
}
}
Having taken care of the representation, there is one problem left to tackle with this refactoring. The optimized algorithm uses the concept of splicing edges. The problem is that my adapter does not know of edges – it knows only of the vertices that were added. In the original implementation it was possible to pass on the integer representation of the edge being spliced to the adapter and then reconstruct the edge, but this was a bad hack. Because we lifted the domain size constraint this approach no longer works as there is no way to represent an edge as an integer. Also you could argue that the adapter should not even care about the concept of edges, it needs only to build a set of vertices and then let the TSP solver do the rest. Conceptually we don’t want the adapter to know of the edges because then we could cheat in the implementation.
Essentially the problem boils down to the fact that the model has a rule that does some magic computations which translate into the addition of a vertex to the graph (the growth process):
[Rule(Action = "Magic()")]
static void Magic()
{
// Compute a new vertex using some magic rules
Vertex v;
...
// Re-use existing concept for adding a vertex to the graph
InsertVertex(v.x, v.y);
}
[Rule(Action = "InsertVertex(x,y)")]
static void InsertVertex(int x, int y)
{
...
}
We don’t want the adapter nor the SUT to know of this magic rule, because it would have to re-implement the same logic to produce the actual added vertex (the generated tests will call Magic on the adapter, not followed by any call to InsertVertex). So how do we avoid this?
Well… one trick is to use the following pattern:
static VertexData magicVertex;
[Rule(Action = "Magic()")]
static void Magic()
{
// Compute a new vertex using some magic rules
Vertex v;
...
// Store computed vertex for insertion
magicVertex = v.v;
}
[Rule(Action = "InsertMagicVertex(x,y)")]
static void InsertMagicVertex(int x, int y)
{
Condition.IsTrue(x == magicVertex.x);
Condition.IsTrue(y == magicVertex.y);
InsertVertex(v.x, v.y);
}
The trick here is that the Magic rule computes the vertex, but instead of adding it directly it stores the required information in a variable priming the model. Then the InsertMagicVertex rule can pick up the computed value and insert it. Because the signature of this rule has all the required information the adapter layer will simply call the same function as InsertVertex does, with no need for re-implementing the difficult computational logic.
In the Config.cord file, instead of using the Magic and InsertMagicVertex rules directly, define the following scenario:
machine MagicScenario() : Main where ForExploration = false
{
Magic ; InsertMagicVertex
}
This will make sure that after computing a vertex it is immediately added to the graph.
No comments:
Post a Comment