Learn R Programming

optrees (version 1.0)

Optimal Trees in Weighted Graphs

Description

Finds optimal trees in weighted graphs. In particular, this package provides solving tools for minimum cost spanning tree problems, minimum cost arborescence problems, shortest path tree problems and minimum cut tree problem.

Copy Link

Version

Install

install.packages('optrees')

Monthly Downloads

23

Version

1.0

License

GPL-3

Maintainer

Manuel Fontenla

Last Published

September 2nd, 2014

Functions in optrees (1.0)

checkArbor

Checks if there is at least one arborescence in the graph
getMinimumArborescence

Computes a minimum cost arborescence
getMinimumSpanningTree

Computes a minimum cost spanning tree
getMinCostArcs

Selects the minimum cost of the arcs pointing to each node
removeLoops

Remove loops of a graph
removeMultiArcs

Remove multi-arcs with no minimum cost
findMinCut

Finds the minimum cut of a given graph
getMinimumCutTree

getMinimumCutTree ---------------------------------------------------------- Computes a minimum cut tree
getCheapArcs

Substracts the minimum weight of the arcs pointing to each node
searchZeroCycle

Zero weight cycle in a graph
checkGraph

Checks if the graph contains at least one tree or one arborescence
ArcList2Cmat

Builds the cost matrix of a graph from its list of arcs
ghTreeGusfield

Gomory-Hu tree with the Gusfield's algorithm
Cmat2ArcList

Builds the list of arcs of a graph from its cost matrix
getZeroArcs

Selects zero weight arcs of a graph
msTreeBoruvka

Minimum cost spanning tree with Boruvka's algorithm.
repGraph

Visual representation of a graph
stepbackArbor

Go back between two stages of the Edmond's algorithm
spTreeDijkstra

Shortest path tree with Dijkstra's algorithm
searchWalk

Finds an open walk in a graph
getComponents

Connected components of a graph
msTreePrim

Minimum cost spanning tree with Prim's algorithm
findstCut

Determines the s-t cut of a graph
msTreeKruskal

Minimum cost spanning tree with Kruskal's algorithm
maxFlowFordFulkerson

Maximum flow with the Ford-Fulkerson algorithm
getShortestPathTree

Computes a shortest path tree
searchFlowPath

Find a maximum flow path
spTreeBellmanFord

Shortest path tree with Bellman-Ford algorithm
compactCycle

Compacts the nodes in a cycle into a single node
msArborEdmonds

Minimum cost arborescence with Edmonds' algorithm
optrees-package

Optimal Trees in Weighted Graphs