Runs the maximum cardinality search algorithm on a directed graph. The maximum cardinality search first chooses any node of the digraph. Then every time it chooses one unprocessed node with maximum cardinality, i.e the sum of capacities on out arcs to the nodes which were previously processed. If there is a cut in the digraph the algorithm should choose again any unprocessed node of the digraph.
Usage
MaxCardinalitySearch(
arcSources,
arcTargets,
arcCapacities,
numNodes,
startNode = -1,
algorithm = "maxcardinalitysearch"
)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
- arcCapacities
Vector corresponding to the distances of a graph's edges
- numNodes
The number of nodes in the graph
- startNode
Optional start node of the path
- algorithm
Choices of algorithm include "maxcardinalitysearch". maxcardinalitysearch is the default.
Value
A named list containing two entries: 1) "cardinalities": the cardinality of each node , 2) "node_reached": a logical vector indicating whether a node was reached or not
Details
For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00255.html.