# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
SeparatorLiptonTarjanFC.h
Go to the documentation of this file.
1
32#pragma once
33
35
36#include <set>
37
38namespace ogdf {
39
40namespace planar_separators {
41
46public:
53 BFSTreeFC(GraphCopy& G, node rootNode) : ArrayBFSTree(G, rootNode) { construct(); }
54
55 void construct();
56};
57
63public:
70 TriangulatingBFSTree(GraphCopy& G, node rootNode) : ArrayBFSTree(G, rootNode) { construct(); }
71
72 void construct();
73
74 void visit(node v, node parent, adjEntry adj, SListPure<node>& bfs);
75};
76
77}
78
80
87public:
93 SeparatorLiptonTarjanFC(bool useTriBFS = false) : useTriangulatingBFS {useTriBFS} { }
94
95 virtual double getMaxSeparatorSize(int n) const override { return -1; }
96
97protected:
98 virtual bool doSeparate(const Graph& G, List<node>& separator, List<node>& first,
99 List<node>& second) override;
100
102 std::shared_ptr<ArrayBFSTree> tree;
103
104 virtual std::string getSpecificName() const override {
105 std::string name = "LTFC";
106 if (useTriangulatingBFS) {
107 name += "-triBFS";
108 }
109 return name;
110 }
111
121
128};
129
130}
Declaration of base class of all planar separator algorithms.
Class for adjacency list elements.
Definition Graph_d.h:79
Class for the representation of edges.
Definition Graph_d.h:300
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Class for the representation of nodes.
Definition Graph_d.h:177
Abstract description of all planar separator algorithms.
Definition SList.h:179
Computes planar separators using Fundamental Cycles.
virtual double getMaxSeparatorSize(int n) const override
Provides the maximal separator size that this algorithm guarantees as a function of the number of nod...
virtual std::string getSpecificName() const override
Returns the unique name of the core algorithm, to be combined with postprocessors later.
edge chooseEdge() const
Randomly selects the initial edge for the first cycle.
virtual bool doSeparate(const Graph &G, List< node > &separator, List< node > &first, List< node > &second) override
Core of the specific separation algorithm - override this in inheriting classes.
std::shared_ptr< ArrayBFSTree > tree
SeparatorLiptonTarjanFC(bool useTriBFS=false)
Constructor.
virtual bool findCycle(List< node > &separator, List< node > &first, List< node > &second)
Finds a cycle that works as a separator.
Abstract BFSTree that is realized via NodeArrays.
BFSTreeFC(GraphCopy &G, node rootNode)
Constructor.
Triangulating BFS tree that operates on a non-triangulated graph and constructs the triangulation tog...
void visit(node v, node parent, adjEntry adj, SListPure< node > &bfs)
TriangulatingBFSTree(GraphCopy &G, node rootNode)
Constructor.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.