: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);

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( ) ;