node package manager
Share your code. npm Orgs help your team discover, share, and reuse code. Create a free org »



Given a directed, acyclic graph, apply a layering. The returned value will be an array of sets of vertices representing the layer assignments. Edges outgoing from each layer may only point to vertices from earlier layers.

const toLayers = require('dag-to-layers')
const digraph = require('digraph-tag')
const graph = digraph`
  A -> B
  B -> C
  C -> D
  X -> Y
  Y -> Z
  Z -> D
  D -> U
  U -> V
let layers = toLayers(graph.vertices, graph.incoming, graph.outgoing)
NB: vertex order within a given layer is not guaranteed:
L6: X             X
L5: Y A           |
L4: Z B           Y   A
L3: C             |   |
L2: D             Z   B
L1: U             |   |
L0: V             |   C
                   \ /


Map<Vertex → Set<Edge>> :: Edges

A map from Vertex to a Set of Edges is known as Edges.

[Set<Vertex>, ...] :: Layering

An array representing a valid layering of a graph. From the above example, the layering would look something like this:

[ Set<V>,  // ← layer zero
  Set<Z, B>,
  Set<Y, A>,
  Set<X> ] // ← layer six
assignLayers(v: Set<Vertices>, to: Edges, from: Edges[, i: Interface]) → Layering

Create a Layering from a graph represented by a set of vertices v, a map of vertices to incoming edges, a map of vertices to outgoing edges, and an optional interface.

(Edge → Vertex) :: E2V

A mapping function from edge to vertex.

{[getFrom:E2V][, getTo:E2V]} :: Interface

An object containing methods necessary for implementing the layer assignment algorithm. getFrom should return the source vertex of an edge, getTo should return the destination vertex.

The default values act as follows:

const getFrom = edge => edge[0]
const getTo = edge => edge[1]