Graphlib v0.7.3-pre

Graphlib is a JavaScript library that provides data structures for undirected and directed multi-graphs along with algorithms that can be used with them.

This documentation describes the Graphlib API. Please visit our GitHub repository for more general information.

Graph Types

There are currently four major graph types in graphlib:

Multigraphs are graphs that can contain more than one edge between the same two nodes.

Compound graphs are graphs that can have nodes that act as parents to, or containers of, other nodes.

Graph

The Graph class represents an undirected multigraph.

Subsequent examples in this section assume that Graph has been required as follows:

var Graph = require("graphlib").Graph;
var graph = new Graph();

new Graph()

Constructs a new empty Graph.

graph.order()

Returns the number of nodes in this graph. For example:

graph.order();
// => 0

graph.addNode(1);
graph.addNode(2);

graph.order();
// => 2

graph.size()

Returns the number of edges in this graph. For example:

graph.size();
// => 0

graph.addNode(1);
graph.addNode(2);
graph.addEdge(null, 1, 2);

graph.size();
// => 1

graph.isDirected()

Always returns false for Graph.

graph.graph([value])

The graph function provides a mechansim to get and set some user-defined information on the graph object itself. With no arguments graph returns the currently set value. With one argument graph replaces the current value on the graph with value. The initial value for the graph is undefined.

graph.graph();
// => undefined

graph.graph("Some graph value");
graph.graph();
// => "Some graph value"

graph.hasNode(u)

Returns true if the node with the id u is a member of this graph and false if not.

graph.hasNode(1);
// => false

graph.addNode(1);
graph.hasNode(1);
// => true

graph.node(u, [value])

The node function provides a mechanism to get and set some user-defined information on an individual node. With one argument this function returns the value currently assigned to the node with the id u. With two arguments this function replaces the current value of the node u with value. The initial value for nodes is undefined.

If there is no node u in this graph this function will throw an Error.

graph.addNode(1);
graph.node(1);
// => undefined

graph.node(1, "Some node value");
graph.node(1);
// => "Some node value"

graph.node(2);
// throws an Error

graph.nodes()

Returns the ids of all nodes in this graph. Use graph.node(u) to get the value for a specific node.

graph.nodes();
// => []

graph.addNode(1);
graph.addNode(2);

graph.nodes()
// => [1, 2]

graph.eachNode(f)

Applies the function f(u, value) to each node in this graph in arbitrary order, where u is the id of the node and value is its currently assigned value.

graph.addNode(1, "label-1");
graph.addNode(2, "label-2");

var results = {};
graph.eachNode(function(u, value) {
    results[u] = value;
});

results
// => { "1": "label-1", "2": "label-2" }

graph.neighbors(u)

Returns the ids of all nodes that are adjacent to the node with the id u. If u is not a member of this graph this function throws an Error.

graph.addNode(1);
graph.addNode(2);
graph.addEdge(null, 1, 2);

graph.neighbors(1);
// => [2]

graph.neighbors(2);
// => [1]

graph.hasEdge(e)

Returns true if an edge with the id e exists in this graph or false if not.

graph.hasEdge("A");
// => false

graph.addNode(1);
graph.addNode(2);
graph.addEdge("A", 1, 2);
graph.hasEdge("A");
// => true

graph.edge(e, [value])

The edge function provides a mechanism to get and set some user-defined information on an individual edge. With one argument this function returns the value currently assigned to the edge with the id e. With two arguments this function replaces the current value of the edge e with value. The initial value for edges is undefined.

If there is no edge e in the graph this function will throw an Error.

graph.addNode(1);
graph.addNode(2);
graph.edge("A", 1, 2);
// => undefined

graph.edge("A", "Some edge value");
graph.edge("A");
// => "Some edge value"

graph.edge("B");
// throws an Error

graph.edges()

Returns the ids of all edges in this graph. Use graph.edge(e) to get the value for a specific edge.

graph.addNode(1);
graph.addNode(2);
graph.addEdge("A", 1, 2);
graph.addEdge("B", 1, 2);
graph.edges();
// => ["A", "B"]

graph.eachEdge(f)

Applies the function f(e, u, v, value) to each edge in the graph in arbitrary order, where e is the edge's id, u and v are the incident node ids, and value it the value assigned to the edge.

graph.addNode(1);
graph.addNode(2);
graph.addEdge("A", 1, 2, "A-label");
graph.addEdge("B", 2, 1, "B-label");

var results = {};
graph.eachEdge(function(e, u, v, label) {
    results[e] = "U: " + u + " V: " + v + " L: " + label;
});

results
// => { "A": "U: 1 V: 2 L: A-label",
//      "B": "U: 2 V: 1 L: B-label" }

graph.incidentNodes(e)

Returns the nodes that are a part of the edge e in a 2-element array. There is no significance to the order in which the nodes appear in the array.

graph.addNode(1);
graph.addNode(2);
graph.addEdge("A", 1, 2);
graph.incidentNodes("A");
// => [ 1, 2 ]

graph.incidentEdges(u, [v])

Returns an arrray of ids for all edges in this graph that are incident on the node u. If the node u is not in this graph this function raises an Error.

Optionally the id of another node, v, may be be specified. This causes the results to be filtered such that only edges between u and v are included in the returned array. If the node v is specified but not a member of this graph this function raises an Error.

graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addEdge("A", 1, 2);
graph.addEdge("B", 2, 3);
graph.addEdge("C", 3, 1);
graph.addEdge("D", 3, 2);

graph.incidentEdges(3);
// => [ "B", "C", "D" ]

graph.inEdges(3, 2);
// => [ "B", "D" ]

graph.addNode(u, [value])

Adds a new node with the id u to this graph. The node u is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If u is null then a unique id is assigned to the node and returned by this function. If a node with the id u is already a member of this graph this function throws an Error.

After the node has been added, its value can be read and updated using graph.node(u, [value]).

graph.delNode(u)

Removes a node from this graph that has the id u. Any edges incident on the node u are also removed. If this graph does not contain a node u then this function will raise an Error.

graph.addEdge([e], u, v, [value])

Adds a new edge to this graph with the id e between a node with the id u and a node with the id v. The edge e is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If e is null this graph will assign an arbitrary id to the edge. This function returns the id of the edge. It will throw an Error if u or v are not members of this graph or if e is already a member of this graph.

