Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
EdgeIndependentSpanningTrees.h
Go to the documentation of this file.
1
32#pragma once
33
35#include <ogdf/basic/List.h>
36
37#include <set>
38#include <vector>
39
40namespace ogdf {
41
52public:
62
65
69
71 EdgeIndependentSpanningTrees(const Graph& G, node root) : m_G {&G}, m_root {root} { }
72
75
77 bool findOne(unsigned int k, Solution& f) const;
78
80 List<Solution> findAll(unsigned int k) const;
81
83 List<Solution> findAllPerm(unsigned int k) const;
84
86 const Graph* getGraph() const { return m_G; }
87
89 void setGraph(const Graph& G) {
90 OGDF_ASSERT(!G.empty());
91 m_G = &G;
92 }
93
95 node getRoot() const { return m_root; }
96
98 void setRoot(node root) { m_root = root; }
99
100protected:
103 void findDo(unsigned int k, std::function<bool(Solution&)> func) const;
104
105private:
106 const Graph* m_G;
108
111 const std::vector<unsigned int>& perm) const;
112
114 bool checkNewTree(const Solution& f1, const Solution& f2, unsigned int k) const;
115
117 bool createParentRel(const Solution& f, unsigned int j, NodeArray<adjEntry>& parent) const;
118
120 bool checkIndependence(const std::vector<NodeArray<adjEntry>>& parents, unsigned int k) const;
121
124 unsigned int p1, unsigned int p2) const;
125
127 bool iterate(Solution& f, unsigned int j, unsigned int k) const;
128
130 bool isFinished(const Solution& f, unsigned int k) const;
131
133 unsigned int createVals(const Solution& f, unsigned int k, std::vector<edge>& tree) const;
134
136 void clearTree(Solution& f, unsigned int j) const;
137
139 bool nextSpanningTree(unsigned int& t, std::vector<edge>& tree) const;
140
142 bool pathExists(const std::vector<edge>& tree, node v1, node v2, unsigned int t) const;
143
145 bool isInSubGraph(const std::vector<edge>& sub, const edge& e, unsigned int t) const;
146
148 bool createInitialSpanningTrees(Solution& f, unsigned int k) const;
149
150 bool insertNewTree(Solution& f, unsigned int t, unsigned int j, std::vector<edge>& tree) const;
151
153 bool findAndInsertNextTree(Solution& f, unsigned int& t, unsigned int j,
154 std::vector<edge>& tree) const;
155};
156
157}
Declaration and implementation of EdgeArray class.
Declaration of doubly linked lists and iterators.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Calculates k edge-independent spanning trees of a graph.
bool insertNewTree(Solution &f, unsigned int t, unsigned int j, std::vector< edge > &tree) const
bool checkTwoPathIndependence(const std::vector< NodeArray< adjEntry > > &parents, node v, unsigned int p1, unsigned int p2) const
Checks two paths for independence.
node getRoot() const
Returns the associated root node.
bool findAndInsertNextTree(Solution &f, unsigned int &t, unsigned int j, std::vector< edge > &tree) const
Iterates using nextSpanningTree until insertNewTree succeeds.
bool nextSpanningTree(unsigned int &t, std::vector< edge > &tree) const
Calculates the next spanning tree after tree using backtracking.
bool findOne(unsigned int k, Solution &f) const
Finds k edge-independent spanning trees in graph m_G rooted at m_root.
bool isInSubGraph(const std::vector< edge > &sub, const edge &e, unsigned int t) const
Checks whether e is in the subgraph.
EdgeIndependentSpanningTrees()
Creates an instance of edge-independent spanning tree withou associated graph and root.
const Graph * getGraph() const
Returns a pointer to the associated graph.
bool checkIndependence(const std::vector< NodeArray< adjEntry > > &parents, unsigned int k) const
Checks k spanning trees for independence.
EdgeIndependentSpanningTrees(const Graph &G)
Creates an instance of edge-independent spanning tree and sets the graph.
bool isFinished(const Solution &f, unsigned int k) const
Checks whether iteration is finished.
void findDo(unsigned int k, std::function< bool(Solution &)> func) const
Finds k edge-independent spanning trees and invokes func for each one, The search is stopped if func ...
void setGraph(const Graph &G)
Sets the associated graph.
bool createInitialSpanningTrees(Solution &f, unsigned int k) const
Creates first k spanning trees.
const Graph * m_G
The associated graph.
List< Solution > findAllPerm(unsigned int k) const
Finds all k edge-independent spanning trees in graph m_G rooted at m_root, including permutations.
List< Solution > findAll(unsigned int k) const
Finds all k edge-independent spanning trees in graph m_G rooted at m_root.
bool createParentRel(const Solution &f, unsigned int j, NodeArray< adjEntry > &parent) const
Creates a parent relation, which for each node in the associated graph contains the adjEntry pointing...
void clearTree(Solution &f, unsigned int j) const
Clears the j-th Tree from f.
bool checkNewTree(const Solution &f1, const Solution &f2, unsigned int k) const
Takes two edge-independent spanning trees and checks for them being unequal under all permutations.
~EdgeIndependentSpanningTrees()=default
Destructor.
unsigned int createVals(const Solution &f, unsigned int k, std::vector< edge > &tree) const
Creates the values needed for nextSpanningTree from f.
bool checkOnePermUnequal(const Solution &f1, const Solution &f2, const std::vector< unsigned int > &perm) const
Takes two edge-independent spanning trees, permutes one and checks for them being unequal.
bool iterate(Solution &f, unsigned int j, unsigned int k) const
Iterates over all subgraphs.
void setRoot(node root)
Sets the associated root node.
EdgeIndependentSpanningTrees(const Graph &G, node root)
Creates an instance of edge-independent spanning tree and sets the graph and root node.
bool pathExists(const std::vector< edge > &tree, node v1, node v2, unsigned int t) const
Checks whether v1 and v2 are connected in the subgraph.
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
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.