MaxCardinalitySearch: Solver for Max Cardinality Search

In rlemon: R Access to LEMON Graph Algorithms

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

rlemon documentation built on Feb. 16, 2023, 5:33 p.m.