Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSTCutBFS.h
Go to the documentation of this file.
1
33#pragma once
34
37#include <ogdf/basic/Queue.h>
41
42namespace ogdf {
43
53template<typename TCost>
54class MinSTCutBFS : public MinSTCutModule<TCost> {
55public:
57
61 virtual bool call(const Graph& graph, node s, node t, List<edge>& edgeList,
62 edge e_st = nullptr) override {
63 return call(graph, nullptr, s, t, edgeList, e_st);
64 }
65
69 virtual bool call(const Graph& graph, const EdgeArray<TCost>& weight, node s, node t,
70 List<edge>& edgeList, edge e_st = nullptr) override {
71 return call(graph, &weight, s, t, edgeList, e_st);
72 }
73
75
76private:
82 bool call(const Graph& graph, const EdgeArray<TCost>* weight, node s, node t,
83 List<edge>& edgeList, edge e_st);
84};
85
86template<typename TCost>
87bool MinSTCutBFS<TCost>::call(const Graph& graph, const EdgeArray<TCost>* weight, node s, node t,
88 List<edge>& edgeList, edge e_st) {
89 bool weighted = (weight != nullptr);
90 delete m_gc;
91 m_gc = new GraphCopy(graph);
94 EdgeArray<edge> mapE(m_weightedGc, nullptr);
95
96 std::function<edge(edge)> orig = [&](edge e) -> edge { return m_gc->original(e); };
97
98 if (weighted) {
99 m_weightedGc.init(graph);
100 if (e_st != nullptr) {
101 e_st = m_weightedGc.copy(e_st);
102 }
103 s = m_weightedGc.copy(s);
104 t = m_weightedGc.copy(t);
105 List<edge> edges;
106 graph.allEdges(edges);
107 for (edge e : edges) {
108 mapE[m_weightedGc.copy(e)] = e;
109 if (m_weightedGc.copy(e) == e_st) {
110 continue;
111 }
112 OGDF_ASSERT((*weight)[e] >= 1);
113 TCost i = 1;
114 for (; i < (*weight)[e]; i++) {
115 edge copyEdge = m_weightedGc.copy(e);
116 edge newEdge = m_weightedGc.newEdge(copyEdge->source(), copyEdge->target());
117 m_weightedGc.move(newEdge, copyEdge->adjSource(), ogdf::Direction::before,
118 copyEdge->adjTarget(), ogdf::Direction::after);
119 mapE[newEdge] = e;
120 }
121 OGDF_ASSERT((*weight)[e] == i);
122 }
123 // we can't reinit m_gc, because it's possible that the original graph of m_gc
124 // doesn't exist anymore.
125 delete m_gc;
126 m_gc = new GraphCopy();
127 m_gc->init(m_weightedGc);
128 orig = [&](edge e) -> edge { return mapE[m_gc->original(e)]; };
130 } else {
132 }
133
135
136 DualGraph dual(CE);
137 if (e_st != nullptr) {
138 e_st = m_gc->copy(e_st);
139 } else {
140 e_st = m_gc->searchEdge(m_gc->copy(s), m_gc->copy(t));
141 }
142
143 edgeList.clear();
144 node source = dual.dualNode(CE.rightFace(e_st->adjSource()));
145 node target = dual.dualNode(CE.leftFace(e_st->adjSource()));
146
147 NodeArray<edge> spPred(dual, nullptr);
148 EdgeArray<node> prev(dual, nullptr);
149 EdgeArray<bool> direction(dual, true);
151 for (adjEntry adj : source->adjEntries) {
152 if (dual.primalEdge(adj->theEdge()) != e_st) {
153 queue.append(adj->theEdge());
154 prev[adj->theEdge()] = source;
155 }
156 }
157 // actual search (using bfs on directed dual)
158 for (;;) {
159 // next candidate edge
160 edge eCand = queue.pop();
161 bool dir = (eCand->source() == prev[eCand]);
162 node v = (dir ? eCand->target() : eCand->source());
163
164 // leads to an unvisited node?
165 if (spPred[v] == nullptr) {
166 // yes, then we set v's predecessor in search tree
167 spPred[v] = eCand;
168 direction[eCand] = dir;
169
170 // have we reached t ...
171 if (v == target) {
172 // ... then search is done.
173 // constructed list of used edges (translated to crossed
174 // edges entries in G) from t back to s (including first
175 // and last!)
176
177 do {
178 edge eDual = spPred[v];
179 OGDF_ASSERT(eDual != nullptr);
180 // this should be the right way round
181 edge eG = dual.primalEdge(eDual);
182 OGDF_ASSERT(eG != nullptr);
183 edgeList.pushBack(orig(eG));
185 v = prev[eDual];
186 } while (v != source);
187
188 break;
189 }
190
191 // append next candidate edges to queue
192 // (all edges leaving v)
193 for (adjEntry adj : v->adjEntries) {
194 if (prev[adj->theEdge()] == nullptr) {
195 queue.append(adj->theEdge());
196 prev[adj->theEdge()] = v;
197 }
198 }
199 }
200 }
201 if (weighted) {
202 auto prevIt = edgeList.begin();
203 for (auto it = prevIt.succ(); it != edgeList.end(); prevIt = it++) {
204 if (*prevIt == *it) {
205 edgeList.del(prevIt);
206 }
207 }
208 }
209 return true;
210}
211}
Includes declaration of dual graph class.
Declaration of graph copy classes.
Template of base class of min-st-cut algorithms.
Declaration and implementation of list-based queues (classes QueuePure<E> and Queue<E>).
Class for adjacency list elements.
Definition Graph_d.h:79
Combinatorial embeddings of planar graphs with modification functionality.
A dual graph including its combinatorial embedding of an embedded graph.
Definition DualGraph.h:56
const edge & primalEdge(edge e) const
Returns the edge in the primal graph corresponding to e.
Definition DualGraph.h:156
const node & dualNode(face f) const
Returns the node in the dual graph corresponding to f.
Definition DualGraph.h:170
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition Graph_d.h:344
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition Graph_d.h:347
node target() const
Returns the target node of the edge.
Definition Graph_d.h:338
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
void allEdges(CONTAINER &edgeContainer) const
Returns a container with all edges of the graph.
Definition Graph_d.h:695
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
void clear()
Removes all elements from the list.
Definition List.h:1610
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
void del(iterator it)
Removes it from the list.
Definition List.h:1595
iterator begin()
Returns an iterator to the first element of the list.
Definition List.h:375
iterator end()
Returns an iterator to one-past-last element of the list.
Definition List.h:393
Min-st-cut algorithm, that calculates the cut by doing a depth first search over the dual graph of of...
Definition MinSTCutBFS.h:54
virtual bool call(const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
The actual algorithm call.
Definition MinSTCutBFS.h:61
virtual bool call(const Graph &graph, const EdgeArray< TCost > &weight, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
The actual algorithm call.
Definition MinSTCutBFS.h:69
bool preprocessingDual(const Graph &graph, GraphCopy &gc, CombinatorialEmbedding &CE, node source, node target, edge e_st)
This method preprocesses gc for minstcut calculations, by adding an st-edge if needed and embedding g...
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
Implementation of list-based queues.
Definition Queue.h:50
Declaration of extended graph algorithms.
Implementation of Dijkstra's single source shortest path algorithm.
EdgeElement * edge
The type of edges.
Definition Graph_d.h:68
#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.