graph.js

2019-07-21 admin

graph.js是什么

什么是graph.js,a javascript library for storing arbitrary data in mathematical (di)graphs, as well as traversing and analyzing them in various ways (ECMAScript 6 Ready)

graph.js使用教程帮助文档

graph.js

Build Status Coverage Status npm Bower

formerly known as js-graph

graph.js 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.

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

Installing graph.js

When running in an ECMAScript 5 environment, this library depends on the Babel ES6 polyfill. For your convenience, a standalone version of graph.js is available, which has the polyfill already baked in.

graph.js is available from NPM and Bower:

npm install graph.js --save
bower install graph.js --save

The Babel polyfill is not distributed through Bower. So Bower users have to either use the standalone version of graph.js, or get the polyfill from someplace else, like NPM.

Loading graph.js

The graph.js library supports all popular module systems: ECMAScript 6, CommonJS (Node.js, IO.js, browserify, webpack), AMD (RequireJS), and good old-fashioned HTML script tags.

import Graph from 'graph.js'; // the ES6 version is default
// use Graph
var Graph = require('graph.js/dist/graph.full.js');
// use Graph
requirejs(['graph.js/dist/graph.full.js'], function (Graph) {
    // use Graph
});
<script src="graph.js/dist/graph.full.js"></script>
<script>
    // use Graph
</script>

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
graph.es6.js for use in an ECMAScript 6 context, e.g., a modern browser or transpiler
graph.js,
graph.min.js requires you to load the Babel polyfill yourself
graph.full.js,
graph.full.min.js already includes the Babel polyfill

If you don’t know which you need, you probably want graph.full.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

  • Graph
    • new Graph(…parts)
    • <ins>instance</ins>
    • .on(event, handler)
    • .off(event, handler)
    • .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, *>
    • .sources() ⇒ Iterator.<string, *>
    • .sinks() ⇒ Iterator.<string, *>
    • .vertices_topologically() ⇒ Iterator.<string, *>
    • .clearEdges()
    • .clear()
    • .equals(other, [eqV], [eqE]) ⇒ boolean
    • .cycles() ⇒ Iterator.<Array.<string>>
    • .cycle() ⇒ Array
    • .hasCycle() ⇒ boolean
    • .paths(from, to) ⇒ Iterator.<Array.<string>>
    • .path(from, to) ⇒ Array
    • .hasPath(from, to) ⇒ boolean
    • .outDegree(key) ⇒ number
    • .inDegree(key) ⇒ number
    • .degree(key) ⇒ number
    • .mergeIn(other, [mV], [mE])
    • .clone([trV], [trE]) ⇒ Graph
    • .transitiveReduction([trV], [trE]) ⇒ Graph
    • .contractPaths([isNexus])
    • .toJSON()
    • “vertex-added”
    • “vertex-removed”
    • “vertex-modified”
    • “edge-added”
    • “edge-removed”
    • “edge-modified”
    • <ins>static</ins>
    • .fromJSON()
    • .VertexExistsError ⇐ Error
      • .vertices : Set.<Array>
    • .VertexNotExistsError ⇐ Error
      • .vertices : Set.<string>
    • .EdgeExistsError ⇐ Error
      • .edges : Set.<Array>
    • .EdgeNotExistsError ⇐ Error
      • .edges : Set.<Array.<string>>
    • .HasConnectedEdgesError ⇐ EdgeExistsError
      • .vertex : string
      • .edges : Set.<Array>
    • .CycleError ⇐ Error
      • .cycle : Array.<string>
    • .BranchlessCycleError ⇐ CycleError
      • .cycle : Array.<string>

<a name=“user-content-graph”></a>

Graph

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


<a name=“user-content-new_graph_new”></a>

new Graph(…parts)

Constructor arguments can be used to supply initial vertices and edges.

Param Type Description
…parts Array.<Array> a short notation for vertices and edges to initially add to the graph; A vertex should be an array of the form [key, value]. An edge should be an array of the form [[from, to], value]. Later values of vertices or edges in this list will overwrite earlier values, but vertices need not precede their edges. Vertices that are connected but store no value need not be listed at all.

