Assertion Failure in nudgeOrthogonalRoutes

[awci]

I'm encountering an assertion failure while using libavoid-js. The error message is as follows:

Aborted(Assertion failed: vs[it->second]->id != freeSegmentID, at: ./adaptagrams/cola/libavoid/orthogonal.cpp,3049,nudgeOrthogonalRoutes)

Steps to Reproduce:

Use the following example data as input:

x:  0 y:  680 width:  120 height:  120
x:  320 y:  1055 width:  120 height:  120
x:  320 y:  1225 width:  120 height:  120
x:  320 y:  1395 width:  120 height:  120
x:  320 y:  1565 width:  120 height:  120
x:  320 y:  1735 width:  120 height:  120
x:  320 y:  1905 width:  120 height:  120
x:  320 y:  2075 width:  120 height:  120
x:  640 y:  1605 width:  120 height:  120
x:  320 y:  2245 width:  120 height:  120
x:  640 y:  25 width:  120 height:  120
x:  320 y:  25 width:  120 height:  120
x:  0 y:  1900 width:  120 height:  120
x:  960 y:  2560 width:  120 height:  120
x:  640 y:  2522.5 width:  120 height:  120
x:  640 y:  362.5 width:  120 height:  120
x:  960 y:  532.5 width:  120 height:  120
x:  640 y:  532.5 width:  120 height:  120
x:  0 y:  510 width:  120 height:  120
x:  0 y:  680 width:  120 height:  120
x:  640 y:  702.5 width:  120 height:  120
x:  1280 y:  1737.5 width:  120 height:  120
x:  1280 y:  2950 width:  120 height:  120
x:  0 y:  1090 width:  120 height:  120
x:  640 y:  872.5 width:  120 height:  120
x:  320 y:  1245 width:  120 height:  120
x:  0 y:  1260 width:  120 height:  120

Set the number of connections between each node to 2.

Include 2 self-relations on nodes.

Expected Behavior: The library should process the input without triggering an assertion failure.

Actual Behavior: The application aborts with the assertion failure mentioned above.

example file:

// debug web version
import { AvoidLib } from './debug-dist/index.mjs';
// production web version
// import { AvoidLib } from './dist/index.js';

