graphalg Directory Reference

Directory dependency graph for graphalg:

Directories
	planar_separator
	steiner_tree

Files
	AStarSearch.h
	Implementation of the A* informed search algorithm.
	Clusterer.h
	Declaration of Clusterer class that computes a clustering for a given graph based on the local neighborhood structure of each edge.
	ClustererModule.h
	Declaration of interface for clustering algorithms that compute a clustering for a given graph based on some structural or semantical properties.
	ConnectivityTester.h
	Class for computing the connectivity of a graph.
	ConvexHull.h
	Declaration of doubly linked lists and iterators.
	Dijkstra.h
	Implementation of Dijkstra's single source shortest path algorithm.
	EdgeIndependentSpanningTrees.h
	Declaration of ogdf::EdgeIndependentSpanningTrees.
	GraphReduction.h
	Declaration and implementation of GraphReduction class reduces by Leaves & Chains.
	Matching.h
	Declares simple matching functions.
	MaxAdjOrdering.h
	Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph.
	MaxFlowEdmondsKarp.h
	Implementation of Edmonds-Karp max-flow algorithm.
	MaxFlowGoldbergTarjan.h
	Declaration and implementation of Goldberg-Tarjan max-flow algorithm with global relabeling and gap relabeling heuristic.
	MaxFlowModule.h
	Interface for Max Flow Algorithms.
	MaxFlowSTPlanarDigraph.h
	Max-Flow on s-t-planar graphs (s and t lie on the boundary of the outer face) via shortest paths in the dual.
	MaxFlowSTPlanarItaiShiloach.h
	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).
	MaximumDensitySubgraph.h
	Declares maximum density subgraph algorithms.
	MinCostFlowModule.h
	Definition of ogdf::MinCostFlowModule class template.
	MinCostFlowReinelt.h
	Definition of ogdf::MinCostFlowReinelt class template.
	MinimumCutModule.h
	Declaration of ogdf::MinimumCutModule.
	MinimumCutNagamochiIbaraki.h
	Calculate minimum cut value for a given Graph.
	MinimumCutStoerWagner.h
	Declaration and implementation of ogdf::MinimumCutStoerWagner.
	MinSTCutBFS.h
	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)
	MinSTCutDijkstra.h
	MinSTCutDijkstra class template.
	MinSTCutMaxFlow.h
	Declaration of min-st-cut algorithms parameterized by max-flow alorithm.
	MinSTCutModule.h
	Template of base class of min-st-cut algorithms.
	MinSteinerTreeDirectedCut.h
	Classes for solving the Steiner tree problem exactly with a branch&cut algorithm.
	MinSteinerTreeDualAscent.h
	Implementation of an approxmiation algorithm for Steiner tree problems given by Richard T.
	MinSteinerTreeGoemans139.h
	Implementation of an LP-based 1.39+epsilon Steiner tree approximation algorithm by Goemans et al.
	MinSteinerTreeKou.h
	Declaration and implementation of the class computing a 2(1-1/l) minimum Steiner tree approximation according to the algorithm of Kou et al.
	MinSteinerTreeMehlhorn.h
	Implementation of Mehlhorn's minimum Steiner tree 2(1-1/l)-approximation algorithm.
	MinSteinerTreeModule.h
	Declaration of ogdf::MinSteinerTreeModule.
	MinSteinerTreePrimalDual.h
	Implementation of an approxmiation algorithm for Steiner tree problems provided by Michel X.
	MinSteinerTreeRZLoss.h
	Implementation of the 1.55-approximation algorithm for the Minimum Steiner Tree problem by Robins and Zelikovsky.
	MinSteinerTreeShore.h
	Implementation of Shore, Foulds and Gibbons' branch and bound algorithm for solving minimum Steiner tree problems.
	MinSteinerTreeTakahashi.h
	Implementation of the 2(1-1/l)-approximation algorithm for the minimum Steiner tree problem by Matsuyama and Takahashi.
	MinSteinerTreeZelikovsky.h
	Implementation of Zelikovsky's 11/6-approximation algorithm for the minimum Steiner tree problem.
	ModifiedNibbleClusterer.h
	Implementation of a fast and simple clustering algorithm, Modified Nibble Clusterer.
	PageRank.h
	Declaration of basic page rank.
	PlanarSeparatorModule.h
	Declaration of base class of all planar separator algorithms.
	SeparatorDual.h
	Declaration of class SeparatorDual.
	SeparatorDualFC.h
	Declaration of class SeparatorDualFC, which applies the Fundamental Cycle Lemma directly to obtain a cycle.
	SeparatorHarPeled.h
	Declaration of class SeparatorHarPeled.
	SeparatorLiptonTarjan.h
	Declaration of class SeparatorLiptonTarjan.
	SeparatorLiptonTarjanFC.h
	Declaration of class SeparatorLiptonTarjanFC.
	ShortestPathAlgorithms.h
	Declaration of several shortest path algorithms.
	ShortestPathModule.h
	Declaration of base class of shortest path algorithms including some useful functions dealing with shortest paths flow (generater, checker).
	ShortestPathWithBFM.h
	Declaration of class ShortestPathWithBFM which computes shortest paths via Bellman-Ford-Moore.
	SpannerBasicGreedy.h
	Implementation of the basic greedy (2k-1)-spanner algorithm of Althöfer et al.
	SpannerBaswanaSen.h
	Implementation of the random cluster-based k-spanner algorithm of Baswana and Sen 2007.
	SpannerBerman.h
	Implementation of an k-spanner approximation algorithm from Berman et al.
	SpannerBermanDisconnected.h
	Implementation of an k-spanner approximation algorithm from Berman et al.
	SpannerElkinNeiman.h
	Implementation of the random k-spanner algorithm of Elkin and Neiman 2018.
	SpannerIteratedWrapper.h
	A wrapper class for iterating calls to spanner algorithms.
	SpannerKortsarzPeleg.h
	Implementation of the 2-spanner approximation algorithm of Kortsarz and Peleg 1994.
	SpannerModule.h
	Basic module for spanner algorithms.
	SteinerTreeLowerBoundDualAscent.h
	Definition of the ogdf::SteinerTreeLowerBoundDualAscent class template.
	SteinerTreePreprocessing.h
	Definition of the ogdf::SteinerTreePreprocessing class template.
	Triconnectivity.h
	Declares class Triconnectivity which realizes the Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-graph.
	Voronoi.h
	Definition of ogdf::Voronoi class template.