Example

var map = new Graph(
    ['Amsterdam',             { population: 825000 }], // vertex
    ['Leiden',                { population: 122000 }], // vertex
    [['Amsterdam', 'Leiden'], { distance:   "40km" }]  // edge
);

<a name=“user-content-graph+on”></a>

graph.on(event, handler)

Register an event handler.

Param Type Description
event string the event to listen for
handler function the function to call for each such event fired, receiving its corresponding value

<a name=“user-content-graph+off”></a>

graph.off(event, handler)

Deregister a previously registered event handler.

Param Type Description
event string the event used to originally register a handler
handler function the handler originally registered

<a name=“user-content-graph+addnewvertex”></a>

graph.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

<a name=“user-content-graph+setvertex”></a>

graph.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

<a name=“user-content-graph+ensurevertex”></a>

graph.ensureVertex(key, [value])

Make sure a vertex with a specific key exists in this graph. If it already exists, do nothing. If it does not yet exist, add a new vertex 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

<a name=“user-content-graph+addvertex”></a>

graph.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

<a name=“user-content-graph+removeexistingvertex”></a>

graph.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

<a name=“user-content-graph+destroyexistingvertex”></a>

graph.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

<a name=“user-content-graph+removevertex”></a>

graph.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

<a name=“user-content-graph+destroyvertex”></a>

graph.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

<a name=“user-content-graph+vertexcount”></a>

graph.vertexCount() ⇒ number

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


<a name=“user-content-graph+hasvertex”></a>

graph.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


<a name=“user-content-graph+vertexvalue”></a>

graph.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.


<a name=“user-content-graph+addnewedge”></a>

graph.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

<a name=“user-content-graph+createnewedge”></a>

graph.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

<a name=“user-content-graph+setedge”></a>

graph.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

<a name=“user-content-graph+spanedge”></a>

graph.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

<a name=“user-content-graph+addedge”></a>

graph.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

<a name=“user-content-graph+ensureedge”></a>

graph.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

<a name=“user-content-graph+createedge”></a>

graph.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

<a name=“user-content-graph+removeexistingedge”></a>

graph.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

<a name=“user-content-graph+removeedge”></a>

graph.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

<a name=“user-content-graph+edgecount”></a>

graph.edgeCount() ⇒ number

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


<a name=“user-content-graph+hasedge”></a>

graph.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


<a name=“user-content-graph+edgevalue”></a>

graph.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.


<a name=“user-content-graph+vertices”></a>

graph.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 = graph.vertices(), kv; !(kv = it.next()).done;) {
    var key   = kv.value[0],
        value = kv.value[1];
    // iterates over all vertices of the graph
}

Example

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

See: @@iterator


<a name=“user-content-graph+@@iterator”></a>

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

A Graph 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 graph) {
    // iterates over all vertices of the graph
}

See: vertices


<a name=“user-content-graph+edges”></a>

graph.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 = graph.edges(), kv; !(kv = it.next()).done;) {
    var from  = kv.value[0],
        to    = kv.value[1],
        value = kv.value[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 graph.edges()) {
    // iterates over all vertices of the graph
}

<a name=“user-content-graph+verticesfrom”></a>

graph.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 = graph.verticesFrom(from), kv; !(kv = it.next()).done;) {
    var to          = kv.value[0],
        vertexValue = kv.value[1],
        edgeValue   = kv.value[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 graph.verticesFrom(from)) {
    // iterates over all outgoing edges of the `from` vertex
}

<a name=“user-content-graph+verticesto”></a>

graph.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 = graph.verticesTo(to), kv; !(kv = it.next()).done;) {
    var from        = kv.value[0],
        vertexValue = kv.value[1],
        edgeValue   = kv.value[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 graph.verticesTo(to)) {
    // iterates over all incoming edges of the `to` vertex
}

<a name=“user-content-graph+verticeswithpathfrom”></a>

graph.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 = graph.verticesWithPathFrom(from), kv; !(kv = it.next()).done;) {
    var key   = kv.value[0],
        value = kv.value[1];
    // iterates over all vertices reachable from `from`
}

