js-graph

js-graph

js-graph is a javascript library for storing arbitrary data in mathematical (di)graphs, as well as traversing and analyzing them in various ways. It was originally created to track dependencies between options and modules. It is written in ECMAScript 6, but auto-generated ECMAScript 5 versions are shipped with it.

If you want to run this library in an ECMAScript 5 context, it depends on the Babel ES6 polyfill. For your convenience, a version is provided with this polyfill already baked in, but you also have the option of providing it yourself.

Feedback of any kind (questions, issues, pull requests) is greatly appreciated.

Files

The dist directory offers different files for use in different circumstances. Use the following table to determine which file to use in your situation.

File	Description
js‑graph.es6.js	for use in an ECMAScript 6 context, e.g., a modern browser or transpiler
js‑graph.js, js‑graph.min.js	requires you to load the Babel polyfill yourself
js‑graph.full.js, js‑graph.full.min.js	already includes the Babel polyfill

If you don't know which you need, you probably want js-graph.full.min.js, because it will work out-of-the-box. But it is generally more elegant to load the polyfill yourself, especially if you use other libraries that also depend on it.

API Documentation

• JsGraph
  • instance
  • .addNewVertex(key, value)
  • .setVertex(key, value)
  • .ensureVertex(key, value)
  • .addVertex(key, value)
  • .removeExistingVertex(key)
  • .destroyExistingVertex(key)
  • .removeVertex(key)
  • .destroyVertex(key)
  • .vertexCount() ⇒ number
  • .hasVertex(key) ⇒ boolean
  • .vertexValue(key) ⇒ *
  • .addNewEdge(from, to, value)
  • .createNewEdge(from, to, value)
  • .setEdge(from, to, value)
  • .spanEdge(from, to, value)
  • .addEdge(from, to, value)
  • .ensureEdge(from, to, value)
  • .createEdge(from, to, value)
  • .removeExistingEdge(from, to)
  • .removeEdge(from, to)
  • .edgeCount() ⇒ number
  • .hasEdge(from, to) ⇒ boolean
  • .edgeValue(from, to) ⇒ *
  • .vertices() ⇒ Iterator.<string, *>
  • .@@iterator() ⇒ Iterator.<string, *>
  • .edges() ⇒ Iterator.<string, string, *>
  • .verticesFrom(from) ⇒ Iterator.<string, *, *>
  • .verticesTo(to) ⇒ Iterator.<string, *, *>
  • .verticesWithPathFrom(from) ⇒ Iterator.<string, *>
  • .verticesWithPathTo(to) ⇒ Iterator.<string, *>
  • .vertices_topologically() ⇒ Iterator.<string, *>
  • .clearEdges()
  • .clear()
  • .equals(other, [eq]) ⇒ boolean
  • .hasCycle() ⇒ boolean
  • .hasPath(from, to) ⇒ boolean
  • .clone([tr]) ⇒ JsGraph
  • .transitiveReduction([tr]) ⇒ JsGraph
  • static
  • .VertexExistsError ⇐ Error
    • .vertices : Set.<{key: string, value}>
  • .VertexNotExistsError ⇐ Error
    • .vertices : Set.<{key: string}>
  • .EdgeExistsError ⇐ Error
    • .edges : Set.<{from: string, to: string, value}>
  • .EdgeNotExistsError ⇐ Error
    • .edges : Set.<{from: string, to: string}>
  • .HasConnectedEdgesError ⇐ Error
    • .key : string
  • .CycleError ⇐ Error
    • .cycle : Array.<string>

---

JsGraph

The main class of this library, to be used for representing a mathematical (di)graph.

---

jsGraph.addNewVertex(key, value)

Add a new vertex to this graph.

Param	Type	Description
key	string	the key with which to refer to this new vertex
value	*	the value to store in this new vertex

Throws:

• VertexExistsError if a vertex with this key already exists

---

jsGraph.setVertex(key, value)

Set the value of an existing vertex in this graph.

Param	Type	Description
key	string	the key belonging to the vertex
value	*	the value to store in this vertex

Throws:

• VertexNotExistsError if a vertex with this key does not exist

---

jsGraph.ensureVertex(key, value)

Make sure a vertex with a specific key exists in this graph. If it already exists, nothing is done. If it does not yet exist, a new vertex is added with the given value.

Param	Type	Description
key	string	the key for the vertex
value	*	the value to store if a new vertex is added

---

jsGraph.addVertex(key, value)

Add a new vertex to this graph. If a vertex with this key already exists, the value of that vertex is overwritten.

