# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
MinSTCutModule.h
Go to the documentation of this file.
1
32#pragma once
33
36
37namespace ogdf {
38
39template<typename TCost>
41public:
46
60 virtual bool call(const Graph& graph, const EdgeArray<TCost>& weight, node s, node t,
61 List<edge>& edgeList, edge e_st = nullptr) = 0;
62
75 virtual bool call(const Graph& graph, node s, node t, List<edge>& edgeList,
76 edge e_st = nullptr) = 0;
77
78 virtual ~MinSTCutModule() { delete m_gc; }
79
87 virtual bool direction(edge e) {
89 OGDF_ASSERT(m_direction[e] != -1);
90 return m_direction[e];
91 }
92
93protected:
95 GraphCopy* m_gc = nullptr;
96
109 node source, node target, edge e_st) {
110 node gcS(gc.copy(source));
111 node gcT(gc.copy(target));
113 bool isSTplanarEmbeded(false);
114 if (gc.representsCombEmbedding()) {
115 CE.init(gc);
117 isSTplanarEmbeded = (adjS != nullptr);
118 }
119 if (isSTplanarEmbeded) {
120 if (e_st == nullptr) {
122 }
123 } else {
124 if (e_st == nullptr) {
125 gc.newEdge(gcS, gcT);
126 }
127 if (!planarSTEmbed(gc, gcS, gcT)) {
128 return false;
129 }
130 CE.init(gc);
131 }
132 return true;
133 }
134};
135}
Declaration of CombinatorialEmbedding and face.
Definition Graph_d.h:79
Combinatorial embeddings of planar graphs with modification functionality.
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
int numberOfEdges() const
Returns the number of edges in the graph.
Definition Graph_d.h:625
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
virtual bool call(const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr)=0
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...
virtual bool direction(edge e)
Returns the direction of e in the cut.
MinSTCutModule()
default constructor (empty)
virtual bool call(const Graph &graph, const EdgeArray< TCost > &weight, node s, node t, List< edge > &edgeList, edge e_st=nullptr)=0
The actual algorithm call.
EdgeArray< int > m_direction
Class for the representation of nodes.
Definition Graph_d.h:177
Declaration of extended graph algorithms.
bool planarSTEmbed(Graph &graph, node s, node t)
s-t-planarly embeds a graph.
#define OGDF_ASSERT(expr)