After the edge has been added, its value can be read and updated using graph.edge(e, [value]).

graph.delEdge(e)

Removes an edge in this graph with the id e. If no edge in this graph has the id e this function will thrown an Error.

graph.copy()

Creates a new Graph that contains all of the nodes and edges from this graph.

graph.filterNodes(f)

Applies the function f(u, value) to each node in this graph and returns a new Graph that only includes those nodes for which f returns true. Edges that have both incident nodes in the new graph are also copied to the new graph.

function filter(u) { return u === 1 || u === 2; }

graph.addNode(1, "node-1");
graph.addNode(2, "node-2");
graph.addNode(3, "node-3");
graph.addEdge(null, 1, 2, "edge-1-2");
graph.addEdge(null, 2, 3, "edge-2-3");

var copy = graph.filterNodes(filter);
copy.nodes();
// => [1, 2]

copy.node(1);
// => "node-1"

copy.neighbors(2);
// => [1]

graph.toDigraph()

Returns a new directed graph using the nodes and edge from this graph. The new graph will have the same nodes, but will have twice the number of edges: each edge is split into edges pointing in opposite directions. Edge ids, consequently, are not preserved by this transformation.

graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addEdge(null, 1, 2);
graph.addEdge(null, 2, 3);
graph.size();
// => 3

var digraph = graph.toDigraph();
digraph instanceof Digraph;
// => true

digraph.nodes();
// => [ 1, 2, 3 ]

digraph.size();
// => 6 /* twice the number of edges */

digraph.successors(2);
// => [ 1, 3 ]

digraph.edges();
// => [ "_ANON-1", "_ANON-2", "_ANON-3", "_ANON-4" ]

Digraph

The Digraph class represents a directed multigraph.

Subsequent examples in this section assume that Digraph has been required as follows:

var Digraph = require("graphlib").Digraph;
var digraph = new Digraph();

new Digraph()

Constructs a new empty Digraph.

digraph.order()

Returns the number of nodes in this digraph. For example:

digraph.order();
// => 0

digraph.addNode(1);
digraph.addNode(2);

digraph.order();
// => 2

digraph.size()

Returns the number of edges in this digraph. For example:

digraph.size();
// => 0

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge(null, 1, 2);

digraph.size();
// => 1

digraph.isDirected()

Always returns true for Digraph.

digraph.graph([value])

The graph function provides a mechansim to get and set some user-defined information on the digraph object itself. With no arguments graph returns the currently set value. With one argument graph replaces the current value on the graph with value. The initial value for the graph is undefined.

digraph.graph();
// => undefined

digraph.graph("Some graph value");
digraph.graph();
// => "Some graph value"

digraph.hasNode(u)

Returns true if the node with the id u is a member of this digraph and false if not.

digraph.hasNode(1);
// => false

digraph.addNode(1);
digraph.hasNode(1);
// => true

digraph.node(u, [value])

The node function provides a mechanism to get and set some user-defined information on an individual node. With one argument this function returns the value currently assigned to the node with the id u. With two arguments this function replaces the current value of the node u with value. The initial value for nodes is undefined.

If there is no node u in this digraph this function will throw an Error.

digraph.addNode(1);
digraph.node(1);
// => undefined

digraph.node(1, "Some node value");
digraph.node(1);
// => "Some node value"

digraph.node(2);
// throws an Error

digraph.nodes()

Returns the ids of all nodes in this digraph. Use digraph.node(u) to get the value for a specific node.

digraph.nodes();
// => []

digraph.addNode(1);
digraph.addNode(2);

digraph.nodes()
// => [1, 2]

digraph.eachNode(f)

Applies the function f(u, value) to each node in this digraph in arbitrary order, where u is the id of the node and value is its currently assigned value.

digraph.addNode(1, "label-1");
digraph.addNode(2, "label-2");

var results = {};
digraph.eachNode(function(u, value) {
    results[u] = value;
});

results
// => { "1": "label-1", "2": "label-2" }

digraph.successors(u)

Returns the ids of all nodes that are successors of the node with the id u. If u is not a member of this digraph this function throws an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge(null, 1, 2);

digraph.successors(1);
// => [2]

digraph.successors(2);
// => []

digraph.predecessors(u)

Returns the ids of all nodes that are predecessors of the node with the id u. If u is not a member of this digraph this function throws an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge(null, 1, 2);

digraph.predecessors(1);
// => []

digraph.predecessors(2);
// => [1]

digraph.neighbors(u)

Returns the ids of all nodes that are adjacent to the node with the id u. If u is not a member of this digraph this function throws an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge(null, 1, 2);

digraph.neighbors(1);
// => [2]

digraph.neighbors(2);
// => [1]

digraph.sources()

Returns the ids of all nodes that are in this digraph that are sources. A source in a directed graph is a node that has no in-edges.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge(null, 1, 2);

digraph.sources();
// => [1]

digraph.sinks()

Returns the ids of all nodes that are in this digraph that are sinks. A sink in a directed graph is a node that has no out-edges.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge(null, 1, 2);

digraph.sinks();
// => [2]

digraph.hasEdge(e)

Returns true if an edge with the id e exists in this digraph or false if not.

digraph.hasEdge("A");
// => false

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge("A", 1, 2);
digraph.hasEdge("A");
// => true

digraph.edge(e, [value])

The edge function provides a mechanism to get and set some user-defined information on an individual edge. With one argument this function returns the value currently assigned to the edge with the id e. With two arguments this function replaces the current value of the edge e with value. The initial value for edges is undefined.

If there is no edge e in the digraph this function will throw an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.edge("A", 1, 2);
// => undefined

digraph.edge("A", "Some edge value");
digraph.edge("A");
// => "Some edge value"

digraph.edge("B");
// throws an Error

digraph.edges()

Returns the ids of all edges in this digraph. Use digraph.edge(e) to get the value for a specific edge.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge("A", 1, 2);
digraph.addEdge("B", 1, 2);
digraph.edges();
// => ["A", "B"]

digraph.eachEdge(f)

Applies the function f(e, u, v, value) to each edge in the digraph in arbitrary order, where e is the edge's id, u and v are the incident node ids, and value it the value assigned to the edge.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge("A", 1, 2, "A-label");
digraph.addEdge("B", 2, 1, "B-label");

