[libavoid] Minimizing edge crossing by choosing appropriate connectionPin

[Thomasb81]

Hello

On following example :

The testcase is represented by 4 shapes. The 2 left shape, are each connected to shape on the right. Each shape on the right have 2 connectorPin. Each connectorPin of each shape are registered with the same channel id and has the attribute exclusive set to true. In other words, the 2 connectorPin of each of the right shape are free to commute.

Since the router is configured with non null crossingPenalty, why the router does not look for the solution that consist to switch the 2 connectorPin on right bottom shape from current solution to remove 1 edge crossing ? By increasing the crossingPenalty the router end-up to choose a route that pass on the left of the left shape : that's not a solution I expect ...

It look like the astar algo is picking up the first available connectorPin as target without considering other option ...

If the router is able to identify the right connectorPin, it could minimize edge crossing. Consequently a drawing of the routing become simpler to understand.

For clarity, here is the result of the modified testcase for which connectionPin channel is chosen to force router to find the solution with only one edge crossing.

Is there a way to configure the router to make it chose the appropriate connectorPin to minimize edge crossing ? Is this behavior a bug or a limitation ?

Thanks

Here the code produce by outputInstanceToSVG:

#include "libavoid/libavoid.h"
using namespace Avoid;
int main(void) {
    Router *router = new Router(OrthogonalRouting);
    router->setRoutingParameter((RoutingParameter)0, 10);
    router->setRoutingParameter((RoutingParameter)1, 0);
    router->setRoutingParameter((RoutingParameter)2, 10);
    router->setRoutingParameter((RoutingParameter)3, 4000);
    router->setRoutingParameter((RoutingParameter)4, 10);
    router->setRoutingParameter((RoutingParameter)5, 100);
    router->setRoutingParameter((RoutingParameter)6, 10);
    router->setRoutingParameter((RoutingParameter)7, 20);
    router->setRoutingParameter((RoutingParameter)8, 1);
    router->setRoutingOption((RoutingOption)0, false);
    router->setRoutingOption((RoutingOption)1, true);
    router->setRoutingOption((RoutingOption)2, false);
    router->setRoutingOption((RoutingOption)3, false);
    router->setRoutingOption((RoutingOption)4, true);
    router->setRoutingOption((RoutingOption)5, true);
    router->setRoutingOption((RoutingOption)6, true);
    Polygon polygon;
    ConnRef *connRef = nullptr;
    ConnEnd srcPt;
    ConnEnd dstPt;
    ConnEnd heConnPt;
    PolyLine newRoute;
    ShapeConnectionPin *connPin = nullptr;

    // shapeRef1
    polygon = Polygon(4);
    polygon.ps[0] = Point(100, 0);
    polygon.ps[1] = Point(100, 50);
    polygon.ps[2] = Point(0, 50);
    polygon.ps[3] = Point(0, 0);
    ShapeRef *shapeRef1 = new ShapeRef(router, polygon, 1);
    connPin = new ShapeConnectionPin(shapeRef1, 1, 100, 25, false, 0, (ConnDirFlags) 8);
    connPin->setExclusive(false);

    // shapeRef2
    polygon = Polygon(4);
    polygon.ps[0] = Point(100, 100);
    polygon.ps[1] = Point(100, 150);
    polygon.ps[2] = Point(0, 150);
    polygon.ps[3] = Point(0, 100);
    ShapeRef *shapeRef2 = new ShapeRef(router, polygon, 2);
    connPin = new ShapeConnectionPin(shapeRef2, 1, 100, 25, false, 0, (ConnDirFlags) 8);
    connPin->setExclusive(false);

    // shapeRef3
    polygon = Polygon(4);
    polygon.ps[0] = Point(300, 0);
    polygon.ps[1] = Point(300, 50);
    polygon.ps[2] = Point(200, 50);
    polygon.ps[3] = Point(200, 0);
    ShapeRef *shapeRef3 = new ShapeRef(router, polygon, 3);
    connPin = new ShapeConnectionPin(shapeRef3, 1, 0, 15, false, 0, (ConnDirFlags) 4);
    connPin = new ShapeConnectionPin(shapeRef3, 1, 0, 35, false, 0, (ConnDirFlags) 4);

    // shapeRef6
    polygon = Polygon(4);
    polygon.ps[0] = Point(300, 100);
    polygon.ps[1] = Point(300, 150);
    polygon.ps[2] = Point(200, 150);
    polygon.ps[3] = Point(200, 100);
    ShapeRef *shapeRef6 = new ShapeRef(router, polygon, 6);
    connPin = new ShapeConnectionPin(shapeRef6, 2, 0, 15, false, 0, (ConnDirFlags) 4);
    connPin = new ShapeConnectionPin(shapeRef6, 2, 0, 35, false, 0, (ConnDirFlags) 4);

    // connRef4
    connRef = new ConnRef(router, 4);
    srcPt = ConnEnd(shapeRef1, 1);
    connRef->setSourceEndpoint(srcPt);
    dstPt = ConnEnd(shapeRef3, 1);
    connRef->setDestEndpoint(dstPt);
    connRef->setRoutingType((ConnType)2);

    // connRef5
    connRef = new ConnRef(router, 5);
    srcPt = ConnEnd(shapeRef2, 1);
    connRef->setSourceEndpoint(srcPt);
    dstPt = ConnEnd(shapeRef3, 1);
    connRef->setDestEndpoint(dstPt);
    connRef->setRoutingType((ConnType)2);

    // connRef7
    connRef = new ConnRef(router, 7);
    srcPt = ConnEnd(shapeRef1, 1);
    connRef->setSourceEndpoint(srcPt);
    dstPt = ConnEnd(shapeRef6, 2);
    connRef->setDestEndpoint(dstPt);
    connRef->setRoutingType((ConnType)2);

    // connRef8
    connRef = new ConnRef(router, 8);
    srcPt = ConnEnd(shapeRef2, 1);
    connRef->setSourceEndpoint(srcPt);
    dstPt = ConnEnd(shapeRef6, 2);
    connRef->setDestEndpoint(dstPt);
    connRef->setRoutingType((ConnType)2);

    router->processTransaction();
    router->outputInstanceToSVG();
    delete router;
    return 0;
};

[Thomasb81]

After toying, reading and mumbling after the code I find this:

https://github.com/mjwybrow/adaptagrams/blob/d00ce5936c12ec80e2070e894d9124fdc5ccd506/cola/libavoid/router.cpp#L945

    // TODO: It might be worth sorting connectors and routing them from 
    //       smallest to largest estimated cost.  This way we likely get 
    //       better exclusive pin assignment during initial routing.

It is a known issue : the router is sensible to the order of processing connector. So changing the order connector are provided into router object produce different result.