graph-json

A JSON-format backed graph library with advanced identification algorithms.

JSON Scheme (DirectedGraph):

{
    "type": "object",
    "properties": {
        "nodes": {
            "type": "array",
            "items": {
                "type": "object",
                "properties": {
                    "name": {
                        "type": "string",
                        "required": true
                    }
                }
            }
        },
        "edges": {
            "type": "array",
            "items": {
                "type": "object",
                "properties": {
                    "name": {
                        "type": "string",
                        "required": true
                    },
                    "from": {
                        "type": "string",
                        "required": true
                    },
                    "to": {
                        "type": "string",
                        "required": true
                    }
                }
            }
        }
    }
}

Documentation

DirectedGraph

You can use the DirectedGraph library in your project by either calling

var DirectedGraph = require('graph-json').DirectedGraph;

or

var DirectedGraph = require('graph-json').DG;

function DirectedGraph([struct])

Creates a directed graph based on the structure defined (a .json object matching the specification), or creates a graph with no edges and nodes if struct is not specified.

An example struct would look like the following (used in the remainder of the documentation)

{
    "nodes": [
        {
            "name": "A"
        },
        {
            "name": "B"
        },
        {
            "name": "C",
            "data": "__DATA__"
        },
        { 
            "name": "T"
        }
    ],
    "edges": [
        {
            "name": "AB",
            "from": "A",
            "to": "B",
            "data" : "__DATA__"
        },
        {
            "name": "BC",
            "from": "B",
            "to": "C"
        }
    ]
}

In order to create a graph, you'll want to parse your JSON object and pass it as a parameter. For example,

//g is the JSON parsed object of graph.json located in the executing directory
var g = JSON.parse(fs.readFileSync('./graph.json'));
 
//t_graph is the graph created from graph.json
var t_graph = new DirectedGraph(g);

Or, you can create a graph without specifying a JSON file:

var t_graph = new DirectedGraph();

The graph above contains no nodes and no edges.

DirectedGraph.prototype.edgesIn = function (node)

Returns the number of edges entering a given node.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
var x = t_graph.edgesIn('B');
console.log(x[0].from); // #==> for the test graph, should print 'A'

DirectedGraph.prototype.edgesOut = function (node)

Returns the number of edges exiting a given node.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
var x = t_graph.edgesOut('A');
console.log(x[0].to) // #==> for the test graph, should print 'B'

DirectedGraph.prototype.getNode = function (id)

Returns a node contained in the graph with the given name (id).

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
var node = t_graph.getNode('C'); // #==> assigns the variable node to the node of the graph with name 'C'

DirectedGraph.prototype.numNodes = function ()

Returns the number of nodes contained in the graph.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
console.log(t_graph.numNodes()); // #==> prints '3' for the test graph

DirectedGraph.prorotype.getEdge = function (id)

Returns an edge contained in the graph with the given name (id).

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
var edge = t_graph.getEdge('BC'); // #==> assigns the variable edge to the edge of the graph with name 'BC'

DirectedGraph.prototype.numEdges = function ()

Returns the number of edges contained in the graph.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
console.log(t_graph.numEdges()) // #==> prints '2' for the test graph

DirectedGraph.prototype.edges = function ()

Returns the edges array internally stored in graph-json.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
var edge_array = t_graph.edges();

DirectedGraph.prototype.isTerminal = function (node)

Returns true if the specified node is ternminal (has no children), and false otherwise.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
console.log(t_graph.isTerminal('T')); // #==> prints 'true' for the test graph

DirectedGraph.prototype.dfs = function (to_find, node, graph)

Performs a depth-first-search on the given graph, searching for to_find starting from node.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
console.log((t_graph.dfs('B', 'A', t_graph)); // #==> prints 'B' for the test graph (search successful) 
console.log((t_graph.dfs('dne', 'A', t_graph)); // #==> prints 'null' for the test graph (search failed) 

function hangingEdges(graph, edges)

Returns an array of the "hanging edges" - edges that either have no from or to node defined - in the current graph schema.

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
var x = hangingEdges(t_graph, t_graph.edges);
if (x.length !== 0) {
    return new ValidationError('Hanging Edges Found: ', x); // # ==> uh-oh! We have hanging edges in the graph.
}
// #==> seeing as the test graph is properly defined, no validation error will be thrown.

DirectedGraph.prototype.addNode = function (name, [dt])

Adds a node to the graph with an optional parameter containing data.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
t_graph.addNode('A'); // adds node 'A' to the graph
t_graph.addNode('B', 'xyz'); // adds node 'B' to the graph, with data xyz

DirectedGraph.prototype.addEdge = function (name, from, to, [dt])

Adds an edge to the graph with an optional parameter containing data.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
t_graph.addEdge('A->B', 'A', 'B'); // adds edge 'A->B' to the graph from node A to node B
t_graph.addEdge('A->C', 'A', 'C', '10'); // adds edge 'A->C' to the graph from node A to node C with data 10

DirectedGraph.prototype.add = function([nodes...])

Adds any number of nodes to a graph, automatically creating the nodes if they do not exist and creating edges between each adjacent node.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
// the following creates nodes 'a', 'b', 'c', and 'd' if they do not exist,
// and then creates the edges a->b, b->c, and c->d
t_graph.add('a', 'b', 'c', 'd'); 

DirectedGraph.prototype.tSort = function ()

Topologically sorts the graph and returns the resulting node array.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
console.log(t_graph.tSort()); //prints a comma-delimited topologically sorted node order of t_graph

DirectedGraph.prototype.isAcyclic = function ()

Returns true if the graph is acyclic, false otherwise. Uses a topological sort under the hood.

Example:

var g = JSON.parse(fs.readFileSync('./graph.json'));
var t_graph = new DirectedGraph(g);
 
if(t_graph.isAcyclic()) {
    //do something
}
else {
    //do something else
}

UndirectedGraph

Need to add this documentation.