wabstractgraph

wAbstractGraph

Collection of abstract data structures and algorithms to process graphs. The module does not bound to any specific format of a graph, so providing adapters toy may use it with anyone. It implements depth-first search, breadth-first search, extracting strongly connected components, topological sort, shortest path search, and others.

Concepts

Graph :: set of nodes and set of edges or arcs connecting some or all nodes.
Incident edges :: of the node, are edges connected to the node.
Connected nodes :: nodes are connected if them have edge connecting both of them.
Reachable node :: node v is reachable from u if there is a path from v to u.
DFS :: depth-first search.
BFS :: breadth-first search.
DAG :: directed acycled graph.
SCC :: Strongly connected components.
Node degree :: total number of incoming and outgoint edges of the node.
Indegree :: of the node is number of incoming edges.
Outdegree :: of the node is number of outgoing edges.
Sink node :: node with zero outdegree.
Source node :: node with zero indegree.
Universal node :: node connected to all nodes of the graph.
Terminal node :: pendant node :: leaf node :: node with degree of one.
Neighborhood :: is an enduced subgraph of the graph, formed by all nodes adjacent to v.
Neigbour nodes :: nodes which are connected to the node.
Low-link value of a node :: smallest node id reachable from the node.
Topological ordering :: linear ordered DAG.
Topological sort :: algorithm of linear ordering of DAG.
Distance between nodes :: minimal number of edges to get from one given node to another given node.
Distance layers :: array of arrays of nodes. First layer has origin or zero-distance set of nodes. Second layer has nodes on distance one from origin. And os on.

Sample

require( '..' );
let _ = wTools;

/*
This example shows how to create a simple graph.
Graph :: set of nodes( vertices ) and set of edges or arcs connecting some or all nodes.
*/

/*
Define a graph of arbitrary structure.
Strcuture of nodes is arbitrary. It could even be instance of a primitive type.
Group of nodes should have handlers which should return lists of neighbour nodes.
*/

var a = { name : 'a', nodes : [] } // 1
var b = { name : 'b', nodes : [] } // 2
var c = { name : 'c', nodes : [] } // 3

// declare lists neighbour nodes

a.nodes.push( b ); // add edge between nodes a and b
b.nodes.push( c ); // add edge between nodes b and c

/* declare the graph */

var sys = new _.graph.AbstractGraphSystem(); // declare sysyem of graphs
var group = sys.groupMake(); // declare group of nodes
group.nodesAdd([ a, b, c ]); // add nodes to the group

console.log( group.nodesExportInfo() ); // print information about nodes relation

/*
    1 : 2
    2 : 3
    3 :
*/

Try out

npm install
node sample/Sample.s