Param	Type	Description
key	string	the key with which to refer to this new vertex
value	*	the value to store in this new vertex

---

jsGraph.removeExistingVertex(key)

Remove an existing vertex from this graph.

Param	Type	Description
key	string	the key of the vertex to remove

Throws:

• VertexNotExistsError if a vertex with this key does not exist
• HasConnectedEdgesError if there are still edges connected to this vertex

---

jsGraph.destroyExistingVertex(key)

Remove an existing vertex from this graph, as well as all edges connected to it.

Param	Type	Description
key	string	the key of the vertex to remove

Throws:

• VertexNotExistsError if a vertex with this key does not exist

---

jsGraph.removeVertex(key)

Remove an existing vertex from this graph. If a vertex with this key does not exist, nothing happens.

Param	Type	Description
key	string	the key of the vertex to remove

Throws:

• HasConnectedEdgesError if there are still edges connected to this vertex

---

jsGraph.destroyVertex(key)

Remove a vertex from this graph, as well as all edges connected to it. If a vertex with this key does not exist, nothing happens.

Param	Type	Description
key	string	the key of the vertex to remove

---

jsGraph.vertexCount() ⇒ number

Returns: number - the number of vertices in the whole graph

---

jsGraph.hasVertex(key) ⇒ boolean

Ask whether a vertex with a given key exists.

Param	Type	Description
key	string	the key to query

Returns: boolean - whether there is a vertex with the given key

---

jsGraph.vertexValue(key) ⇒ *

Get the value associated with the vertex of a given key.

Param	Type	Description
key	string	the key to query

Returns: * - the value associated with the vertex of the given key. Note that a return value of undefined can mean

1. that there is no such vertex, or
2. that the stored value is actually undefined.

Use hasVertex to distinguish these cases.

---

jsGraph.addNewEdge(from, to, value)

Add a new edge to this graph.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex
value	*	the value to store in this new edge

Throws:

• EdgeExistsError if an edge between from and to already exists
• VertexNotExistsError if the from and/or to vertices do not yet exist in the graph

---

jsGraph.createNewEdge(from, to, value)

Add a new edge to this graph. If the from and/or to vertices do not yet exist in the graph, they are implicitly added with an undefined value.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex
value	*	the value to store in this new edge

Throws:

• EdgeExistsError if an edge between from and to already exists

---

jsGraph.setEdge(from, to, value)

Set the value of an existing edge in this graph.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex
value	*	the value to store in this edge

Throws:

• EdgeNotExistsError if an edge between from and to does not yet exist

---

jsGraph.spanEdge(from, to, value)

Make sure an edge between the from and to vertices in this graph. If one already exists, nothing is done. If one does not yet exist, a new edge is added with the given value.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex
value	*	the value to store if a new edge is added

Throws:

• VertexNotExistsError if the from and/or to vertices do not yet exist in the graph

---

jsGraph.addEdge(from, to, value)

Add a new edge to this graph. If an edge between from and to already exists, the value of that edge is overwritten.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex
value	*	the value to store in this new edge

Throws:

• VertexNotExistsError if the from and/or to vertices do not yet exist in the graph

---

jsGraph.ensureEdge(from, to, value)

Make sure an edge between the from and to vertices exists in this graph. If it already exists, nothing is done. If it does not yet exist, a new edge is added with the given value. If the from and/or to vertices do not yet exist in the graph, they are implicitly added with an undefined value.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex
value	*	the value to store if a new edge is added

---

jsGraph.createEdge(from, to, value)

Add a new edge to this graph. If an edge between the from and to vertices already exists, the value of that edge is overwritten. If the from and/or to vertices do not yet exist in the graph, they are implicitly added with an undefined value.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex
value	*	the value to store if a new edge is added

---

jsGraph.removeExistingEdge(from, to)

Remove an existing edge from this graph.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex

Throws:

• EdgeNotExistsError if an edge between the from and to vertices doesn't exist

---

jsGraph.removeEdge(from, to)

Remove an edge from this graph. If an edge between the from and to vertices doesn't exist, nothing happens.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex

---

jsGraph.edgeCount() ⇒ number

Returns: number - the number of edges in the whole graph

---

jsGraph.hasEdge(from, to) ⇒ boolean

Ask whether an edge between given from and to vertices exist.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex

Returns: boolean - whether there is an edge between the given from and to vertices

---

jsGraph.edgeValue(from, to) ⇒ *

Get the value associated with the edge between given from and to vertices.

Param	Type	Description
from	string	the key for the originating vertex
to	string	the key for the terminating vertex

