optrees (version 1.0)

findstCut: Determines the s-t cut of a graph

Description

findstCut reviews a given graph with a cut between two nodes with the bread-first search strategy and determines the two cut set of the partition. The cut is marked in the arc list with an extra column that indicates the remaining capacity of each arc.

Usage

findstCut(nodes, arcs, s = 1, t = nodes[length(nodes)])

Arguments

nodes

vector containing the nodes of the graph, identified by a number that goes from $1$ to the order of the graph.

arcs

matrix with the list of arcs of the graph. Each row represents one arc. The first two columns contain the two endpoints of each arc and the third column contains their weights.

s

number pointing one node of the s cut in a given graph. It's node $1$ by default.

t

number pointing one node of the t cut in a given graph. It's the last node by default.

Value

findstCut returns a list with two elements:

s.cut

vector with the nodes of the s cut.

t.cut

vector with the nodes of the t cut.

See Also

This function is an auxiliar function used in ghTreeGusfield and getMinimumCutTree.