Graph

Definition

In computer science, a graph is an abstract data type that is meant to implement the graph and hypergraph concepts from mathematics.

A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes may be part of the graph structure, or may be external entities represented by integer indices or references.

A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Source: Wikipedia

Implementation details

This implementation uses the adjacency list representation

How to use

Import

var Graph = require('algorithms').DataStructure.Graph;

Initialization

When initializing a Graph, a boolean parameter can be passed to the constructor to indicate if the graph is directed or not. If nothing is passed, the default value is true

var g = new Graph(); // Directed graph
g = new Graph(false); // Undirected graph
g = new Graph(true); // Directed graph

Graph.prototype.addVertex(v)

Adds a vertex to the graph

g.addVertex(a);
g.addVertex(b);
g.addVertex(c);

g.vertices; // [a, b, c]

Graph.prototype.addEdge(a, b[, w])

Adds an edge between a and b with weight w (default to 1 if not specified)

g.addEdge('a', 'b');
g.addEdge('b', 'c', 10);

Graph.prototype.edge(a, b)

Returns the weight of the edge between a and b

g.addEdge('a', 'b');
g.addEdge('b', 'c', 10);

g.edge('a', 'b'); // 1
g.edge('b', 'c'); // 10
g.edge('a', 'c'); // undefined

Graph.prototype.neighbors(v)

Returns the list of vertices that are neighbors to v

g.addEdge('a', 'b');
g.addEdge('b', 'c', 10);
g.addEdge('b', 'd', 5);

g.neighbors('a'); // ['b']
g.neighbors('b'); // ['c', 'd']