var results = {};
digraph.eachEdge(function(e, u, v, label) {
    results[e] = "U: " + u + " V: " + v + " L: " + label;
});

results
// => { "A": "U: 1 V: 2 L: A-label",
//      "B": "U: 2 V: 1 L: B-label" }

digraph.source(e)

Returns the source node incident on the edge with the id e. If no such edge exists in this digraph this function throws an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge("A", 1, 2);
digraph.source("A");
// => 1

digraph.target(e)

Returns the target node incident on the edge with the id e. If no such edge exists in this digraph this function throws an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge("A", 1, 2);
digraph.target("A");
// => 2

digraph.incidentNodes(e)

Returns the nodes that are a part of the edge e in a 2-element array. There is no significance to the order in which the nodes appear in the array.

digraph.addNode(1);
digraph.addNode(2);
digraph.addEdge("A", 1, 2);
digraph.incidentNodes("A");
// => [ 1, 2 ]

digraph.inEdges(target, [source])

Returns an array of ids for all edges in this digraph that have the node identified by target as their target. If the node target is not in this digraph this function raises an Error.

Optionally a node identified by source can be specified. This causes the results to be filtered such that only edges pointing from source to target are included. If the node source is specified but is not in this digraph then this function raises an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addNode(3);
digraph.addEdge("A", 1, 2);
digraph.addEdge("B", 2, 3);
digraph.addEdge("C", 3, 1);
digraph.addEdge("D", 3, 2);

digraph.inEdges(2);
// => [ "A", "D" ]

digraph.inEdges(2, 3);
// => [ "D" ]

Note that digraph.inEdges(target, source) yields the same result as digraph.outEdges(source, target).

digraph.outEdges(source, [target])

Returns an array of ids for all edges in this digraph that have the node identified by source as their source. If the node source is not in this digraph this function raises an Error.

Optionally a node identified by target can be specified. This causes the results to be filtered such that only edges pointing from source to target are included. If the node target is specified but is not in this digraph then this function raises an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addNode(3);
digraph.addEdge("A", 1, 2);
digraph.addEdge("B", 2, 3);
digraph.addEdge("C", 3, 1);
digraph.addEdge("D", 3, 2);

digraph.outEdges(3);
// => [ "C", "D" ]

digraph.inEdges(3, 2);
// => [ "D" ]

digraph.incidentEdges(u, [v])

Returns an arrray of ids for all edges in this digraph that are incident on the node u. If the node u is not in this digraph this function raises an Error.

Optionally the id of another node, v, may be be specified. This causes the results to be filtered such that only edges between u and v are included in the returned array. If the node v is specified but not a member of this digraph this function raises an Error.

digraph.addNode(1);
digraph.addNode(2);
digraph.addNode(3);
digraph.addEdge("A", 1, 2);
digraph.addEdge("B", 2, 3);
digraph.addEdge("C", 3, 1);
digraph.addEdge("D", 3, 2);

digraph.incidentEdges(3);
// => [ "B", "C", "D" ]

digraph.inEdges(3, 2);
// => [ "B", "D" ]

digraph.addNode(u, [value])

Adds a new node with the id u to this digraph. The node u is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If u is null then a unique id is assigned to the node and returned by this function. If a node with the id u is already a member of this digraph this function throws an Error.

After the node has been added, its value can be read and updated using digraph.node(u, [value]).

digraph.delNode(u)

Removes a node from this digraph that has the id u. Any edges incident on the node u are also removed. If this digraph does not contain a node u then this function will raise an Error.

digraph.addEdge([e], u, v, [value])

Adds a new edge to this digraph with the id e from a node with the id u to a node with the id v. The edge e is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If e is null this digraph will assign an arbitrary id to the edge. This function returns the id of the edge. It will throw an Error if u or v are not members of this digraph or if e is already a member of this digraph.

After the edge has been added, its value can be read and updated using digraph.edge(e, [value]).

digraph.delNode(u)

Removes a node from this digraph that has the id u. Any edges incident on the node u are also removed. If this digraph does not contain a node u then this function will raise an Error.

digraph.copy()

Creates a new Digraph that contains all of the nodes and edges from this digraph.

digraph.filterNodes(f)

Applies the function f(u, value) to each node in this digraph and returns a new Digraph that only includes those nodes for which f returns true. Edges that have both incident nodes in the new digraph are also copied to the new digraph.

function filter(u) { return u === 1 || u === 2; }

digraph.addNode(1, "node-1");
digraph.addNode(2, "node-2");
digraph.addNode(3, "node-3");
digraph.addEdge(null, 1, 2, "edge-1-2");
digraph.addEdge(null, 2, 3, "edge-2-3");

var copy = digraph.filterNodes(filter);
copy.nodes();
// => [1, 2]

copy.node(1);
// => "node-1"

copy.neighbors(2);
// => [1]

digraph.toGraph()

Returns a new undirected graph using the nodes and edge from this graph. The new graph will have the same nodes, but the edges will be made undirected. Edge ids are preserved in this transformation.

digraph.addNode(1);
digraph.addNode(2);
digraph.addNode(3);
digraph.addEdge("A", 1, 2);
digraph.addEdge("B", 2, 3);

var graph = digraph.toGraph();
graph instanceof Graph;
// => true

graph.nodes();
// => [ 1, 2, 3 ]

graph.neighbors(2);
// => [ 1, 3 ]

graph.edges();
// => [ "A", "B" ]

CGraph

The CGraph class represents a compound undirected multigraph. It differs from Graph in that its nodes can have children.

Subsequent examples in this section assume that CGraph has been required as follows:

var CGraph = require("graphlib").CGraph;
var cgraph = new CGraph();

new CGraph()

Constructs a new empty CGraph.

cgraph.parent(u, [parent])

This function returns the current parent of the node u if only one argument is supplied. If two arguments are supplied this function sets the parent of u to the node parent. If parent is null this effectively sets the parent to the root cgraph.

This function will throw an Error if either u or parent are not in this cgraph.

cgraph.addNode(1);
cgraph.parent(1);
// => null

cgraph.addNode("sg1");
cgraph.parent(1, "sg1");
cgraph.parent(1);
// => "sg1"

cgraph.children(id)

Returns the ids of all children of the with the id u. The id null can be used to get immediate children of the root cgraph.

