# optrees v1.0

0

0th

Percentile

## Optimal Trees in Weighted Graphs

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.

## Functions in optrees

 Name Description 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 No Results!