Giraph

Immutable graph data structures

Install

npm install -S giraph
bower install -S giraph

Usage

require('giraph')()
  .add('a', { my: 'data' })
  .add('b')
  .add('c')
  .connect('a', 'b', 3)
  .connect('a', 'c')

Docs

Giraph comes with a number of different graph types:

• Undirected Graph
• Directed Graph (Not Implemented Yet)
• Directed Acyclic Graph (Not Implemented Yet)

Undirected Graph

Exported as a factory function on the root namespace:

.([options])

Options and defaults

{
  immutable: true
}

require('giraph')() // => empty graph

The undirected graph has the following members

Property: .map: {}

Hashes vertices by id.

Property: .options

Instance options

Property: .length

The number of vertices

.add( id[, data] )

Returns a new instance with Vertex(id[, data]) added to it.

.get( id )

Gets the Vertex at id.

.remove( id )

Returns a new instance with id removed.

.connect( a, b, edgeWeight )

Returns a new instance with a and b connected.

.contains( String|Vertex id )

Returns a boolean indicating whether or not id is in the graph.

Note: if passing in a String, is equivalent to checking id in graph.map.

.merge( a[, b[, ...]] )

Returns a new instance with all other graphs merged into the current.

Note: merging takes Left-to-right precedence. If a and b both contain the same node, c, but have different data attached, b will take precedence.

Example:

var g1 = giraph()
  .add('a')
  .add('b', { some: 'thing' })
  .connect('a', 'b', 1);

var g2 = giraph()
 .add('b', { some: 'data' })
 .add('c')
 .conect('b', 'c');
 
// a->b->c
var g3 = g1.merge( g2 );

// { some: 'data' }
console.log( g3.get('b').data );

.each( Function iterator )

Iterates through each vertex. The iterator argument has the following signature:

function( Vertex v, Number i, Graph g )

Example:

require('giraph')
  .add('a', { some: 'data' }).add('b').add('c')
  .each( function( vertex, i, graph ){
    console.log( vertex.id, vertex.data, i );
  });
  
  // a { some: 'data' }
  // b null
  // c null

Returns this

.reduce( Function iterator, Mixed initialValue )

Iterates through the graph, producing a single value. iterator has the following signature

function( Mixed currentValue, Vertex V, Number i, Graph g )

Returns Value of reduction

.instance()

Returns this instance or a clone() depending on options.immutable.

.edges([id])

Returns an array of edges with the following structure:

{ vertices: ['a', 'b'], weight: 10 }

Optionally, pass a vertex ID to only get edges touching that vertex.

.clone()

Returns a new instance of the graph

.weight()

Returns The total weight of all edges in the graph

.mutate(handler)

Allows mutation to occur on an immutable graph for a single turn of the event loop.

Returns the original instance

require('giraph')()
  .mutate(function( g ){
    // Batch operations here
    g.add('a').add('b').add('c');
  })

.mst()

Returns a Minimum Spanning Tree represented as a Graph.

Directed Graph

TODO

Directed Acyclic Graph

TODO

Vertex

A vertex is essentially an Identifier with data attached and connections to other vertices.

It's available under .vertex( id[, data[, options]]).

.id String

ID of the vertex

.data Mixed

Optional attached data

.options Object

Optional options:

{
  immutable: true
}

.clone()

Returns a new instance of the vertex

TODO

• Topological Sorting
• Cliques and maximum cliques
• Planarism
• Creating sub-graphs and walks