📔
@graph-data-structure/specification

Graph data structure specification for JavaScript.

⚠️ 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( ) ;`