Returns: * - the value associated with the edge between the given from and to vertices Note that a return value of undefined can mean

1. that there is no such edge, or
2. that the stored value is actually undefined.

Use hasEdge to distinguish these cases.

---

jsGraph.vertices() ⇒ Iterator.<string, *>

Iterate over all vertices of the graph, in no particular order.

Returns: Iterator.<string, *> - an object conforming to the ES6 iterator protocol
Example

for (var it = jsGraph.vertices(), keyVal = it.next(); !it.done;) {
    var key   = keyVal[0],
        value = keyVal[1];
    // iterates over all vertices of the graph
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [key, value] of jsGraph.vertices()) {
    // iterates over all vertices of the graph
}

See: @@iterator

---

jsGraph.@@iterator() ⇒ Iterator.<string, *>

A JsGraph object is itself iterable, and serves as a short notation in ECMAScript 6 to iterate over all vertices in the graph, in no particular order.

Returns: Iterator.<string, *> - an object conforming to the ES6 iterator protocol
Example

for (let [key, value] of jsGraph) {
    // iterates over all vertices of the graph
}

See: vertices

---

jsGraph.edges() ⇒ Iterator.<string, string, *>

Iterate over all edges of the graph, in no particular order.

Returns: Iterator.<string, string, *> - an object conforming to the ES6 iterator protocol
Example

for (var it = jsGraph.edges(), fromToVal = it.next(); !it.done;) {
    var from  = fromToVal[0],
        to    = fromToVal[1],
        value = fromToVal[2];
    // iterates over all edges of the graph
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [from, to, value] of jsGraph.edges()) {
    // iterates over all vertices of the graph
}

---

jsGraph.verticesFrom(from) ⇒ Iterator.<string, *, *>

Iterate over the outgoing edges of a given vertex in the graph, in no particular order.

Param	Type	Description
from	string	the key of the vertex to take the outgoing edges from

Throws:

• VertexNotExistsError if a vertex with the given from key does not exist

Returns: Iterator.<string, *, *> - an object conforming to the ES6 iterator protocol
Example

for (var it = jsGraph.verticesFrom(from), toVertexEdge = it.next(); !it.done;) {
    var to          = toVertexEdge[0],
        vertexValue = toVertexEdge[1],
        edgeValue   = toVertexEdge[2];
    // iterates over all outgoing vertices of the `from` vertex
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [to, vertexValue, edgeValue] of jsGraph.verticesFrom(from)) {
    // iterates over all outgoing edges of the `from` vertex
}

---

jsGraph.verticesTo(to) ⇒ Iterator.<string, *, *>

Iterate over the incoming edges of a given vertex in the graph, in no particular order.

Param	Type	Description
to	string	the key of the vertex to take the incoming edges from

Throws:

• VertexNotExistsError if a vertex with the given to key does not exist

Returns: Iterator.<string, *, *> - an object conforming to the ES6 iterator protocol
Example

for (var it = jsGraph.verticesTo(to), fromVertexEdge = it.next(); !it.done;) {
    var from        = fromVertexEdge[0],
        vertexValue = fromVertexEdge[1],
        edgeValue   = fromVertexEdge[2];
    // iterates over all outgoing vertices of the `from` vertex
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [from, vertexValue, edgeValue] of jsGraph.verticesTo(to)) {
    // iterates over all incoming edges of the `to` vertex
}

---

jsGraph.verticesWithPathFrom(from) ⇒ Iterator.<string, *>

Iterate over all vertices reachable from a given vertex in the graph, in no particular order.

Param	Type	Description
from	string	the key of the vertex to take the reachable vertices from

Throws:

• VertexNotExistsError if a vertex with the given from key does not exist

Returns: Iterator.<string, *> - an object conforming to the ES6 iterator protocol
Example

for (var it = jsGraph.verticesWithPathFrom(from), keyValue = it.next(); !it.done;) {
    var key   = keyValue[0],
        value = keyValue[1];
    // iterates over all vertices reachable from `from`
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [key, value] of jsGraph.verticesWithPathFrom(from)) {
    // iterates over all vertices reachable from `from`
}

---

jsGraph.verticesWithPathTo(to) ⇒ Iterator.<string, *>

Iterate over all vertices from which a given vertex in the graph can be reached, in no particular order.

Param	Type	Description
to	string	the key of the vertex to take the reachable vertices from

Throws:

• VertexNotExistsError if a vertex with the given to key does not exist

Returns: Iterator.<string, *> - an object conforming to the ES6 iterator protocol
Example