async function main() {
  // init Avoid module
  await AvoidLib.load();
  const Avoid = AvoidLib.getInstance();

  const router = new Avoid.Router(Avoid.OrthogonalRouting);

  router.setRoutingParameter(6, 30); // shapeBufferDistance = 30
  router.setRoutingParameter(
    Avoid.idealNudgingDistance,
    10
  );
  router.setRoutingOption(
    Avoid.nudgeOrthogonalTouchingColinearSegments,
    false
  );

  /*
      This option can be used to control whether the router performs a preprocessing step
      before orthogonal nudging where is tries to unify segments and centre them in free space.
      This generally results in better quality ordering and nudging.

      Defaults to true.

      You may wish to turn this off for large examples where it can be very slow
      and will make little difference.
      */
  router.setRoutingOption(
    Avoid.performUnifyingNudgingPreprocessingStep,
    true
  );

  router.setRoutingOption(Avoid.nudgeSharedPathsWithCommonEndPoint, true);

  router.setRoutingOption(
    Avoid.nudgeOrthogonalSegmentsConnectedToShapes,
    true
  );

  const w = 120;
  const h = 120;

  let x1 = 0;
  let y1 = 680;
  const rectangle1CentrePoint = new Avoid.Point(50, 50);
  const rectangle1TopLeftPoint = new Avoid.Point(x1, y1);
  const rectangle1BottomRightPoint = new Avoid.Point(x1+w, y1+h);
  const rectangle1 = new Avoid.Rectangle(rectangle1TopLeftPoint, rectangle1BottomRightPoint);
  const shapeRef1 = new Avoid.ShapeRef(router, rectangle1);

  let x2 = 320;
  let y2 = 1055;
  const rectangle2CentrePoint = new Avoid.Point(750, 750);
  const rectangle2TopLeftPoint = new Avoid.Point(x2, y2);
  const rectangle2BottomRightPoint = new Avoid.Point(x2+w, y2+h);
  const rectangle2 = new Avoid.Rectangle(rectangle2TopLeftPoint, rectangle2BottomRightPoint);
  const shapeRef2 = new Avoid.ShapeRef(router, rectangle2);

  let x3 = 320;
  let y3 = 1225;
  const rectangle3CentrePoint = new Avoid.Point(150, 450);
  const rectangle3TopLeftPoint = new Avoid.Point(x3, y3);
  const rectangle3BottomRightPoint = new Avoid.Point(x3+w, y3+h);
  const rectangle3 = new Avoid.Rectangle(rectangle3TopLeftPoint, rectangle3BottomRightPoint);
  const shapeRef3 = new Avoid.ShapeRef(router, rectangle3);


  let x4 = 320;
  let y4 = 1225;
  const rectangle4CentrePoint = new Avoid.Point(50, 50);
  const rectangle4TopLeftPoint = new Avoid.Point(x4, y4);
  const rectangle4BottomRightPoint = new Avoid.Point(x4+w, y4+h);
  const rectangle4 = new Avoid.Rectangle(rectangle4TopLeftPoint, rectangle4BottomRightPoint);
  const shapeRef4 = new Avoid.ShapeRef(router, rectangle4);

  let x5 = 320;
  let y5 = 1565;
  const rectangle5CentrePoint = new Avoid.Point(750, 750);
  const rectangle5TopLeftPoint = new Avoid.Point(x5, y5);
  const rectangle5BottomRightPoint = new Avoid.Point(x5+w, y5+h);
  const rectangle5 = new Avoid.Rectangle(rectangle5TopLeftPoint, rectangle5BottomRightPoint);
  const shapeRef5 = new Avoid.ShapeRef(router, rectangle5);

  let x6 = 320;
  let y6 = 1735;
  const rectangle6CentrePoint = new Avoid.Point(150, 450);
  const rectangle6TopLeftPoint = new Avoid.Point(x6, y6);
  const rectangle6BottomRightPoint = new Avoid.Point(x6+w, y6+h);
  const rectangle6 = new Avoid.Rectangle(rectangle6TopLeftPoint, rectangle6BottomRightPoint);
  const shapeRef6 = new Avoid.ShapeRef(router, rectangle6);


  let x7 = 320;
  let y7 = 1905;
  const rectangle7CentrePoint = new Avoid.Point(50, 50);
  const rectangle7TopLeftPoint = new Avoid.Point(x7, y7);
  const rectangle7BottomRightPoint = new Avoid.Point(x7+w, y7+h);
  const rectangle7 = new Avoid.Rectangle(rectangle7TopLeftPoint, rectangle7BottomRightPoint);
  const shapeRef7 = new Avoid.ShapeRef(router, rectangle7);

  let x8 = 320;
  let y8 = 2075;
  const rectangle8CentrePoint = new Avoid.Point(750, 750);
  const rectangle8TopLeftPoint = new Avoid.Point(x8, y8);
  const rectangle8BottomRightPoint = new Avoid.Point(x8+w, y8+h);
  const rectangle8 = new Avoid.Rectangle(rectangle8TopLeftPoint, rectangle8BottomRightPoint);
  const shapeRef8 = new Avoid.ShapeRef(router, rectangle8);

  let x9 = 640;
  let y9 = 1605;
  const rectangle9CentrePoint = new Avoid.Point(150, 450);
  const rectangle9TopLeftPoint = new Avoid.Point(x9, y9);
  const rectangle9BottomRightPoint = new Avoid.Point(x9+w, y9+h);
  const rectangle9 = new Avoid.Rectangle(rectangle9TopLeftPoint, rectangle9BottomRightPoint);
  const shapeRef9 = new Avoid.ShapeRef(router, rectangle9);

  let x10 = 320;
  let y10 = 2245;
  const rectangle10CentrePoint = new Avoid.Point(150, 450);
  const rectangle10TopLeftPoint = new Avoid.Point(x10, y10);
  const rectangle10BottomRightPoint = new Avoid.Point(x10+w, y10+h);
  const rectangle10 = new Avoid.Rectangle(rectangle10TopLeftPoint, rectangle10BottomRightPoint);
  const shapeRef10 = new Avoid.ShapeRef(router, rectangle10);

  let x11 = 640;
  let y11 = 25;
  const rectangle11CentrePoint = new Avoid.Point(150, 450);
  const rectangle11TopLeftPoint = new Avoid.Point(x11, y11);
  const rectangle11BottomRightPoint = new Avoid.Point(x11+w, y11+h);
  const rectangle11 = new Avoid.Rectangle(rectangle11TopLeftPoint, rectangle11BottomRightPoint);
  const shapeRef11 = new Avoid.ShapeRef(router, rectangle11);

  let x12 = 320;
  let y12 = 25;
  const rectangle12CentrePoint = new Avoid.Point(150, 450);
  const rectangle12TopLeftPoint = new Avoid.Point(x12, y12);
  const rectangle12BottomRightPoint = new Avoid.Point(x12+w, y12+h);
  const rectangle12 = new Avoid.Rectangle(rectangle12TopLeftPoint, rectangle12BottomRightPoint);
  const shapeRef12 = new Avoid.ShapeRef(router, rectangle12);

  let x13 = 0;
  let y13 = 1900;
  const rectangle13CentrePoint = new Avoid.Point(150, 450);
  const rectangle13TopLeftPoint = new Avoid.Point(x13, y13);
  const rectangle13BottomRightPoint = new Avoid.Point(x13+w, y13+h);
  const rectangle13 = new Avoid.Rectangle(rectangle13TopLeftPoint, rectangle13BottomRightPoint);
  const shapeRef13 = new Avoid.ShapeRef(router, rectangle13);

  let x14 = 960;
  let y14 = 2560;
  const rectangle14CentrePoint = new Avoid.Point(150, 450);
  const rectangle14TopLeftPoint = new Avoid.Point(x14, y14);
  const rectangle14BottomRightPoint = new Avoid.Point(x14+w, y14+h);
  const rectangle14 = new Avoid.Rectangle(rectangle14TopLeftPoint, rectangle14BottomRightPoint);
  const shapeRef14 = new Avoid.ShapeRef(router, rectangle14);

  let x15 = 640;
  let y15 = 2522.5;
  const rectangle15CentrePoint = new Avoid.Point(150, 450);
  const rectangle15TopLeftPoint = new Avoid.Point(x15, y15);
  const rectangle15BottomRightPoint = new Avoid.Point(x15+w, y15+h);
  const rectangle15 = new Avoid.Rectangle(rectangle15TopLeftPoint, rectangle15BottomRightPoint);
  const shapeRef15 = new Avoid.ShapeRef(router, rectangle15);

  let x16 = 640;
  let y16 = 362.5;
  const rectangle16CentrePoint = new Avoid.Point(150, 450);
  const rectangle16TopLeftPoint = new Avoid.Point(x16, y16);
  const rectangle16BottomRightPoint = new Avoid.Point(x16+w, y16+h);
  const rectangle16 = new Avoid.Rectangle(rectangle16TopLeftPoint, rectangle16BottomRightPoint);
  const shapeRef16 = new Avoid.ShapeRef(router, rectangle16);

  let x17 = 960;
  let y17 = 532.5;
  const rectangle17CentrePoint = new Avoid.Point(150, 450);
  const rectangle17TopLeftPoint = new Avoid.Point(x17, y17);
  const rectangle17BottomRightPoint = new Avoid.Point(x17+w, y17+h);
  const rectangle17 = new Avoid.Rectangle(rectangle17TopLeftPoint, rectangle17BottomRightPoint);
  const shapeRef17 = new Avoid.ShapeRef(router, rectangle17);

  let x18 = 640;
  let y18 = 532.5;
  const rectangle18CentrePoint = new Avoid.Point(150, 450);
  const rectangle18TopLeftPoint = new Avoid.Point(x18, y18);
  const rectangle18BottomRightPoint = new Avoid.Point(x18+w, y18+h);
  const rectangle18 = new Avoid.Rectangle(rectangle18TopLeftPoint, rectangle18BottomRightPoint);
  const shapeRef18 = new Avoid.ShapeRef(router, rectangle18);

  let x19 = 0;
  let y19 = 510;
  const rectangle19CentrePoint = new Avoid.Point(150, 450);
  const rectangle19TopLeftPoint = new Avoid.Point(x19, y19);
  const rectangle19BottomRightPoint = new Avoid.Point(x19+w, y19+h);
  const rectangle19 = new Avoid.Rectangle(rectangle19TopLeftPoint, rectangle19BottomRightPoint);
  const shapeRef19 = new Avoid.ShapeRef(router, rectangle19);

  let x20 = 0;
  let y20 = 680;
  const rectangle20CentrePoint = new Avoid.Point(150, 450);
  const rectangle20TopLeftPoint = new Avoid.Point(x20, y20);
  const rectangle20BottomRightPoint = new Avoid.Point(x20+w, y20+h);
  const rectangle20 = new Avoid.Rectangle(rectangle20TopLeftPoint, rectangle20BottomRightPoint);
  const shapeRef20 = new Avoid.ShapeRef(router, rectangle20);

  let x21 = 640;
  let y21 = 702.5;
  const rectangle21CentrePoint = new Avoid.Point(150, 450);
  const rectangle21TopLeftPoint = new Avoid.Point(x21, y21);
  const rectangle21BottomRightPoint = new Avoid.Point(x21+w, y21+h);
  const rectangle21 = new Avoid.Rectangle(rectangle21TopLeftPoint, rectangle21BottomRightPoint);
  const shapeRef21 = new Avoid.ShapeRef(router, rectangle21);

  let x22 = 1280;
  let y22 = 1737;
  const rectangle22CentrePoint = new Avoid.Point(150, 450);
  const rectangle22TopLeftPoint = new Avoid.Point(x22, y22);
  const rectangle22BottomRightPoint = new Avoid.Point(x22+w, y22+h);
  const rectangle22 = new Avoid.Rectangle(rectangle22TopLeftPoint, rectangle22BottomRightPoint);
  const shapeRef22 = new Avoid.ShapeRef(router, rectangle22);

  let x23 = 1280;
  let y23 = 2950;
  const rectangle23CentrePoint = new Avoid.Point(150, 450);
  const rectangle23TopLeftPoint = new Avoid.Point(x23, y23);
  const rectangle23BottomRightPoint = new Avoid.Point(x23+w, y23+h);
  const rectangle23 = new Avoid.Rectangle(rectangle23TopLeftPoint, rectangle23BottomRightPoint);
  const shapeRef23 = new Avoid.ShapeRef(router, rectangle23);

  let x24 = 0;
  let y24 = 1090;
  const rectangle24CentrePoint = new Avoid.Point(150, 450);
  const rectangle24TopLeftPoint = new Avoid.Point(x24, y24);
  const rectangle24BottomRightPoint = new Avoid.Point(x24+w, y24+h);
  const rectangle24 = new Avoid.Rectangle(rectangle24TopLeftPoint, rectangle24BottomRightPoint);
  const shapeRef24 = new Avoid.ShapeRef(router, rectangle24);

  let x25 = 640;
  let y25 = 872;
  const rectangle25CentrePoint = new Avoid.Point(150, 450);
  const rectangle25TopLeftPoint = new Avoid.Point(x25, y25);
  const rectangle25BottomRightPoint = new Avoid.Point(x25+w, y25+h);
  const rectangle25 = new Avoid.Rectangle(rectangle25TopLeftPoint, rectangle25BottomRightPoint);
  const shapeRef25 = new Avoid.ShapeRef(router, rectangle25);

  let x26 = 320;
  let y26 = 1245;
  const rectangle26CentrePoint = new Avoid.Point(150, 450);
  const rectangle26TopLeftPoint = new Avoid.Point(x26, y26);
  const rectangle26BottomRightPoint = new Avoid.Point(x26+w, y26+h);
  const rectangle26 = new Avoid.Rectangle(rectangle26TopLeftPoint, rectangle26BottomRightPoint);
  const shapeRef26 = new Avoid.ShapeRef(router, rectangle26);

  let x27 = 0;
  let y27 = 1260;
  const rectangle27CentrePoint = new Avoid.Point(150, 450);
  const rectangle27TopLeftPoint = new Avoid.Point(x27, y27);
  const rectangle27BottomRightPoint = new Avoid.Point(x27+w, y27+h);
  const rectangle27 = new Avoid.Rectangle(rectangle27TopLeftPoint, rectangle27BottomRightPoint);
  const shapeRef27 = new Avoid.ShapeRef(router, rectangle27);


  function connCallback(connRefPtr) {
    const connRef = Avoid.wrapPointer(connRefPtr, Avoid.ConnRef);
    //console.log(connRefPtr, Avoid.getPointer(connRef));
    console.log(`Connector ${connRef.id()} needs rerouting!`);
    const route = connRef.displayRoute();
    //console.log('New path: ');
    //console.log('----------');
    for (let i = 0; i < route.size(); i++) {
      //console.log(`(${route.get_ps(i).x}, ${route.get_ps(i).y})`);
    }
    console.timeEnd('Start');
    //console.log('----------');
  }

  function connectShapes(shape1, shape2) {
    const shapeConnectionPinSrc1 = new Avoid.ShapeConnectionPin(shape1, 1, 0.5, 0.5, true, 0, 15);
    shapeConnectionPinSrc1.setExclusive(false);
    const connRefSrcConnEnd = new Avoid.ConnEnd(shape1, 1);
    const shapeConnectionPinDest1 = new Avoid.ShapeConnectionPin(shape2, 1, 0.5, 0.5, true, 0, 15);
    shapeConnectionPinDest1.setExclusive(false);
    const connRefDestConnEnd = new Avoid.ConnEnd(shape2, 1);
    const connRef = new Avoid.ConnRef(router, connRefSrcConnEnd, connRefDestConnEnd);
    connRef.setCallback(connCallback, connRef);
    return connRef;
  }

  const shapes = [
    shapeRef1, shapeRef2, shapeRef3,
    shapeRef4, shapeRef5, shapeRef6,
    shapeRef7, shapeRef8, shapeRef9,
    shapeRef10, shapeRef11, shapeRef12
  ];
  const connections = [];
  const numConnections = 2;  // For example, create 10 connections between each pair
  for (let i = 0; i < shapes.length; i++) {
// create two way connections between shapes
    for (let j = 0; j < shapes.length; j++) {
// disables self relations
      //if (i !== j) {
        // Create multiple connections between shape[i] and shape[j]
        for (let k = 0; k < numConnections; k++) {
          console.log(`Creating edge between Shape${i} -> Shape${j} Connection No: ${k}`);
          connections.push(connectShapes(shapes[i], shapes[j]));
        }
      //}
    }
  }
  console.time('Start');
  router.processTransaction();
}

