MaxCardinalitySearch {rlemon}

Solver for Max Cardinality Search

Description

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.

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.

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