If u is not in this cgraph this function will throw an Error.

cgraph.children(null);
// => []

cgraph.addNode(1);
cgraph.children(null);
// => [ 1 ]

g.addNode("sg1");
g.children(null);
// => [ 1, "sg1" ]

g.parent(1, "sg1");
g.children(null);
// => [ "sg1" ]]
g.children("sg1");
// => [ 1 ]

cgraph.order()

Returns the number of nodes in this cgraph. For example:

cgraph.order();
// => 0

cgraph.addNode(1);
cgraph.addNode(2);

cgraph.order();
// => 2

cgraph.size()

Returns the number of edges in this cgraph. For example:

cgraph.size();
// => 0

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.addEdge(null, 1, 2);

cgraph.size();
// => 1

cgraph.isDirected()

Always returns false for CGraph.

cgraph.graph([value])

The graph function provides a mechansim to get and set some user-defined information on the cgraph object itself. With no arguments graph returns the currently set value. With one argument graph replaces the current value on the graph with value. The initial value for the graph is undefined.

cgraph.graph();
// => undefined

cgraph.graph("Some graph value");
cgraph.graph();
// => "Some graph value"

cgraph.hasNode(u)

Returns true if the node with the id u is a member of this cgraph and false if not.

cgraph.hasNode(1);
// => false

cgraph.addNode(1);
cgraph.hasNode(1);
// => true

cgraph.node(u, [value])

The node function provides a mechanism to get and set some user-defined information on an individual node. With one argument this function returns the value currently assigned to the node with the id u. With two arguments this function replaces the current value of the node u with value. The initial value for nodes is undefined.

If there is no node u in this cgraph this function will throw an Error.

cgraph.addNode(1);
cgraph.node(1);
// => undefined

cgraph.node(1, "Some node value");
cgraph.node(1);
// => "Some node value"

cgraph.node(2);
// throws an Error

cgraph.nodes()

Returns the ids of all nodes in this cgraph. Use cgraph.node(u) to get the value for a specific node.

cgraph.nodes();
// => []

cgraph.addNode(1);
cgraph.addNode(2);

cgraph.nodes()
// => [1, 2]

cgraph.eachNode(f)

Applies the function f(u, value) to each node in this cgraph in arbitrary order, where u is the id of the node and value is its currently assigned value.

cgraph.addNode(1, "label-1");
cgraph.addNode(2, "label-2");

var results = {};
cgraph.eachNode(function(u, value) {
    results[u] = value;
});

results
// => { "1": "label-1", "2": "label-2" }

cgraph.neighbors(u)

Returns the ids of all nodes that are adjacent to the node with the id u. If u is not a member of this cgraph this function throws an Error.

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.addEdge(null, 1, 2);

cgraph.neighbors(1);
// => [2]

cgraph.neighbors(2);
// => [1]

cgraph.hasEdge(e)

Returns true if an edge with the id e exists in this cgraph or false if not.

cgraph.hasEdge("A");
// => false

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.addEdge("A", 1, 2);
cgraph.hasEdge("A");
// => true

cgraph.edge(e, [value])

The edge function provides a mechanism to get and set some user-defined information on an individual edge. With one argument this function returns the value currently assigned to the edge with the id e. With two arguments this function replaces the current value of the edge e with value. The initial value for edges is undefined.

If there is no edge e in the cgraph this function will throw an Error.

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.edge("A", 1, 2);
// => undefined

cgraph.edge("A", "Some edge value");
cgraph.edge("A");
// => "Some edge value"

cgraph.edge("B");
// throws an Error

cgraph.edges()

Returns the ids of all edges in this cgraph. Use cgraph.edge(e) to get the value for a specific edge.

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.addEdge("A", 1, 2);
cgraph.addEdge("B", 1, 2);
cgraph.edges();
// => ["A", "B"]

cgraph.eachEdge(f)

Applies the function f(e, u, v, value) to each edge in the cgraph in arbitrary order, where e is the edge's id, u and v are the incident node ids, and value it the value assigned to the edge.

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.addEdge("A", 1, 2, "A-label");
cgraph.addEdge("B", 2, 1, "B-label");

var results = {};
cgraph.eachEdge(function(e, u, v, label) {
    results[e] = "U: " + u + " V: " + v + " L: " + label;
});

results
// => { "A": "U: 1 V: 2 L: A-label",
//      "B": "U: 2 V: 1 L: B-label" }

cgraph.incidentNodes(e)

Returns the nodes that are a part of the edge e in a 2-element array. There is no significance to the order in which the nodes appear in the array.

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.addEdge("A", 1, 2);
cgraph.incidentNodes("A");
// => [ 1, 2 ]

cgraph.incidentEdges(u, [v])

Returns an arrray of ids for all edges in this cgraph that are incident on the node u. If the node u is not in this cgraph this function raises an Error.

Optionally the id of another node, v, may be be specified. This causes the results to be filtered such that only edges between u and v are included in the returned array. If the node v is specified but not a member of this cgraph this function raises an Error.

cgraph.addNode(1);
cgraph.addNode(2);
cgraph.addNode(3);
cgraph.addEdge("A", 1, 2);
cgraph.addEdge("B", 2, 3);
cgraph.addEdge("C", 3, 1);
cgraph.addEdge("D", 3, 2);

cgraph.incidentEdges(3);
// => [ "B", "C", "D" ]

cgraph.inEdges(3, 2);
// => [ "B", "D" ]

cgraph.addNode(u, [value])

Adds a new node with the id u to this cgraph. The node u is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If u is null then a unique id is assigned to the node and returned by this function. If a node with the id u is already a member of this cgraph this function throws an Error.

After the node has been added, its value can be read and updated using cgraph.node(u, [value]).

cgraph.delNode(u)

Removes a node from this cgraph that has the id u. Any edges incident on the node u are also removed. If this cgraph does not contain a node u then this function will raise an Error.

cgraph.addEdge([e], u, v, [value])

Adds a new edge to this cgraph with the id e between a node with the id u and a node with the id v. The edge e is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If e is null this cgraph will assign an arbitrary id to the edge. This function returns the id of the edge. It will throw an Error if u or v are not members of this cgraph or if e is already a member of this cgraph.

After the edge has been added, its value can be read and updated using cgraph.edge(e, [value]).

cgraph.delEdge(e)

