# graph/index.js

``````/**
*  A graph is a non-linear data structure where a node can have zero or more
*  connected nodes.
*
*  @module graph
*/

const { Stack, Queue } = require("../linear")
const GraphNode = require("./node")
const HashMap = require("../maps").HashMap

/**
*  The connection between two nodes in a graph is called an **edge**.
*  Nodes are also referred to as **vertices**.
*
*  A graph can be **directed** or **undirected**. A directed graph
*  has edges that allow traversing in one direction only. Whereas edges
*  in an undirected graph are two-way and can be traversed freely.
*
*  Graphs can be **cyclic** or **acyclic**. A graph in which you can
*  pass through a node more than once is called a cyclic graph. Those
*/
class Graph {
/**
*  Instantiates a graph.
*  @param {boolean} [directed=true] Edge direction. Set to `false`
*    for an undirected graph.
*/
constructor(directed = true) {
this._nodes = new HashMap()
this._isDirected = directed
}

get count() {
return this._nodes.count
}

/**
*  Add a vertex to the graph. Returns the new vertex or the existing
*  one if it already exists.
*
*  Runtime: `O(1)`
*
*  @param {any} data
*  @returns {GraphNode} the new node or the existing one if it already
*    exists
*/
if(this._nodes.has(data)) {
return this._nodes.get(data)
}

const vertex = new GraphNode(data)
return vertex
}

/**
*  Removes vertex with the given `data` from the graph. Returns the removed
*  node's value or `null` if no such node was found.
*
*  Runtime: `O(n)` where n = number of vertices + number of edges
*
*  @param {any} data
*  @returns {?any}
*/
removeVertex(data) {
if(!this._nodes.has(data)) {
return null
}

const current = this._nodes.get(data)
Array.from(this._nodes.values()).forEach(node => node.removeNeighbour(current))
return this._nodes.delete(data)
}

/**
*  Create a connection between `source` node and `destination` node. If the
*  graph is undirected, it will also create the connection from `destination`
*  to `destination`.
*  If the nodes don't exist, they will be created anew with values set to
*  `source` and `destination` respectively.
*
*  Return source/destination node pair as
*    `{ source: GraphNode, destination: GraphNode }`
*
*  Runtime: `O(1)`
*
*  @param {any} source
*  @param {any} destination
*  @returns {{GraphNode, GraphNode}} source/destination node pair
*/

if(!this._isDirected) {
}

return {
source: sourceNode,
destination: destNode
}
}

/**
*  Remove connection between `source` node and `destination` node.
*  If the graph is undirected it will also remove the connection from
*  `destination` to `destination`.
*
*  Returns `true` if  deletion is successful, `false` if no such nodes
*  exist.
*
*  Runtime: `O(n)` where n is the number of edges
*
*  @param {any} source
*  @param {any} destination
*/
removeEdge(source, destination) {
const sourceNode = this._nodes.get(source)
const destNode = this._nodes.get(destination)

if (sourceNode && destNode) {
sourceNode.removeNeighbour(destNode)
if(!this._isDirected) {
destNode.removeNeighbour(sourceNode)
}
return true
}

return false
}

/**
*  Returns `true` if two nodes are adjacent to each other.
*
*  @param {any} source source node's value
*  @param {any} destination destination node's value
*  @returns {boolean}
*/
areNeighbours(source, destination) {
const sourceNode = this._nodes.get(source)
const destNode = this._nodes.get(destination)

if (sourceNode && destNode) {
return sourceNode.isNeighbour(destNode)
}

return false
}

/**
*  Depth-first search goes deep before going wide. Works the same
*
*  @param {any} startValue value of the vertex to start the search from
*/
* searchDepthFirst(startValue) {
const startVertex = this._nodes.get(startValue)
yield* Graph.Search(startVertex, Stack)
}

/**
*  Breadth-first search goes deep before going wide. Works the same
*  @param {any} startValue the value of the vertex to start the search from
*/
const startVertex = this._nodes.get(startValue)
yield* Graph.Search(startVertex, Queue)
}

/**
*  Generic graph search method. Can be passed a `Type` which determines
*  the search method used.
*
*  Breadth-first search if `Type` is `Queue`.
*  Depth-first search if `Type` is `Stack`.
*
*  @private
*  @param {GraphNode} first vertex to start the search
*  @param {Stack|Queue} Type `Stack` for depth-first; `Queue` for breadth-first
*/
static* Search(first, Type = Stack) {
const visited = new HashMap()
const visitList = new Type()

Type == Stack ? visitList.push(first) : visitList.enqueue(first)

while (visitList._items.count > 0) {
const node = Type == Stack ? visitList.pop() : visitList.dequeue()
if (node && !visited.has(node)) {
yield node