Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

graphalg Directory Reference
+ Directory dependency graph for graphalg:

Directories

directory  steiner_tree
 

Files

file  AStarSearch.h [code]
 Implementation of the A* informed search algorithm.
 
file  Clusterer.h [code]
 Declaration of Clusterer class that computes a clustering for a given graph based on the local neighborhood structure of each edge. Uses the criteria by Auber, Chiricota, Melancon for small-world graphs to compute clustering index and edge strength.
 
file  ClustererModule.h [code]
 Declaration of interface for clustering algorithms that compute a clustering for a given graph based on some structural or semantical properties.
 
file  ConnectivityTester.h [code]
 Class for computing the connectivity of a graph.
 
file  ConvexHull.h [code]
 Declaration of doubly linked lists and iterators.
 
file  Dijkstra.h [code]
 Implementation of Dijkstra's single source shortest path algorithm.
 
file  EdgeIndependentSpanningTrees.h [code]
 Declaration of ogdf::EdgeIndependentSpanningTrees.
 
file  GraphReduction.h [code]
 Declaration and implementation of GraphReduction class reduces by Leaves & Chains.
 
file  Matching.h [code]
 Declares simple matching functions.
 
file  MaxAdjOrdering.h [code]
 Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph.
 
file  MaxFlowEdmondsKarp.h [code]
 Implementation of Edmonds-Karp max-flow algorithm. Runtime O( |E|^2 * |V| )
 
file  MaxFlowGoldbergTarjan.h [code]
 Declaration and implementation of Goldberg-Tarjan max-flow algorithm with global relabeling and gap relabeling heuristic.
 
file  MaxFlowModule.h [code]
 Interface for Max Flow Algorithms.
 
file  MaxFlowSTPlanarDigraph.h [code]
 Max-Flow on s-t-planar graphs (s and t lie on the boundary of the outer face) via shortest paths in the dual. See [Ahuja, Magnanti, Orlin: Network Flows. Section 8.4]. Runtime: O(V log V).
 
file  MaxFlowSTPlanarItaiShiloach.h [code]
 Implementation of the maximum flow algorithm for s-t-planar graphs by Alon Itai and Yossi Shiloach (See "Maximum Flow in Planar Networks", p.135, 1979, Society for Industrial and Applied Mathematics).
 
file  MinCostFlowModule.h [code]
 Definition of ogdf::MinCostFlowModule class template.
 
file  MinCostFlowReinelt.h [code]
 Definition of ogdf::MinCostFlowReinelt class template.
 
file  MinimumCut.h [code]
 Declares & implements a minimum-cut algorithm according to an approach of Stoer and Wagner 1997. However, no Priority Queues are used as suggested in the approach. Should be adapted to improve performance.
 
file  MinSTCutBFS.h [code]
 Declaration of min-st-cut algorithm which calculates the min-st-cut of an st-planar graph by doing a BFS on the dual graph (class MinSTCutDFS)
 
file  MinSTCutDijkstra.h [code]
 MinSTCutDijkstra class template.
 
file  MinSTCutMaxFlow.h [code]
 Declaration of min-st-cut algorithms parameterized by max-flow alorithm.
 
file  MinSTCutModule.h [code]
 Template of base class of min-st-cut algorithms.
 
file  MinSteinerTreeDirectedCut.h [code]
 Classes for solving the Steiner tree problem exactly with a branch&cut algorithm. The used ILP formulation is the directed cut formulation.
 
file  MinSteinerTreeDualAscent.h [code]
 Implementation of an approxmiation algorithm for Steiner tree problems given by Richard T. Wong.
 
file  MinSteinerTreeGoemans139.h [code]
 Implementation of an LP-based 1.39+epsilon Steiner tree approximation algorithm by Goemans et al.
 
file  MinSteinerTreeKou.h [code]
 Declaration and implementation of the class computing a 2(1-1/l) minimum Steiner tree approximation according to the algorithm of Kou et al.
 
file  MinSteinerTreeMehlhorn.h [code]
 Implementation of Mehlhorn's minimum Steiner tree 2(1-1/l)-approximation algorithm.
 
file  MinSteinerTreeModule.h [code]
 Declaration of ogdf::MinSteinerTreeModule.
 
file  MinSteinerTreePrimalDual.h [code]
 Implementation of an approxmiation algorithm for Steiner tree problems provided by Michel X. Goemans and David P. Williamson.
 
file  MinSteinerTreeRZLoss.h [code]
 Implementation of the 1.55-approximation algorithm for the Minimum Steiner Tree problem by Robins and Zelikovsky.
 
file  MinSteinerTreeShore.h [code]
 Implementation of Shore, Foulds and Gibbons' branch and bound algorithm for solving minimum Steiner tree problems.
 
file  MinSteinerTreeTakahashi.h [code]
 Implementation of the 2(1-1/l)-approximation algorithm for the minimum Steiner tree problem by Matsuyama and Takahashi.
 
file  MinSteinerTreeZelikovsky.h [code]
 Implementation of Zelikovsky's 11/6-approximation algorithm for the minimum Steiner tree problem.
 
file  ModifiedNibbleClusterer.h [code]
 Implementation of a fast and simple clustering algorithm, Modified Nibble Clusterer.
 
file  PageRank.h [code]
 Declaration of basic page rank.
 
file  ShortestPathAlgorithms.h [code]
 Declaration of several shortest path algorithms.
 
file  ShortestPathModule.h [code]
 Declaration of base class of shortest path algorithms including some useful functions dealing with shortest paths flow (generater, checker).
 
file  ShortestPathWithBFM.h [code]
 Declaration of class ShortestPathWithBFM which computes shortest paths via Bellman-Ford-Moore.
 
file  SteinerTreeLowerBoundDualAscent.h [code]
 Definition of the ogdf::SteinerTreeLowerBoundDualAscent class template.
 
file  SteinerTreePreprocessing.h [code]
 Definition of the ogdf::SteinerTreePreprocessing class template.
 
file  Triconnectivity.h [code]
 Declares class Triconnectivity which realizes the Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-graph.
 
file  Voronoi.h [code]
 Definition of ogdf::Voronoi class template.