Package Exports

graph-json

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (graph-json) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

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;

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.