Example

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

<a name=“user-content-graph+verticeswithpathto”></a>

graph.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 = graph.verticesWithPathTo(to), kv; !(kv = it.next()).done;) {
    var key   = kv.value[0],
        value = kv.value[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 graph.verticesWithPathTo(to)) {
    // iterates over all vertices from which `to` can be reached
}

<a name=“user-content-graph+sources”></a>

graph.sources() ⇒ Iterator.<string, *>

Iterate over all vertices that have no incoming edges, in no particular order.

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

for (var it = graph.sources(), kv; !(kv = it.next()).done;) {
    var key   = kv.value[0],
        value = kv.value[1];
    // iterates over all vertices with no incoming edges
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [key, value] of graph.sources()) {
    // iterates over all vertices with no incoming edges
}

<a name=“user-content-graph+sinks”></a>

graph.sinks() ⇒ Iterator.<string, *>

Iterate over all vertices that have no outgoing edges, in no particular order.

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

for (var it = graph.sinks(), kv; !(kv = it.next()).done;) {
    var key   = kv.value[0],
        value = kv.value[1];
    // iterates over all vertices with no outgoing edges
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let [key, value] of graph.sinks()) {
    // iterates over all vertices with no outgoing edges
}

<a name=“user-content-graph+vertices_topologically”></a>

graph.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 = graph.vertices_topologically(), kv; !(kv = it.next()).done;) {
    var key   = kv.value[0],
        value = kv.value[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 graph.vertices_topologically()) {
    // iterates over all vertices of the graph in topological order
}

<a name=“user-content-graph+clearedges”></a>

graph.clearEdges()

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


<a name=“user-content-graph+clear”></a>

graph.clear()

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


<a name=“user-content-graph+equals”></a>

graph.equals(other, [eqV], [eqE]) ⇒ boolean

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

Param Type Description
other Graph the other graph to compare to this one
[eqV] function a custom equality function for values stored in vertices; defaults to === comparison; The first two arguments are the values to compare. The third is the corresponding key.
[eqE] function a custom equality function for values stored in edges; defaults to the function given for trV; The first two arguments are the values to compare. The third and fourth are the from and to keys respectively.

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


<a name=“user-content-graph+cycles”></a>

graph.cycles() ⇒ Iterator.<Array.<string>>

Iterate over all simple directed cycles in this graph, in no particular order. If you mutate the graph in between iterations, behavior of the iterator becomes unspecified. (So, don’t.)

Returns: Iterator.<Array.<string>> - an object conforming to the ES6 iterator protocol. Each iterated value is an array containing the vertex keys describing the cycle. These arrays will contain each vertex key only once — even the first/last one. Example

for (var it = graph.cycles(), kv; !(kv = it.next()).done;) {
    var cycle = kv.value;
    // iterates over all cycles of the graph
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let cycle of graph.cycles()) {
    // iterates over all cycles of the graph
}

<a name=“user-content-graph+cycle”></a>

graph.cycle() ⇒ Array

Find any directed cycle in this graph.

Returns: Array - an array containing the vertex keys describing the cycle; null, if there is no cycle; The array will contain each vertex key only once — even the first/last one.


<a name=“user-content-graph+hascycle”></a>

graph.hasCycle() ⇒ boolean

Test whether this graph contains a directed cycle.

Returns: boolean - whether this graph contains any directed cycle


<a name=“user-content-graph+paths”></a>

graph.paths(from, to) ⇒ Iterator.<Array.<string>>

Iterate over all paths between two given keys in this graph, in no particular order. If you mutate the graph in between iterations, behavior of the iterator becomes unspecified. (So, don’t.)

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

Throws:

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

Returns: Iterator.<Array.<string>> - an object conforming to the ES6 iterator protocol. Each iterated value is an array containing the vertex-keys describing the path. Example

for (var it = graph.paths(), kv; !(kv = it.next()).done;) {
    var path = kv.value;
    // iterates over all paths between `from` and `to` in the graph
}

Example

// in ECMAScript 6, you can use a for..of loop
for (let path of graph.paths()) {
    // iterates over all paths between `from` and `to` in the graph
}

<a name=“user-content-graph+path”></a>

graph.path(from, to) ⇒ Array

Find any path between a given pair of keys.

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

Throws:

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

Returns: Array - an array with the keys of the path found between the two vertices, including those two vertices themselves; null if no such path exists


<a name=“user-content-graph+haspath”></a>

graph.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

Throws:

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

Returns: boolean - whether such a path exists


<a name=“user-content-graph+outdegree”></a>

graph.outDegree(key) ⇒ number

Get the number of edges going out of a given vertex.

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

Throws:

  • VertexNotExistsError if a vertex with this key does not exist

Returns: number - the number of edges going out of the key vertex


<a name=“user-content-graph+indegree”></a>

graph.inDegree(key) ⇒ number

Get the number of edges coming into a given vertex.

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

Throws:

  • VertexNotExistsError if a vertex with this key does not exist

Returns: number - the number of edges coming into the key vertex


<a name=“user-content-graph+degree”></a>

graph.degree(key) ⇒ number

Get the number of edges connected to a given vertex.

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

Throws:

  • VertexNotExistsError if a vertex with this key does not exist

Returns: number - the number of edges connected to the key vertex


<a name=“user-content-graph+mergein”></a>

graph.mergeIn(other, [mV], [mE])

Merge another graph into this graph.

Param Type Description
other Graph the other graph to merge into this one
[mV] function a custom merge function for values stored in vertices; defaults to whichever of the two values is not undefined, giving preference to that of the other graph; The first and second arguments are the vertex values of this graph and the other graph respectively. The third is the corresponding key.
[mE] function a custom merge function for values stored in edges; defaults to whichever of the two values is not undefined, giving preference to that of the other graph; The first and second arguments are the edge values of this graph and the other graph respectively. The third and fourth are the corresponding from and to keys.

<a name=“user-content-graph+clone”></a>

graph.clone([trV], [trE]) ⇒ Graph

Create a clone of this graph.

Param Type Description
[trV] function a custom transformation function for values stored in vertices; defaults to the identity function; The first argument is the value to clone. The second is the corresponding key.
[trE] function a custom transformation function for values stored in edges; defaults to the function given for trV; The first argument is the value to clone. The second and third are the from and to keys respectively.

Returns: Graph - a clone of this graph


<a name=“user-content-graph+transitivereduction”></a>

graph.transitiveReduction([trV], [trE]) ⇒ Graph

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

Param Type Description
[trV] function a custom transformation function for values stored in vertices; defaults to the identity function; The first argument is the value to clone. The second is the corresponding key.
[trE] function a custom transformation function for values stored in edges; defaults to the function given for trV; The first argument is the value to clone. The second and third are the from and to keys respectively.

Returns: Graph - a clone of this graph with all transitive edges removed


<a name=“user-content-graph+contractpaths”></a>

graph.contractPaths([isNexus])

This method replaces stretches of non-branching directed pathway into single edges. More specifically, it identifies all ‘nexus’ vertices in the graph and preserves them. It then removes all other vertices and all edges from the graph, then inserts edges between nexuses that summarize the connectivity that was there before.

A nexus is any vertex that is not characterized by ‘1 edge in, 1 edge out’. A custom isNexus function may be provided to manually select additional vertices that should be preserved as nexus.

Param Type Description
[isNexus] function a predicate for identifying additional vertices that should be treated as nexus; It receives a key and value associated to a vertex and should return true if and only if that vertex should be a nexus.

Throws:

  • BranchlessCycleError if the graph contains a cycle with no branches or nexuses

<a name=“user-content-graph+tojson”></a>

toJSON() ⇒ string

Serialize this graph into a JSON string. The resulting string can be deserialized with Graph.fromJSON

Returns: string - a JSON string representation of the current state of this graph Example

let json   = graph1.toJSON();
let graph2 = Graph.fromJSON(json);
console.log(graph1.equals(graph2)); // true

See: Graph.fromJSON


<a name=“user-content-graph.fromjson”></a>

fromJSON(json) ⇒ Graph

Deserialize a string returned from .toJSON() into a new Graph instance equal to the original.

Param Type Description
json string a string originally returned from .toJSON()

Returns: Graph - a graph equal to the original Example

let json   = graph1.toJSON();
let graph2 = Graph.fromJSON(json);
console.log(graph1.equals(graph2)); // true

See: Graph#toJSON


<a name=“user-content-graph+event_vertex-added”></a>

“vertex-added”

An event that is triggered just after a vertex is added to this graph. Handlers receive the new vertex [key, value] as an argument.

See: on, off


<a name=“user-content-graph+event_vertex-removed”></a>

“vertex-removed”

An event that is triggered just after a vertex is removed from this graph. Handlers receive the vertex key as an argument.

See: on, off


<a name=“user-content-graph+event_vertex-modified”></a>

“vertex-modified”

An event that is triggered after a vertex in this graph is modified. It is also triggered after any “vertex-added” event. Handlers receive the vertex [key, value] as an argument.

See: on, off


<a name=“user-content-graph+event_edge-added”></a>

“edge-added”

An event that is triggered just after an edge is added to this graph. Handlers receive the new edge [[from, to], value] as an argument.

See: on, off


<a name=“user-content-graph+event_edge-removed”></a>

“edge-removed”

An event that is triggered just after an edge is removed from this graph. Handlers receive the edge key [from, to] as an argument.

See: on, off


<a name=“user-content-graph+event_edge-modified”></a>

“edge-modified”

An event that is triggered after an edge in this graph is modified. It is also triggered after any “edge-added” event. Handlers receive the edge [[from, to], value] as an argument.

See: on, off


<a name=“user-content-graph.vertexexistserror”></a>

Graph.VertexExistsError ⇐ Error

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

Extends: Error


<a name=“user-content-graph.vertexexistserror+vertices”></a>

vertexExistsError.vertices : Set.<Array>

the set of relevant vertices as [key, value] shaped arrays


<a name=“user-content-graph.vertexnotexistserror”></a>

Graph.VertexNotExistsError ⇐ Error

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

Extends: Error


<a name=“user-content-graph.vertexnotexistserror+vertices”></a>

vertexNotExistsError.vertices : Set.<string>

the set of relevant vertex keys


<a name=“user-content-graph.edgeexistserror”></a>

Graph.EdgeExistsError ⇐ Error

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

Extends: Error


<a name=“user-content-graph.edgeexistserror+edges”></a>

edgeExistsError.edges : Set.<Array>

the set of relevant edges as [[from, to], value] shaped arrays


<a name=“user-content-graph.edgenotexistserror”></a>

Graph.EdgeNotExistsError ⇐ Error

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

Extends: Error


<a name=“user-content-graph.edgenotexistserror+edges”></a>

edgeNotExistsError.edges : Set.<Array.<string>>

the set of relevant edge keys as [from, to] shaped arrays


<a name=“user-content-graph.hasconnectededgeserror”></a>

Graph.HasConnectedEdgesError ⇐ EdgeExistsError

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

Extends: EdgeExistsError


<a name=“user-content-graph.hasconnectededgeserror+vertex”></a>

hasConnectedEdgesError.vertex : string

the key of the vertex that has connected edges


<a name=“user-content-graph.edgeexistserror+edges”></a>

hasConnectedEdgesError.edges : Set.<Array>

the set of relevant edges as [[from, to], value] shaped arrays


<a name=“user-content-graph.cycleerror”></a>

Graph.CycleError ⇐ Error

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

Extends: Error


<a name=“user-content-graph.cycleerror+cycle”></a>

cycleError.cycle : Array.<string>

the vertices involved in the cycle, in order but with an unspecified starting point


<a name=“user-content-graph.branchlesscycleerror”></a>

Graph.BranchlessCycleError ⇐ CycleError

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

Extends: CycleError


<a name=“user-content-graph.cycleerror+cycle”></a>

branchlessCycleError.cycle : Array.<string>

the vertices involved in the cycle, in order but with an unspecified starting point


你可能感兴趣的文章:

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-70288.html

文章标题:graph.js

回到顶部