Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSTCutDijkstra.h
Go to the documentation of this file.
1
32#pragma once
33
39
40namespace ogdf {
41
51template<typename TCost>
52class MinSTCutDijkstra : public MinSTCutModule<TCost> {
53public:
55
59 virtual bool call(const Graph& graph, const EdgeArray<TCost>& weight, node s, node t,
60 List<edge>& edgeList, edge e_st = nullptr) override;
61
65 virtual bool call(const Graph& graph, node s, node t, List<edge>& edgeList,
66 edge e_st = nullptr) override {
67 EdgeArray<TCost> weight(graph, 1);
68 return call(graph, weight, s, t, edgeList, e_st);
69 }
70
72};
73
74template<typename TCost>
75bool MinSTCutDijkstra<TCost>::call(const Graph& graph, const EdgeArray<TCost>& weight, node s,
76 node t, List<edge>& edgeList, edge e_st) {
77 delete m_gc;
78 m_gc = new GraphCopy(graph);
80
82
84
85 DualGraph dual(CE);
86 if (e_st != nullptr) {
87 e_st = m_gc->copy(e_st);
88 } else {
89 e_st = m_gc->searchEdge(m_gc->copy(s), m_gc->copy(t));
90 }
91 edgeList.clear();
92 node source = dual.dualNode(CE.rightFace(e_st->adjSource()));
93 node target = dual.dualNode(CE.leftFace(e_st->adjSource()));
94
95
98 for (edge e : m_gc->edges) {
99 if (e != e_st) {
100 weightDual[dual.dualEdge(e)] = weight[m_gc->original(e)];
101 sumOfWeights += weightDual[dual.dualEdge(e)];
103 }
104 }
107 sourceNodeList.pushFront(source);
109 NodeArray<TCost> distance(dual);
111 D.call(dual, weightDual, sourceNodeList, prevEdge, distance);
112
113 node v = target;
114 do {
115 edge eDual = prevEdge[v];
116 OGDF_ASSERT(eDual != nullptr);
117 edge eG = dual.primalEdge(eDual);
118 OGDF_ASSERT(eG != nullptr);
119 edgeList.pushBack(m_gc->original(eG));
120 MinSTCutModule<TCost>::m_direction[m_gc->original(eG)] = eDual->target() != v;
121 v = (v == eDual->target() ? eDual->source() : eDual->target());
122 } while (v != source);
123 return true;
124}
125}
Includes declaration of dual graph class.
Declaration of graph copy classes.
Template of base class of min-st-cut algorithms.
Combinatorial embeddings of planar graphs with modification functionality.
Dijkstra's single source shortest path algorithm.
Definition Dijkstra.h:53
void call(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition Dijkstra.h:246
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
const edge & dualEdge(edge e) const
Returns the edge in the dual graph corresponding to e.
Definition DualGraph.h:177
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
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
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
Min-st-cut algorithm, that calculates the cut by calculating the shortest path between the faces adja...
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.
virtual bool call(const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
The actual algorithm call.
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
Declaration of extended graph algorithms.
Implementation of Dijkstra's single source shortest path algorithm.
#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.