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.
MaxCardinalitySearch(
arcSources,
arcTargets,
arcCapacities,
numNodes,
startNode = -1,
algorithm = "maxcardinalitysearch"
)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
Vector corresponding to the source nodes of a graph's edges
Vector corresponding to the destination nodes of a graph's edges
Vector corresponding to the distances of a graph's edges
The number of nodes in the graph
Optional start node of the path
Choices of algorithm include "maxcardinalitysearch". maxcardinalitysearch is the default.
For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00255.html.