Edge positioning in dagre-d3

Question

I am using dagre-d3 and created this sample graph. Is it possible to avoid the crossing problem in the sample marked with 1. Maybe this is possible to mark the edge connection to the bottom of the node. I am not sure how to achieve this functionality. Can someone help with that?

Furthermore, is it possible to straighten the edges 2, 3, and 4. There is enough space to straighten them. I just dont know how to do that.

Any help would be appreciated.

Zeeshan

Answer 1

// Create a new directed graph
var g = new dagreD3.graphlib.Graph().setGraph({});

// function to shuffle the list...
function shuffle(a) {
  var j, x, i;
  for (i = a.length; i; i -= 1) {
    j = Math.floor(Math.random() * i);
    x = a[i - 1];
    a[i - 1] = a[j];
    a[j] = x;
  }
  return a;
}

var nodes = ["10007154_1100", "148570017_1100", "148570018_1100", "148570019_1100",
  "148570025_1100", "148570010_1100", "148570021_1100", "148570020_1100",
  "148570026_1100", "148570011_1100", "148570022_1100", "148570010_1200", "148570020_1200", "148570026_1200", "148570023_1100", "148570011_1200",
  "148570023_1200"

];

// collect edges to a list
var edgeList = [
  ["10007154_1100", "148570017_1100", {
    "label": ""
  }],
  ["148570017_1100", "148570018_1100", {
    "label": ""
  }],
  ["148570018_1100", "148570019_1100", {
    "label": ""
  }],
  ["148570018_1100", "148570025_1100", {
    "label": ""
  }],
  ["148570019_1100", "148570020_1100", {
    "label": ""
  }],
  ["148570019_1100", "148570021_1100", {
    "label": ""
  }],
  ["148570019_1100", "148570010_1100", {
    "label": ""
  }],
  ["148570025_1100", "148570010_1100", {
    "label": ""
  }],
  ["148570025_1100", "148570026_1100", {
    "label": ""
  }],
  ["148570021_1100", "148570022_1100", {
    "label": ""
  }],
  ["148570010_1100", "148570011_1100", {
    "label": ""
  }],
  ["148570010_1100", "148570010_1200", {
    "label": ""
  }],
  ["148570020_1100", "148570020_1200", {
    "label": ""
  }],
  ["148570026_1100", "148570026_1200", {
    "label": ""
  }],
  ["148570026_1200", "148570011_1200", {
    "label": ""
  }],
  ["148570010_1200", "148570011_1200", {
    "label": ""
  }],
  ["148570022_1100", "148570023_1100", {
    "label": ""
  }],
  ["148570023_1100", "148570023_1200", {
    "label": ""
  }]
];

// Automatically label each of the nodes


var svg = d3.select("svg"),
  inner = svg.select("g");

function render_graph(render) {

  var max_cnt = 100; // try 100 times, if optimal not found, give up
  var iter_cnt = 0;
  var optimalArray, best_result;
  while (max_cnt--) {
    var g = new dagreD3.graphlib.Graph().setGraph({});
    nodes.forEach(function(node) {
      g.setNode(node, {
        label: node
      });
    });

    // set edges... randomize the list
    var list = shuffle(edgeList);
    if (!optimalArray) optimalArray = list;
    edgeList.forEach((edge) => {
      g.setEdge.apply(g, edge);
    })

    // Set the rankdir
    g.graph().rankdir = "LR";
    g.graph().nodesep = 60;

    render(inner, g);

    var nn = svg.select(".edgePaths");
    var paths = nn[0][0];
    var fc = paths.firstChild;
    var boxes = [];
    while (fc) {
      // console.log(fc.firstChild.getAttribute("d"))
      var path = fc.firstChild.getAttribute("d");
      var coords = path.split(/,|L/).map(function(c) {
        var n = c;
        if ((c[0] == "M" || c[0] == "L")) n = c.substring(1);
        return parseFloat(n);
      })
      boxes.push({
        left: coords[0],
        top: coords[1],
        right: coords[coords.length - 2],
        bottom: coords[coords.length - 1]
      });
      // console.log(coords);
      fc = fc.nextSibling;
    }
    // console.log("boxes", boxes);
    var collisionCnt = 0;
    boxes.forEach(function(a) {
      // --> test for collisions against other nodes...
      boxes.forEach(function(b) {
        if (a == b) return;
        // test if outside
        if ((a.right < b.left) ||
          (a.left > b.right) ||
          (a.top > b.bottom) ||
          (a.bottom < b.top)) {

          // test if inside
          if (a.left >= b.left && a.left <= b.right || a.right >= b.left && a.right <= b.right) {
            if (a.top <= b.top && a.top >= b.bottom) {
              collisionCnt++;
            }
            if (a.bottom <= b.top && a.bottom >= b.bottom) {
              collisionCnt++;
            }
          }
        } else {
          collisionCnt++;
        }
      })
    })
    console.log("collisions ", collisionCnt);
    if (collisionCnt == 0) {
      optimalArray = list.slice();
      console.log("Iteration cnt ", iter_cnt);
      break;
    }
    if (typeof(best_result) == "undefined") {
      best_result = collisionCnt;
    } else {
      if (collisionCnt < best_result) {
        optimalArray = list.slice();
        best_result = collisionCnt;
      }
    }
    iter_cnt++;
  }

  // if no optimal was found just render what was found...
  if (best_result >= 0) {
    var g = new dagreD3.graphlib.Graph().setGraph({});
    nodes.forEach(function(node) {
      g.setNode(node, {
        label: node
      });
    });
    optimalArray.forEach((edge) => {
      g.setEdge.apply(g, edge);
    })
    g.graph().rankdir = "LR";
    g.graph().nodesep = 60;
    render(inner, g);
  }

  // Center the graph
  var initialScale = 0.75;
  zoom
    .translate([(svg.attr("width") - g.graph().width * initialScale) / 2, 20])
    .scale(initialScale)
    .event(svg);
  svg.attr('height', g.graph().height * initialScale + 40);

}

// Set up zoom support
var zoom = d3.behavior.zoom().on("zoom", function() {
  inner.attr("transform", "translate(" + d3.event.translate + ")" +
    "scale(" + d3.event.scale + ")");
});
svg.call(zoom);

// Create the renderer
var render = new dagreD3.render();

render_graph(render);

// Run the renderer. This is what draws the final graph.

Answer 2

I think the latest dagre library doesn't have these issues any more. I replicated your diagram (click here for the demo). It's not exactly the same but quite similar.

The demo site is powered by mermaid which is powered by dagre.

Answer 3

This is a highly non-trivial problem you are trying to solve. AFAIK dagre uses a variant of the algorithm from Brandes-Köpf to calculate the alignments. Even if you can understand that algorithm, adjusting it is very hard. Instead using a completely different algorithm might give you better results: In yFiles for HTML's implementation of the hierarchic/Sugiyama style layout the Simplex Network Rank Assignment algorithm is used and it normally does not suffer from the problems you are seeing in your (otherwise very nice) drawing. GraphViz also has an implementation of that algorithm, so maybe using this will provide better results for your example, too. The Simplex approach is computationally far more expensive but is very easy to configure and fine-tune.

Regarding your first point: From a quick look at the sources I could not understand why the problem appears in your sample with Dagre. It looks like the port assignment of the incoming edges does not work correctly - the location of the ports should be sorted according to the relative locations of the nodes in the previous layer. It doesn't look like it's just the bezier control points that are wrong.