# 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:

`Graph`

represents an undirected multigraph`Digraph`

represents a directed multigraph`CGraph`

represents a compound undirected multigraph`CDigraph`

represents a compound directed multigraph

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])

`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])

`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)

`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`

.