optrees (version 1.0)

compactCycle: Compacts the nodes in a cycle into a single node

Description

Given a directed graph with a cycle, compactCycle compacts all the nodes in the cycle to a single node called supernode. The function uses the first and the last node of the cycle as a fusion point and obtains the costs of the incoming and outgoing arcs of the new node.

Usage

compactCycle(nodes, arcs, cycle)

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.

cycle

vector with the original nodes in the cycle.

Value

compactCycle returns the nodes and the list of arcs forming a new graph with the compressed cycle within a supernode. Also returns a list of the correspondences between the nodes of the new graph and the nodes of the previous graph.

See Also

This function is an auxiliar function used in msArborEdmonds and getMinimumArborescence.