for (var it = jsGraph.verticesWithPathTo(to), keyValue = it.next(); !it.done;) {
    var key   = keyValue[0],
        value = keyValue[1];
    // iterates over all vertices from which `to` can be reached
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [key, value] of jsGraph.verticesWithPathTo(to)) {
    // iterates over all vertices from which `to` can be reached
}

---

jsGraph.vertices_topologically() ⇒ Iterator.<string, *>

Iterate over all vertices of the graph in topological order.

Returns: Iterator.<string, *> - an object conforming to the ES6 iterator protocol
Example

for (var it = jsGraph.vertices_topologically(), keyVal = it.next(); !it.done;) {
    var key   = keyVal[0],
        value = keyVal[1];
    // iterates over all vertices of the graph in topological order
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [key, value] of jsGraph.vertices_topologically()) {
    // iterates over all vertices of the graph in topological order
}

---

jsGraph.clearEdges()

Remove all edges from the graph, but leave the vertices intact.

---

jsGraph.clear()

Remove all edges and vertices from the graph, putting it back in its initial state.

---

jsGraph.equals(other, [eq]) ⇒ boolean

Ask whether this graph and another graph are equal. Two graphs are equal if they have the same vertices and the same edges.

Param	Type	Description
other	JsGraph	the other graph to compare this one to
[eq]	function	a custom equality function for stored values; defaults to === comparison; The first two arguments are the two values to compare. If they are vertex values, the third argument is the vertex key. If they are edge values, the third and fourth argument are the from and to keys respectively. (So you can test the fourth argument to distinguish the two cases.)

Returns: boolean - true if the two graphs are equal; false otherwise

---

jsGraph.hasCycle() ⇒ boolean

Test whether the graph contains a directed cycle.

Returns: boolean - false, if there is no cycle; a truthy value if there is a cycle (not necessarily true; future versions of the library might return a description of the cycle)

---

jsGraph.hasPath(from, to) ⇒ boolean

Test whether there is a directed path between a given pair of keys.

Param	Type	Description
from	string	the originating vertex
to	string	the terminating vertex

Returns: boolean - false, if there is no such path; a truthy value if there is such a path (not necessarily true; future versions of the library might return a description of the path)

---

jsGraph.clone([tr]) ⇒ JsGraph

Create a clone of this graph.

Param	Type	Description
[tr]	function	a custom transformation function for stored values; defaults to the identity function; The first argument is the value to clone. If it is a vertex value, the third argument is the vertex key. If it is an edge value, the third and fourth argument are the from and to keys respectively. (So you can test the fourth argument to distinguish the two cases.)

Returns: JsGraph - a clone of this graph

---

jsGraph.transitiveReduction([tr]) ⇒ JsGraph

Create a clone of this graph, but without any transitive edges.

Param	Type	Description
[tr]	function	a custom transformation function for stored values; defaults to the identity function; The first argument is the value to clone. If it is a vertex value, the third argument is the vertex key. If it is an edge value, the third and fourth argument are the from and to keys respectively. (So you can test the fourth argument to distinguish the two cases.)

Returns: JsGraph - a clone of this graph

---

JsGraph.VertexExistsError ⇐ Error

This type of error is thrown when specific vertices are expected not to exist, but do.

Extends: Error

---

vertexExistsError.vertices : Set.<{key: string, value}>

the set of relevant vertices

---

JsGraph.VertexNotExistsError ⇐ Error

This type of error is thrown when specific vertices are expected to exist, but don't.

Extends: Error

---

vertexNotExistsError.vertices : Set.<{key: string}>

the set of relevant vertices

---

JsGraph.EdgeExistsError ⇐ Error

This type of error is thrown when specific edges are expected not to exist, but do.

Extends: Error

---

edgeExistsError.edges : Set.<{from: string, to: string, value}>

the set of relevant edges

---

JsGraph.EdgeNotExistsError ⇐ Error

This type of error is thrown when specific edges are expected to exist, but don't.

Extends: Error

---

edgeNotExistsError.edges : Set.<{from: string, to: string}>

the set of relevant edges

---

JsGraph.HasConnectedEdgesError ⇐ Error

This type of error is thrown when a vertex is expected not to have connected edges, but does.

Extends: Error

---

hasConnectedEdgesError.key : string

the key of the relevant vertex

---

JsGraph.CycleError ⇐ Error

This type of error is thrown when a graph is expected not to have a directed cycle, but does.

Extends: Error

---

cycleError.cycle : Array.<string>

the vertices involved in the cycle

---