Removes an edge in this cgraph with the id e. If no edge in this cgraph has the id e this function will thrown an Error.

cgraph.copy()

Creates a new CGraph that contains all of the nodes and edges from this cgraph.

cgraph.filterNodes(f)

Applies the function f(u, value) to each node in this cgraph and returns a new CGraph that only includes those nodes for which f returns true. Edges that have both incident nodes in the new cgraph are also copied to the new cgraph.

function filter(u) { return u === 1 || u === 2; }

cgraph.addNode(1, "node-1");
cgraph.addNode(2, "node-2");
cgraph.addNode(3, "node-3");
cgraph.addEdge(null, 1, 2, "edge-1-2");
cgraph.addEdge(null, 2, 3, "edge-2-3");

var copy = cgraph.filterNodes(filter);
copy.nodes();
// => [1, 2]

copy.node(1);
// => "node-1"

copy.neighbors(2);
// => [1]

CDigraph

The CDigraph class represents a compound directed multigraph. It differs from Digraph in that its nodes can have children.

Subsequent examples in this section assume that CDigraph has been required as follows:

var CDigraph = require("graphlib").CDigraph;
var cdigraph = new CDigraph();

new CDigraph()

Constructs a new empty CDigraph.

cdigraph.parent(u, [parent])

This function returns the current parent of the node u if only one argument is supplied. If two arguments are supplied this function sets the parent of u to the node parent. If parent is null this effectively sets the parent to the root cdigraph.

This function will throw an Error if either u or parent are not in this cdigraph.

cdigraph.addNode(1);
cdigraph.parent(1);
// => null

cdigraph.addNode("sg1");
cdigraph.parent(1, "sg1");
cdigraph.parent(1);
// => "sg1"

cdigraph.children(id)

Returns the ids of all children of the with the id u. The id null can be used to get immediate children of the root cdigraph.

If u is not in this cdigraph this function will throw an Error.

cdigraph.children(null);
// => []

cdigraph.addNode(1);
cdigraph.children(null);
// => [ 1 ]

g.addNode("sg1");
g.children(null);
// => [ 1, "sg1" ]

g.parent(1, "sg1");
g.children(null);
// => [ "sg1" ]]
g.children("sg1");
// => [ 1 ]

cdigraph.order()

Returns the number of nodes in this cdigraph. For example:

cdigraph.order();
// => 0

cdigraph.addNode(1);
cdigraph.addNode(2);

cdigraph.order();
// => 2

cdigraph.size()

Returns the number of edges in this cdigraph. For example:

cdigraph.size();
// => 0

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge(null, 1, 2);

cdigraph.size();
// => 1

cdigraph.isDirected()

Always returns true for CDigraph.

cdigraph.graph([value])

The graph function provides a mechansim to get and set some user-defined information on the cdigraph object itself. With no arguments graph returns the currently set value. With one argument graph replaces the current value on the graph with value. The initial value for the graph is undefined.

cdigraph.graph();
// => undefined

cdigraph.graph("Some graph value");
cdigraph.graph();
// => "Some graph value"

cdigraph.hasNode(u)

Returns true if the node with the id u is a member of this cdigraph and false if not.

cdigraph.hasNode(1);
// => false

cdigraph.addNode(1);
cdigraph.hasNode(1);
// => true

cdigraph.node(u, [value])

The node function provides a mechanism to get and set some user-defined information on an individual node. With one argument this function returns the value currently assigned to the node with the id u. With two arguments this function replaces the current value of the node u with value. The initial value for nodes is undefined.

If there is no node u in this cdigraph this function will throw an Error.

cdigraph.addNode(1);
cdigraph.node(1);
// => undefined

cdigraph.node(1, "Some node value");
cdigraph.node(1);
// => "Some node value"

cdigraph.node(2);
// throws an Error

cdigraph.nodes()

Returns the ids of all nodes in this cdigraph. Use cdigraph.node(u) to get the value for a specific node.

cdigraph.nodes();
// => []

cdigraph.addNode(1);
cdigraph.addNode(2);

cdigraph.nodes()
// => [1, 2]

cdigraph.eachNode(f)

Applies the function f(u, value) to each node in this cdigraph in arbitrary order, where u is the id of the node and value is its currently assigned value.

cdigraph.addNode(1, "label-1");
cdigraph.addNode(2, "label-2");

var results = {};
cdigraph.eachNode(function(u, value) {
    results[u] = value;
});

results
// => { "1": "label-1", "2": "label-2" }

cdigraph.successors(u)

Returns the ids of all nodes that are successors of the node with the id u. If u is not a member of this cdigraph this function throws an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge(null, 1, 2);

cdigraph.successors(1);
// => [2]

cdigraph.successors(2);
// => []

cdigraph.predecessors(u)

Returns the ids of all nodes that are predecessors of the node with the id u. If u is not a member of this cdigraph this function throws an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge(null, 1, 2);

cdigraph.predecessors(1);
// => []

cdigraph.predecessors(2);
// => [1]

cdigraph.neighbors(u)

Returns the ids of all nodes that are adjacent to the node with the id u. If u is not a member of this cdigraph this function throws an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge(null, 1, 2);

cdigraph.neighbors(1);
// => [2]

cdigraph.neighbors(2);
// => [1]

cdigraph.sources()

Returns the ids of all nodes that are in this cdigraph that are sources. A source in a directed graph is a node that has no in-edges.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge(null, 1, 2);

cdigraph.sources();
// => [1]

cdigraph.sinks()

Returns the ids of all nodes that are in this cdigraph that are sinks. A sink in a directed graph is a node that has no out-edges.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge(null, 1, 2);

cdigraph.sinks();
// => [2]

cdigraph.hasEdge(e)

Returns true if an edge with the id e exists in this cdigraph or false if not.

cdigraph.hasEdge("A");
// => false

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge("A", 1, 2);
cdigraph.hasEdge("A");
// => true

cdigraph.edge(e, [value])

The edge function provides a mechanism to get and set some user-defined information on an individual edge. With one argument this function returns the value currently assigned to the edge with the id e. With two arguments this function replaces the current value of the edge e with value. The initial value for edges is undefined.

If there is no edge e in the cdigraph this function will throw an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.edge("A", 1, 2);
// => undefined

cdigraph.edge("A", "Some edge value");
cdigraph.edge("A");
// => "Some edge value"