main()

[awci]

@Aksem can you pls take a look at this? The example code is from branch [bugfix/crash](https://github.com/Aksem/libavoid-js/tree/bugfix/crash)

[Aksem]

Yes, I'll try to reproduce it in the evening

[Aksem]

@awci I managed to reproduce the error, thank you for the code example. I'll post updates about the solution here.

[awci]

Hi @Aksem thanks for your quick reply I am waiting for an update from you thanks a lot again.

[KMordalski]

@Aksem (CC: @awci )

I've encountered same issue some time ago. For visual reproduction you can check my bug report in jointjs repository.

I've also forked you repository to make libavoid.wasm module restartable so once algorithm fails I don't have to force user to refresh entire page to reload the module.

[awci]

Hi @Aksem
I hope you're doing well. I just wanted to follow up on the issue. I understand you're busy, but I wanted to know if there have been any updates or if there's anything I can do to help move things forward.

[Aksem]

Hi @awci !
I reproduced the problem in adaptagrams / libavoid , there is a test for that ( https://github.com/Aksem/adaptagrams/tree/bugfix/orthogonal-nudging ), I found where and why it happens, but I'm still working on the solution.

[Aksem]

It seems to work, but I will check results more precisely today and if they are correct, create a new version.

[Aksem]

v0.4.3 with fix is published, please try it and if you encounter any problems, just let me know.

[KMordalski]

@Aksem
Thanks for fixing that!
I'll take a look at the fix soon. Much appreciate!

Have you considered pinging original creators at https://github.com/mjwybrow/adaptagrams to update their code? 🤔