Graph

Abstract graph implementation.

A Graph consists of GraphNodes. Each GraphNode can be in three states: - UNDISCOVERED - VISITED - FINISHED

GraphNode:__init(val)

View source

Constructor.

Arguments:

  • val (any): value for the new node.

GraphNode:__tostring__()

View source

Returns:

  • (string) string representation

Graph:__init()

View source

Constructor.

Graph:size()

View source

Returns:

  • (int) number of nodes in the graph.

Graph:assertValidNode(node)

View source

Verifies that the node is in the graph

Arguments:

  • node (Graph.Node): the node to verify.

Graph:addNode(val)

View source

Adds a node with given value to the graph.

Arguments:

  • val (any): value for the new node.

Returns:

  • (Graph.Node)

Graph:connectionsOf(node)

View source

Returns neighbours of a given node.

Arguments:

  • node (Graph.Node): the node to find neighbours for.

Returns:

  • (table(Graph.Node))

Graph:nodeSet()

View source

Returns a set of nodes in the graph.

Returns:

  • (Set(Graph.Node))

Graph:resetState()

View source

Initializes all nodes to Graph.state.UNDISCOVERED.

Returns:

  • (Graph)

The graph will be returned

Graph:breadthFirstSearch(source, callbacks)

View source

Performs breadth first search.

Arguments:

  • source (Graph.Node): the source node to start BFS.
  • callbacks (table[string:function]): a map with optional callbacks

Available callbacks:. Optional.

  • discover = function(Graph.Node): called when a node is initially encountered

  • finish = function(Graph.Node): called when a node has been fully explored (eg. its connected nodes have all been visited)

Graph:shortestPath(source, destination, skipBFS)

View source

Returns the shortest path from source to destination

Arguments:

  • source (Graph.Node): starting node.
  • destination (Graph.Node): end node.
  • skipBFS (boolean): whether BFS has already been performned. Optional.

Note: This function relies on the results from a BFS call. By default, a BFS is performed before

retrieving the shortest path. Alternatively, if the caller has already performed BFS, then

this BFS can be skipped by passing in skipBFS = true.

Graph:depthFirstSearch(nodes, callbacks)

View source

Performs depth first search.

Arguments:

  • nodes (table[Graph.Node]): the table of nodes on which to perform DFS. If not set, then all nodes in the graph are used.
  • callbacks (table[string:function]): a map with optional callbacks

Available callbacks:. Optional.

  • discover = function(Graph.Node): called when a node is initially encountered

  • finish = function(Graph.Node): called when a node has been fully explored (eg. its connected nodes have all been visited)