cdigraph.edge("B");
// throws an Error

cdigraph.edges()

Returns the ids of all edges in this cdigraph. Use cdigraph.edge(e) to get the value for a specific edge.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge("A", 1, 2);
cdigraph.addEdge("B", 1, 2);
cdigraph.edges();
// => ["A", "B"]

cdigraph.eachEdge(f)

Applies the function f(e, u, v, value) to each edge in the cdigraph in arbitrary order, where e is the edge's id, u and v are the incident node ids, and value it the value assigned to the edge.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge("A", 1, 2, "A-label");
cdigraph.addEdge("B", 2, 1, "B-label");

var results = {};
cdigraph.eachEdge(function(e, u, v, label) {
    results[e] = "U: " + u + " V: " + v + " L: " + label;
});

results
// => { "A": "U: 1 V: 2 L: A-label",
//      "B": "U: 2 V: 1 L: B-label" }

cdigraph.source(e)

Returns the source node incident on the edge with the id e. If no such edge exists in this cdigraph this function throws an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge("A", 1, 2);
cdigraph.source("A");
// => 1

cdigraph.target(e)

Returns the target node incident on the edge with the id e. If no such edge exists in this cdigraph this function throws an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge("A", 1, 2);
cdigraph.target("A");
// => 2

cdigraph.incidentNodes(e)

Returns the nodes that are a part of the edge e in a 2-element array. There is no significance to the order in which the nodes appear in the array.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addEdge("A", 1, 2);
cdigraph.incidentNodes("A");
// => [ 1, 2 ]

cdigraph.inEdges(target, [source])

Returns an array of ids for all edges in this cdigraph that have the node identified by target as their target. If the node target is not in this cdigraph this function raises an Error.

Optionally a node identified by source can be specified. This causes the results to be filtered such that only edges pointing from source to target are included. If the node source is specified but is not in this cdigraph then this function raises an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addNode(3);
cdigraph.addEdge("A", 1, 2);
cdigraph.addEdge("B", 2, 3);
cdigraph.addEdge("C", 3, 1);
cdigraph.addEdge("D", 3, 2);

cdigraph.inEdges(2);
// => [ "A", "D" ]

cdigraph.inEdges(2, 3);
// => [ "D" ]

Note that cdigraph.inEdges(target, source) yields the same result as cdigraph.outEdges(source, target).

cdigraph.outEdges(source, [target])

Returns an array of ids for all edges in this cdigraph that have the node identified by source as their source. If the node source is not in this cdigraph this function raises an Error.

Optionally a node identified by target can be specified. This causes the results to be filtered such that only edges pointing from source to target are included. If the node target is specified but is not in this cdigraph then this function raises an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addNode(3);
cdigraph.addEdge("A", 1, 2);
cdigraph.addEdge("B", 2, 3);
cdigraph.addEdge("C", 3, 1);
cdigraph.addEdge("D", 3, 2);

cdigraph.outEdges(3);
// => [ "C", "D" ]

cdigraph.inEdges(3, 2);
// => [ "D" ]

cdigraph.incidentEdges(u, [v])

Returns an arrray of ids for all edges in this cdigraph that are incident on the node u. If the node u is not in this cdigraph this function raises an Error.

Optionally the id of another node, v, may be be specified. This causes the results to be filtered such that only edges between u and v are included in the returned array. If the node v is specified but not a member of this cdigraph this function raises an Error.

cdigraph.addNode(1);
cdigraph.addNode(2);
cdigraph.addNode(3);
cdigraph.addEdge("A", 1, 2);
cdigraph.addEdge("B", 2, 3);
cdigraph.addEdge("C", 3, 1);
cdigraph.addEdge("D", 3, 2);

cdigraph.incidentEdges(3);
// => [ "B", "C", "D" ]

cdigraph.inEdges(3, 2);
// => [ "B", "D" ]

cdigraph.addNode(u, [value])

Adds a new node with the id u to this cdigraph. The node u is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If u is null then a unique id is assigned to the node and returned by this function. If a node with the id u is already a member of this cdigraph this function throws an Error.

After the node has been added, its value can be read and updated using cdigraph.node(u, [value]).

cdigraph.delNode(u)

Removes a node from this cdigraph that has the id u. Any edges incident on the node u are also removed. If this cdigraph does not contain a node u then this function will raise an Error.

cdigraph.addEdge([e], u, v, [value])

Adds a new edge to this cdigraph with the id e from a node with the id u to a node with the id v. The edge e is assigned the value of value if it is specified. Otherwise it defaults to the value undefined. If e is null this cdigraph will assign an arbitrary id to the edge. This function returns the id of the edge. It will throw an Error if u or v are not members of this cdigraph or if e is already a member of this cdigraph.

After the edge has been added, its value can be read and updated using cdigraph.edge(e, [value]).

cdigraph.delNode(u)

Removes a node from this cdigraph that has the id u. Any edges incident on the node u are also removed. If this cdigraph does not contain a node u then this function will raise an Error.

cdigraph.copy()

Creates a new CDigraph that contains all of the nodes and edges from this cdigraph.

cdigraph.filterNodes(f)

Applies the function f(u, value) to each node in this cdigraph and returns a new CDigraph that only includes those nodes for which f returns true. Edges that have both incident nodes in the new cdigraph are also copied to the new cdigraph.

function filter(u) { return u === 1 || u === 2; }

cdigraph.addNode(1, "node-1");
cdigraph.addNode(2, "node-2");
cdigraph.addNode(3, "node-3");
cdigraph.addEdge(null, 1, 2, "edge-1-2");
cdigraph.addEdge(null, 2, 3, "edge-2-3");

var copy = cdigraph.filterNodes(filter);
copy.nodes();
// => [1, 2]

copy.node(1);
// => "node-1"

copy.neighbors(2);
// => [1]

digraph.toGraph()

Returns a new undirected graph using the nodes and edge from this graph. The new graph will have the same nodes, but the edges will be made undirected. Edge ids are preserved in this transformation.

digraph.addNode(1);
digraph.addNode(2);
digraph.addNode(3);
digraph.addEdge("A", 1, 2);
digraph.addEdge("B", 2, 3);

var graph = digraph.toGraph();
graph instanceof Graph;
// => true

