Narwhals Prolong Mischief

    simplify-dag

    2.0.1 • Public • Published

    simplify-dag

    Given a directed acyclic graph, simplify straight-line runs into single vertices.

    const simplify = require('simplify-dag')
    const digraph = require('digraph-tag')
     
    let graph = digraph`
      A -> B
      B -> C
      C -> D
      X -> Y
      Y -> Z
      Z -> D
      D -> U
      U -> V
    `
     
    let simplified = simplify(graph) 
    /*
       A   X
       ↓   ↓
       B   Y
       ↓   ↓       [A, B, C]   [X, Y, Z]
       C   Z            \___   ___/
        \ /                 \ /
         Y     --->          Y
         ↓                   ↓
         D               [D, U, V]
         ↓
         U
         ↓
         V
    */

    Note: passing a graph with cycles to this module will mostly likely result in an infinite loop. Be sure to remove cycles from your graph before applying this module.

    API

    Map<Vertex → Set<Edge>> → Edges

    A Map from Vertex (whatever type you provide) to Edge will be defined as Edges.

    {vertices: Set<Vertex>, outgoing: Edges, incoming: Edges} → Graph

    An object with the properties vertices, outgoing, and incoming, whose types are Set<Vertex> and Edges respectively will be known as a Graph. Incoming Edges will map a given Vertex instance to every incoming Edge, and outgoing Edges will map Vertex instances to every outgoing Edge. Edge and Vertex types are user-defined – that is, you should provide instructions to this module on how to treat these types.

    Array<Vertex> → DerivedVertex

    DerivedVertex instances represent straight-line runs of Vertex instances from the original graph. This module will only produce DerivedVertex instances.

    {copyEdge: Function?, {s,g}et{From,To}: Function?}? → Interface

    An Interface is defined as an object that optionally defines copyEdge, getFrom, and getTo properties.

    • copyEdge takes the original Edge object, and should return a new copy of it.
    • getFrom takes an Edge and returns the source of the edge. If not defined it will treat edges as 2-element arrays, and attempt to take the first element as the source.
    • getTo takes an Edge and returns the destination of the edge. As above, if not defined it will treat edges as a 2-element array and return the second element as the destination.
    • setFrom takes an Edge and a Vertex and should mutate the Edge such that it originates from the vertex.
    • setTo takes an Edge and a Vertex and should mutate the Edge such that it terminates in the vertex.
    simplify(vertices: Set<Vertex>, incoming: Edges,
    outgoing: Edges, interface: Interface) → Graph

    Given a set of vertices, a map from vertex to incoming edges, a map from vertex to outgoing edges, and optionally an interface for Vertex and Edge interaction, return a new Graph instance representing a simplified DAG.

    License

    MIT

    Install

    npm i simplify-dag

    DownloadsWeekly Downloads

    5

    Version

    2.0.1

    License

    MIT

    Last publish

    Collaborators

    • chrisdickinson