graphnode

Install

npm install graphnode

Description

This module provides Graph ADT and standard graph algorithms

Vertex

A vertex is created as follows

var vertex1 = new Vertex(null, null, "vertex1");

The constructore takes 3 arguments

• Parent
• Value
• Label

If a label is not provided, then a default label is assigned to vertex.

Edge

An edge is created as follows

var edge1 = new Edge(vertex1, vertex2, 10, "edge1");

The constructore takes 4 arguments

• Source vertex
• Destination vertex
• Cost
• Label

If a label is not provided, then a default label is assigned to the edge.

Creating Graph

var graph = new Graph(vertices, edges, "graph1", false);

The constructore takes 4 arguments

• Array of vertices
• Array of edges
• Name of graph
• Whether graph is directed

Graph internally maintains an adjacency list and it depends on whether graph is directed or undirected.

Graph created can be stored for future use. The name of the graph is used to store the graph. To retrieve the stored the graph, you need to provide the name of graph.

Store graph

graphnode.saveGraphInStore(graph);

Retrieve graph

graph = graphnode.getGraphFromStore(nameOfGraph);

Algorithms

Currently only search algorithms are supported

• Breadth first search
• Depth first search

Search algorithms take search value as input which is basically the label of vertex you are searching for. After completion of search algorithms, you can inspect vertices to find their logical distance from source vertex. The source vertex is the index '0' vertex in the vertices array.

Example Code

    var graphnode = require('graphnode');    
    var Vertex = graphnode.Vertex;
    var Edge = graphnode.Edge;    
    var vertex1 = new Vertex(null, null, "vertex1");
    var vertex2 = new Vertex(null, null, "vertex2");
    var vertex3 = new Vertex(null, null, "vertex3");
    var vertex4 = new Vertex(null, null, "vertex4");
    var vertex5 = new Vertex(null, null, "vertex5");
    var vertex6 = new Vertex(null, null, "vertex6");    
    var vertices = new Array(vertex1, vertex2, vertex3, vertex4, vertex5, vertex6);    
    var edge1 = new Edge(vertex1, vertex2, 10, "edge1");
    var edge2 = new Edge(vertex1, vertex6, 100, "edge2");
    var edge3 = new Edge(vertex2, vertex3, 5, "edge3");
    var edge4 = new Edge(vertex2, vertex5, 2, "edge4");
    var edge5 = new Edge(vertex3, vertex6, 3, "edge5");
    var edge6 = new Edge(vertex3, vertex4, 4, "edge6");    
    var edges = new Array(edge1, edge2, edge3, edge4, edge5, edge6);    
    var Graph = graphnode.Graph;    
    var graph = new Graph(vertices, edges, "graph1", false);    
    var result = graph.breadthFirstSearch("vertex3");    
    console.log(result);    
    result = graph.depthFirstSearch("vertex3");    
    console.log(result);    
    graphnode.saveGraphInStore(graph);    
    graph = graphnode.getGraphFromStore(graph.getGraphName());    
    console.log(graph);