graph.nodes();
// => [ 1, 2, 3 ]

graph.neighbors(2);
// => [ 1, 3 ]

graph.edges();
// => [ "A", "B" ]

alg

The alg modules includes a number of algorithms that can be used with the graph classes included in graphlib. You can either get to all algorithms using var alg = require("graphlib").alg or you can get a single algorithm, e.g. topsort, using var topsort = require("graphlib").alg.topsort.

For the purposes of this section, we assume the following requires:

var alg = require("graphlib").alg;

alg.topsort(g)

An implementation of topological sorting.

Given a Digraph g this function returns an array of nodes such that for each edge u -> v, u appears before v in the array. If the graph has a cycle it is impossible to generate such a list and CycleException is thrown.

Takes O(|V| + |E|) time.

alg.topsort(digraph);
// => [ 1, 2, 3, 4 ] 
// OR
// => [ 1, 3, 2, 4 ]

alg.isAyclic(g)

Given a Digraph, g, this function returns true if the graph has no cycles and returns false if it does. This algorithm returns as soon as it detects the first cycle. You can use alg.findCycles to get the actual list of cycles in the graph.

var digraph = new Digraph();
digraph.addNode(1);
digraph.addNode(2);
digraph.addNode(3);
digraph.addEdge(null, 1, 2);
digraph.addEdge(null, 2, 3);

alg.isAcyclic(digraph);
// => true

digraph.addEdge(null, 3, 1);
alg.isAcyclic(digraph);
// => false

alg.findCycles(g)

Given a Digraph, g, this function returns all nodes that are part of a cycle. As there may be more than one cycle in a graph this function return an array of these cycles, where each cycle is itself represented by an array of ids for each node involved in that cycle. alg.isAcyclic is more efficient if you only need to determine whether a graph has a cycle or not.

var digraph = new Digraph();
digraph.addNode(1);
digraph.addNode(2);
digraph.addNode(3);
digraph.addEdge(null, 1, 2);
digraph.addEdge(null, 2, 3);

alg.findCycles(digraph);
// => []

digraph.addEdge(null, 3, 1);
alg.findCycles(digraph);
// => [ [ 3, 2, 1 ] ]

digraph.addNode(4);
digraph.addNode(5);
digraph.addEdge(null, 4, 5);
digraph.addEdge(null, 5, 4);
alg.findCycles(digraph);
// => [ [ 3, 2, 1 ], [ 5, 4 ] ]

alg.dijkstra(g, source, [weightFunc], [incidentFunc])

This function is an implementation of Dijkstra's algorithm which finds the shortest path from source to all other nodes in g. This function returns a map of u -> { distance, predecessor }. The distance property holds the sum of the weights from source to u along the shortest path or Number.POSITIVE_INFINITY if there is no path from source. The predecessor property can be used to walk the individual elements of the path from source to u in reverse order.

It takes an optional weightFunc(e) which returns the weight of the edge e. If no weightFunc is supplied then each edge is assumed to have a weight of 1. This function throws an Error if any of the traversed edges have a negative edge weight.

It takes an optional incidentFunc(u) which returns the ids of all edges incident to the node u for the purposes of shortest path traversal. By default this function uses the g.outEdges for Digraphs and g.incidentEdges for Graphs.

It takes O((|E| + |V|) * log |V|) time.

function weight(e) { return digraph.edge(e); }

alg.dijkstra(digraph, "A", weight);
// => { A: { distance: 0 },
//      B: { distance: 6, predecessor: 'C' },
//      C: { distance: 4, predecessor: 'A' },
//      D: { distance: 2, predecessor: 'A' },
//      E: { distance: 8, predecessor: 'F' },
//      F: { distance: 4, predecessor: 'D' } }

alg.dijkstraAll(g, [weightFunc], [incidentFunc])

This function finds the shortest path from each node to every other reachable node in the graph. It is similar to alg.dijkstra, but instead of returning a single-source array, it returns a mapping of of source -> alg.dijksta(g, source, weightFunc, incidentFunc).

This function takes an optional weightFunc(e) which returns the weight of the edge e. If no weightFunc is supplied then each edge is assumed to have a weight of 1. This function throws an Error if any of the traversed edges have a negative edge weight.

This function takes an optional incidentFunc(u) which returns the ids of all edges incident to the node u for the purposes of shortest path traversal. By default this function uses the outEdges function on the supplied graph.

This function takes O(|V| * (|E| + |V|) * log |V|) time.

function weight(e) { return digraph.edge(e); }

alg.dijkstraAll(digraph, weight);
// => { A:
//       { A: { distance: 0 },
//         B: { distance: 6, predecessor: 'C' },
//         C: { distance: 4, predecessor: 'A' },
//         D: { distance: 2, predecessor: 'A' },
//         E: { distance: 8, predecessor: 'F' },
//         F: { distance: 4, predecessor: 'D' } },
//      B:
//       { A: { distance: Infinity },
//         B: { distance: 0 },
//         C: { distance: Infinity },
//         D: { distance: Infinity },
//         E: { distance: 6, predecessor: 'B' },
//         F: { distance: Infinity } },
//      C: { ... },
//      D: { ... },
//      E: { ... },
//      F: { ... } }

alg.floydWarshall(g, [weightFunc], [incidentFunc])

