GraphSearch {rlemon}

Solver for Graph Search

Description

Runs a common graph search algorithm to find the minimum cardinality shortest path. Finds the shortest path from/to all vertices if a start/end node are not given.

Usage

GraphSearch(
  arcSources,
  arcTargets,
  numNodes,
  startNode = -1,
  endNode = -1,
  algorithm = "Bfs"
)

Arguments

arcSources

Vector corresponding to the source nodes of a graph's edges

arcTargets

Vector corresponding to the destination nodes of a graph's edges

numNodes

The number of nodes in the graph

startNode

Optional start node of the path

endNode

Optional end node of the path

algorithm

Choices of algorithm include "Bfs" (Breadth First Search) and "Dfs" (Depth First Search). Bfs is the default.

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00608.html.

Value

A named list containing three entries: 1) "predecessors": the predecessor of each vertex in its shortest path, 2) "distances": the distances from each node to the startNode, 3) "node_reached": a vector of logicals indicating whether a node was reached.