Home Manual Reference Source

:notebook_with_decorative_cover:

@graph-data-structure/specification

Graph data structure specification for JavaScript.

:warning: Depending on your environment, the code may require regeneratorRuntime to be defined, for instance by importing regenerator-runtime/runtime.

// eslint-disable-next-line ava/use-test
import ava from 'ava';
import * as spec from '@graph-data-structure/specification';
spec.graph(ava, "My graph implementation", MyGraphConstructor);

License Version Tests Dependencies GitHub issues Downloads

Code issues Code maintainability Code coverage (cov) Code technical debt Documentation Package size

Signatures

Graphs, DiGraphs, MultiGraphs, and MultiDiGraphs

Graph, DiGraph, MultiGraph, or MultiDiGraph

Create a new graph.

let G = new Graph( ) ;
// ...
let G = new DiGraph( ) ;
// ...
let G = new MultiGraph( ) ;
// ...
let G = new MultiDiGraph( ) ;
// ...

vadd

Add a vertex to graph G.

let u = G.vadd( ) ;

vdel

Delete vertex u from graph G.

G.vdel( u ) ;

eadd

Add edge (u,v) to graph G.

let e = G.eadd( u , v ) ;

edel

Delete edge e from graph G.

G.edel( e ) ;

vitr

Get an iterator over vertex references in graph G.

for ( let u of G.vitr( ) ) ... ;

eitr

Get an iterator over edge references in graph G.

for ( let e of g.eitr( ) ) ... ;

iitr

Get an iterator over edge references of edges incident to u in graph G.

for ( let e of G.iitr( u ) ) ... ;

nitr

Get an iterator over vertex references of neighbors of u in graph G.

for ( let v of G.nitr( u ) ) ... ;

vertices

Get an iterator over vertices in graph G.

for ( let u of G.vertices( ) ) ... ;

edges

Get an iterator over edges in graph G.

for ( let [ u , v , e ] of G.edges( ) ) ... ;

incident

Get an iterator over edges incident to w in graph G.

for ( let [ u , v , e ] of G.incident( w ) ) ... ;

endpoints

Get endpoints u and v of an edge reference e in graph G.

let [ u , v ] = G.endpoints( e ) ;

DiGraphs and MultiDiGraphs

These methods must also be implemented (with the same invariants) in Graphs and MultiGraphs for convenience.

initr

Get an iterator over edge references of ingoing edges of u in graph G.

for ( let e of G.initr( u ) ) ... ;

outitr

Get an iterator over edge references of outgoing edges of u in graph G.

for ( let e of G.outitr( u ) ) ... ;

dpitr

Get an iterator over direct predecessors of u in graph G.

for ( let v of G.dpitr( u ) ) ... ;

dsitr

Get an iterator over direct successors of u in graph G.

for ( let v of G.dsitr( u ) ) ... ;

ingoing

Get an iterator over ingoing edges of w in graph G. The invariant v === w must hold.

for ( let [ u , v , e ] of G.ingoing( w ) ) ... ;

outgoing

Get an iterator over outgoing edges of w in graph G. The invariant u === w must hold.

for ( let [ u , v , e ] of G.outgoing( w ) ) ... ;

reverse

Reverse the directions of edges in G.

G.reverse( ) ;