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 =const digraph =const graph = digraph`A -> BB -> CC -> DX -> YY -> ZZ -> DD -> UU -> V`let layers =/*NB: vertex order within a given layer is not guaranteed:L6: X XL5: Y A |L4: Z B Y AL3: C | |L2: D Z BL1: U | |L0: V | C\ /Y|D|U|V*/
A map from
Vertex to a
Edges is known as
An array representing a valid layering of a graph. From the above example, the layering would look something like this:
[ Set<V>, // ← layer zeroSet<U>,Set<D>,Set<C>,Set<Z, B>,Set<Y, A>,Set<X> ] // ← layer six
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.
A mapping function from edge to vertex.
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
The default values act as follows:
const getFrom = edge0const getTo = edge1