code: function findType1Conflicts(g, layering) {
    var conflicts = {};
  
    function visitLayer(prevLayer, layer) {
      var
        // last visited node in the previous layer that is incident on an inner
        // segment.
        k0 = 0,
        // Tracks the last node in this layer scanned for crossings with a type-1
        // segment.
        scanPos = 0,
        prevLayerLength = prevLayer.length,
        lastNode = _.last(layer);
  
      _.forEach(layer, function(v, i) {
        var w = findOtherInnerSegmentNode(g, v),
          k1 = w ? g.node(w).order : prevLayerLength;
  
        if (w || v === lastNode) {
          _.forEach(layer.slice(scanPos, i +1), function(scanNode) {
            _.forEach(g.predecessors(scanNode), function(u) {
              var uLabel = g.node(u),
                uPos = uLabel.order;
              if ((uPos < k0 || k1 < uPos) &&
                  !(uLabel.dummy && g.node(scanNode).dummy)) {
                addConflict(conflicts, u, scanNode);
              }
            });
          });
          scanPos = i + 1;
          k0 = k1;
        }
      });
  
      return layer;
    }
  
    _.reduce(layering, visitLayer);
    return conflicts;
  }
docs: /*
  Marks all edges in the graph with a type-1 conflict with the "type1Conflict"
  property. A type-1 conflict is one where a non-inner segment crosses an
  inner segment. An inner segment is an edge with both incident nodes marked
  with the "dummy" property.
  
  This algorithm scans layer by layer, starting with the second, for type-1
  conflicts between the current layer and the previous layer. For each layer
  it scans the nodes from left to right until it reaches one that is incident
  on an inner segment. It then scans predecessors to determine if they have
  edges that cross that inner segment. At the end a final scan is done for all
  nodes on the current rank to see if they cross the last visited inner
  segment.
  
  This algorithm (safely) assumes that a dummy node will only be incident on a
  single node in the layers being scanned.