d3-dag
    Preparing search index...

    Interface MutGraph<NodeDatum, LinkDatum>

    a mutable graph representation

    In addition to all of the methods inherent to Graphs, this also allows structure graph modification with the node and link methods to either create an empty node or create a link between two nodes. Nodes and links can be removed with the delete method on nodes and links.

    In order to keep track of caches, internally adding links runs union-find which has near, but not quite, constant complexity. However, various methods can run in linear time making some access patterns run in worst case quadratic if they're called in between modifications. This was ultimately deemed acceptable as all modification will likely come before a layout, and that will always take linear time.

    interface MutGraph<in out NodeDatum, in out LinkDatum> {
        acyclic(): boolean;
        connected(): boolean;
        leaves(): IterableIterator<MutGraphNode<NodeDatum, LinkDatum>>;
        link(
            source: MutGraphNode<NodeDatum, LinkDatum>,
            target: MutGraphNode<NodeDatum, LinkDatum>,
            ...datum: undefined extends LinkDatum
                ? [datum?: LinkDatum]
                : [datum: LinkDatum],
        ): MutGraphLink<NodeDatum, LinkDatum>;
        links(): IterableIterator<MutGraphLink<NodeDatum, LinkDatum>>;
        multi(): boolean;
        nlinks(): number;
        nnodes(): number;
        node(
            ...datum: undefined extends NodeDatum
                ? [datum?: NodeDatum]
                : [datum: NodeDatum],
        ): MutGraphNode<NodeDatum, LinkDatum>;
        nodes(): IterableIterator<MutGraphNode<NodeDatum, LinkDatum>>;
        roots(): IterableIterator<MutGraphNode<NodeDatum, LinkDatum>>;
        split(): IterableIterator<MutGraphNode<NodeDatum, LinkDatum>>;
        toJSON(): unknown;
        topological(
            rank?: Rank<NodeDatum, LinkDatum>,
        ): GraphNode<NodeDatum, LinkDatum>[];
    }

    Type Parameters

    • in out NodeDatum
    • in out LinkDatum

    Hierarchy (View Summary)

    Index

    Methods

    • an iterator over the leaves of the graph

      The leaves are defined as a set of nodes such that every node in the graph is an ancestor of one of the leaves, an no leaf is an ancestor of any other leaf. It is guaranteed to include every node with no children, but one node in a cycle may be chosen if there is no unique leaf for that cycle.

      Returns IterableIterator<MutGraphNode<NodeDatum, LinkDatum>>

      the current implementation will return a minimal leaf set as long as target cycles contain a node with a single child.

    • true if at least one node in this graph has multiple links to the same child

      Returns boolean

    • an iterator over every node in the graph

      Returns IterableIterator<MutGraphNode<NodeDatum, LinkDatum>>

      Be careful not to modify the graph structure while iterating as any modification, including adding or removing links, can change the behavior of iteration giving unexpected results. If you want to guarantee consistent iteration, allocating an array first with [...graph.nodes()] will ensure consistent iteration.

    • an iterator over the roots of the graph

      The roots are defined as a set of nodes such that every node in the graph is a descendant of one of the roots, an no root is a descendant of any other root. It is guaranteed to include every node with no parents, but one node in a cycle may be chosen if there is no unique root for that cycle.

      Returns IterableIterator<MutGraphNode<NodeDatum, LinkDatum>>

      the current implementation will return a minimal root set as long as source cycles contain a node with a single parent.

    • serialize the graph

      Returns unknown

      this is intended to be called automatically by JSON.stringify.

    • compute a topological order of the graph

      If the graph can't be represented in topological order, this will try to minimize the number of edge inversions. Optimally minimizing inversions is np-complete, so this will only be approximate.

      You can optionally specify a Rank accessor that defines a numerical rank for every node. Nodes with a lower rank will come before nodes of a higher rank even if that requires more edge inversions. Nodes without a rank are unconstrained.

      Parameters

      Returns GraphNode<NodeDatum, LinkDatum>[]