Interface Graph<NodeDatum, LinkDatum>

A graph representation

Graphs are collections of GraphNodes, held together by GraphLinks, although there's no requirement that they're connected. Graphs support iterating over their nodes and links as well as checking if certain properties hold. Each node is also defined as a graph of just its connected component, so all methods of a graph also apply to any individual node, treated as all nodes reachable from the current node.

The structure of a Graph is immutable, allowing for appropriate variance with readonly methods. For a graph whos structure can be modified, see MutGraph.

Methods names preceeded by an n will return a number, often the length of the iterable produces by the method sans-prefix.

interface Graph<out NodeDatum = unknown, out LinkDatum = unknown> {
    acyclic(): boolean;
    connected(): boolean;
    leaves(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>;
    links(): IterableIterator<GraphLink<NodeDatum, LinkDatum>, any, any>;
    multi(): boolean;
    nlinks(): number;
    nnodes(): number;
    nodes(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>;
    roots(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>;
    split(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>;
    toJSON(): unknown;
    topological(
        rank?: Rank<NodeDatum, LinkDatum>,
    ): GraphNode<NodeDatum, LinkDatum>[];
}

Type Parameters

  • out NodeDatum = unknown
  • out LinkDatum = unknown

Hierarchy (View Summary)

Methods

acyclic connected leaves links multi nlinks nnodes nodes roots split toJSON topological

Methods

acyclic

  • acyclic(): boolean

  • true if there no cycles in the graph

    Returns boolean

connected

  • connected(): boolean

  • true if every node in the graph is reachable from every other

    Returns boolean

leaves

  • leaves(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>

  • 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<GraphNode<NodeDatum, LinkDatum>, any, any>

    Remarks

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

links

multi

  • multi(): boolean

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

    Returns boolean

nlinks

  • nlinks(): number

  • the number of links in the graph

    Returns number

nnodes

  • nnodes(): number

  • the number of nodes in the graph

    Returns number

nodes

  • nodes(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>

  • an iterator over every node in the graph

    Returns IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>

    Remarks

    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.

roots

  • roots(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>

  • 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<GraphNode<NodeDatum, LinkDatum>, any, any>

    Remarks

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

split

  • split(): IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>

  • split a graph into connected components

    Returns IterableIterator<GraphNode<NodeDatum, LinkDatum>, any, any>

    splits an iterable over a single node in each connected component

    Remarks

    Since each node behaves like a graph of its connected component, this is equivalent with returning a graph of each connected component.

toJSON

  • toJSON(): unknown

  • serialize the graph

    Returns unknown

    Remarks

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

topological

  • topological(
        rank?: Rank<NodeDatum, LinkDatum>,
    ): GraphNode<NodeDatum, LinkDatum>[]

  • 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>[]

Settings

Member Visibility

On This Page

Methods