This function is an implementation of the Floyd-Warshall algorithm, which finds the shortest path from each node to every other reachable node in the graph. It is similar to alg.dijkstraAll, but it handles negative edge weights and is more efficient for some types of graphs. This function returns a map of source -> { target -> { distance, predecessor }. The distance property holds the sum of the weights from source to target along the shortest path of Number.POSITIVE_INFINITY if there is no path from source. The predecessor property can be used to walk the individual elements of the path from source to target in reverse order.

This function takes an optional weightFunc(e) which returns the weight of the edge e. If no weightFunc is supplied then each edge is assumed to have a weight of 1.

This function takes an optional incidentFunc(u) which returns the ids of all edges incident to the node u for the purposes of shortest path traversal. By default this function uses the outEdges function on the supplied graph.

This algorithm takes O(|V|^3) time.

function weight(e) { return digraph.edge(e); }

alg.floydWarshall(digraph, weight);
// => { A:
//       { A: { distance: 0 },
//         B: { distance: 6, predecessor: 'C' },
//         C: { distance: 4, predecessor: 'A' },
//         D: { distance: 2, predecessor: 'A' },
//         E: { distance: 8, predecessor: 'F' },
//         F: { distance: 4, predecessor: 'D' } },
//      B:
//       { A: { distance: Infinity },
//         B: { distance: 0 },
//         C: { distance: Infinity },
//         D: { distance: Infinity },
//         E: { distance: 6, predecessor: 'B' },
//         F: { distance: Infinity } },
//      C: { ... },
//      D: { ... },
//      E: { ... },
//      F: { ... } }

alg.tarjan(g)

This function is an implementation of Tarjan's algorithm which finds all strongly connected components in the directed graph g. Each strongly connected component is composed of nodes that can reach all other nodes in the component via directed edges. A strongly connected component can consist of a single node if that node cannot both reach and be reached by any other specific node in the graph. Components of more than one node are guaranteed to have at least one cycle.

This function returns an array of components. Each component is itself an array that contains the ids of all nodes in the component.

alg.tarjan(digraph);
// => [ [ 'F', 'G' ],
//      [ 'H', 'D', 'C' ],
//      [ 'E', 'B', 'A' ] ]

alg.components(g)

Finds all connected components in a graph and returns an array of these components. Each component is itself an array that contains the ids of nodes in the component.

This function works with both undirected and directed graphs.

alg.components(graph);
// => [ [ 'A', 'B', 'C', 'D' ],
//      [ 'E', 'F', 'G' ],
//      [ 'H', 'I' ] ]

alg.prim(g, weightFunc)

Prim's algorithm takes a connected undirected graph and generates a minimum spanning tree. This function returns the minimum spanning tree as an undirected graph. This algorithm is derived from the description in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.

This function takes a weightFunc(e) which returns the weight of the edge e. It throws an Error if the graph is not connected.

This function takes O(|E| log |V|) time.

function weight(e) { return graph.edge(e); }
alg.prim(graph, weight);

Returns a tree (represented with a Graph) of the following form:

alg.preorder(g, root, callback)

This function performs a preorder traversal of the graph g starting at the node root. For each node visited, u, the function callback(u) is called. If the graph is a directed graph or if it does not represent a tree structure, the function will throw an error. In the latter case, some nodes may be visited before it is determined that the graph is not a tree.

alg.preorder(graph, "A");
// => One of:
// [ "A", "B", "C", "D", "E" ]
// [ "A", "B", "C", "E", "D" ]
// [ "A", "C", "D", "E", "B" ]
// [ "A", "C", "E", "D", "B" ]

alg.postorder(g, root, callback)

This function performs a postorder traversal of the graph g starting at the node root. For each node visited, u, the function callback(u) is called. If the graph is a directed graph or if it does not represent a tree structure, the function will throw an error. In the latter case, some nodes may be visited before it is determined that the graph is not a tree.

alg.postorder(graph, "A");
// => One of:
// [ "B", "D", "E", C", "A" ]
// [ "B", "E", "D", C", "A" ]
// [ "D", "E", "C", B", "A" ]
// [ "E", "D", "C", B", "A" ]

converter.json

The converter modules provide a way to convert a graph into some other form and back. Currently, we only support a JSON format. The JSON format is reversible, so the following assertion passes:

var decode = require("graphlib").converter.json.decode,
    encode = require("graphlib").converter.json.encode;

var encoded = encode(graph);
var decoded = decode(encoded.nodes, encoded.edges, encoded.type);
assert.deepEqual(graph, decoded);

converter.json.decode(nodes, edges, [Ctor])

Creates a graph of type Ctor, or Digraph if Ctor is undefined, with the given nodes and edges. Ctor may be either a constructor function or one of the strings "graph", "digraph", "cgraph", or "cdigraph".

nodes must be an array of entries of the form { [id], [value], [children] }. If id is not set then a unique id will be assigned to the node. If value is not set then the node will be assigned the undefined value. children is only used when Ctor instanceof CGraph || Ctor instanceof CDigraph and if it is set it must contain an array of node ids in the graph.

edges must be an array of entries of the form { [id], u, v, [value] }. If id is not set then a unique id will be assigned to the edge. u represents the source in a directed graph and one of the incident nodes in an undirected graph. v represents the target in a directed graph or the other incident node in a directed graph. If value is not set then the edge will be assigned the undefined value.

Here's an example of decoding a simple directed graph:

var decode = require("graphlib").converter.json.decode,
    Digraph = require("graphlib").Digraph;

var nodes = [{id: 1}, {id: 2}];
var edges = [{id: "A", u: 1, v: 2}, {id: "B", u: 2, v: 1}];
var graph = decode(nodes, edges);

graph.nodes();
// => [1, 2]

graph.edges();
// => ["A", "B"]

graph.source("A");
// => 1

graph.target("A");
// => 2

Here's an exmple of decoding a compound directed graph:

var decode = require("graphlib").converter.json.decode,
    CDigraph = require("graphlib").CDigraph;

var nodes = [{id: "sg1", children: [1, 2]},
               {id: 1},
               {id: 2}];
var graph = decode(nodes, [], CGraph);

  graph.nodes();
  // => ["sg1", 1, 2]

  graph.children(null);
  // => ["sg1"]

  graph.children("sg1");
  // => [1, 2]

converter.json.encode(graph)

This function converts the given graph into an object of the form { nodes, edges, type }. These nodes and edges act the same as the equivalent parameters for the decode function. The type property will be one of the strings "graph", "digraph", "cgraph", or "cdigraph".

var encode = require("graphlib").converter.json.encode,
    Digraph = require("graphlib").Digraph;

var graph = new Digraph();
graph.addNode(1);
graph.addNode(2, "foo");
graph.addEdge("A", 1, 2, "bar");

encode(graph);
// => { nodes: [{ id: 1, value: undefined },
//              { id: 2, value: "foo" }],
//      edges: [{ id: "A", u: 1, v: 2, value: "bar" }],
//      type: "digraph" }

Filters

The filters in the module can be used with graph.filterNodes and digraph.filterNodes. These filters are available as:

var filter = require("graphlib").filter;

filter.all()

Returns all nodes in the graph. Thus subgraph is identical in the following code blocks:

var subgraph = graph.copy();

and

var subgraph = graph.filterNode(filter.all());

filter.nodesFromList(list)

Returns true only for nodes with ids in list.