|
|||
|
|
|
|||
|
|
Computes a max flow in s-t-planar network via uppermost paths. More...
#include <ogdf/graphalg/MaxFlowSTPlanarItaiShiloach.h>
Inheritance diagram for ogdf::MaxFlowSTPlanarItaiShiloach< TCap >:Public Member Functions | |
| ~MaxFlowSTPlanarItaiShiloach () | |
| Free allocated ressources. More... | |
| void | computeFlowAfterValue () |
| Computes the actual flow on each edge. More... | |
| TCap | computeValue (const EdgeArray< TCap > &originalCapacities, const node &source, const node &target) |
| Computes the maximal flow from source to sink. More... | |
| Public Member Functions inherited from ogdf::MaxFlowModule< TCap > | |
| MaxFlowModule () | |
| Empty Constructor. More... | |
| MaxFlowModule (const Graph &graph, EdgeArray< TCap > *flow=nullptr) | |
| Constructor that calls init. More... | |
| virtual | ~MaxFlowModule () |
| Destructor that deletes m_flow if it is an internal flow array. More... | |
| TCap | computeFlow (EdgeArray< TCap > &cap, node &s, node &t, EdgeArray< TCap > &flow) |
| Only a shortcut for computeValue and computeFlowAfterValue. More... | |
| void | computeFlowAfterValue (EdgeArray< TCap > &flow) |
Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phases. The flow is stored in the parameter flow. More... | |
| virtual void | init (const Graph &graph, EdgeArray< TCap > *flow=nullptr) |
Initialize the problem with a graph and optional flow array. If no flow array is given, a new ("internal") array will be created. If a flow array is given, the algorithm uses this "external" array. More... | |
| bool | isFeasibleInstance () const |
| Return whether the instance is feasible, i.e. the capacities are non-negative. More... | |
| void | useEpsilonTest (const double &eps) |
| Change the used EpsilonTest from StandardEpsilonTest to a user given EpsilonTest. More... | |
Private Types | |
| enum | EdgePathType { EdgePathType::NoPath, EdgePathType::SourcePath, EdgePathType::TargetPath, EdgePathType::Unknown } |
| Each edge may be part of the source or target path. More... | |
| enum | NodeType { NodeType::New, NodeType::Path, NodeType::Done } |
| Each node has a certain type depending on its participation in any path. More... | |
Private Member Functions | |
| void | appendEdge (const edge e) |
| Appends an edge to the current path. More... | |
| void | dropEdge (const edge e) |
| Removes a single edge from the current path. More... | |
| bool | findUppermostPath (const edge saturatedEdge) |
| Establishes the next uppermost path. More... | |
| EdgePathType | getPathType (const edge e) const |
| Performs an alternating backtracking from source and target to determine whether the new node is part of the source or target path. More... | |
| TCap | shiftPriority (TCap priority) |
| see unshiftedPriority More... | |
| TCap | unshiftedPriority (edge e) |
| To work with unsigned, we need a priority shifting of the elements in the priority queue. More... | |
| TCap | unshiftedTopPriority () |
| see unshiftedPriority More... | |
Private Attributes | |
| adjEntry | m_commonFaceAdj |
| NodeArray< int > | m_edgeCounter |
| The number of edges visited from each node. More... | |
| TCap | m_partialFlow |
| The flow reached thus far (monotonically increasing). More... | |
| NodeArray< edge > | m_pred |
| The predecessor of each node in the currently uppermost path. More... | |
| PrioritizedMapQueue< edge, TCap > * | m_prioritizedEdges = nullptr |
| A priority queue for storing all edges currently in a path. More... | |
| NodeArray< NodeType > | m_status |
| The status of each node. More... | |
| EdgeArray< bool > | m_visited |
| Whether each edge has was visited. More... | |
Additional Inherited Members | |
| Protected Attributes inherited from ogdf::MaxFlowModule< TCap > | |
| const EdgeArray< TCap > * | m_cap |
| Pointer to the given capacity array. More... | |
| EpsilonTest * | m_et |
| Pointer to the used EpsilonTest. More... | |
| EdgeArray< TCap > * | m_flow |
| Pointer to (extern) flow array. More... | |
| const Graph * | m_G |
| Pointer to the given graph. More... | |
| const node * | m_s |
| Pointer to the source node. More... | |
| const node * | m_t |
| Pointer to the sink node. More... | |
Computes a max flow in s-t-planar network via uppermost paths.
Definition at line 52 of file MaxFlowSTPlanarItaiShiloach.h.
|
strongprivate |
Each edge may be part of the source or target path.
We do not store this information. It is only a temporary variable in two routines.
| Enumerator | |
|---|---|
| NoPath | |
| SourcePath | |
| TargetPath | |
| Unknown | |
Definition at line 87 of file MaxFlowSTPlanarItaiShiloach.h.
|
strongprivate |
Each node has a certain type depending on its participation in any path.
| Enumerator | |
|---|---|
| New | |
| Path | |
| Done | |
Definition at line 80 of file MaxFlowSTPlanarItaiShiloach.h.
|
inline |
Free allocated ressources.
Definition at line 113 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlineprivate |
Appends an edge to the current path.
| e | The edge to be added, must not be part of any path so far |
Definition at line 288 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlinevirtual |
Computes the actual flow on each edge.
Most edges have already been assigned their respective flow values. However, there might be some edges remaining (as part of tangling paths from source and sink).
Implements ogdf::MaxFlowModule< TCap >.
Definition at line 183 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlinevirtual |
Computes the maximal flow from source to sink.
Assumes the graph to be s-t-planary embedded.
| originalCapacities | the positive capacity of each edge |
| source | the source node |
| target | the sink node |
Implements ogdf::MaxFlowModule< TCap >.
Definition at line 124 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlineprivate |
Removes a single edge from the current path.
Note that the edge is not actually removed from the graph.
| e | The edge to be removed, must be part of a path |
Definition at line 308 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlineprivate |
Establishes the next uppermost path.
| saturatedEdge | The edge saturated most recently |
Definition at line 204 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlineprivate |
Performs an alternating backtracking from source and target to determine whether the new node is part of the source or target path.
| e | The newly encountered edge from the old node to a new one. |
Definition at line 337 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlineprivate |
| priority | original priority |
Definition at line 72 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlineprivate |
To work with unsigned, we need a priority shifting of the elements in the priority queue.
| e | edge in m_prioritizedEdges |
Definition at line 59 of file MaxFlowSTPlanarItaiShiloach.h.
|
inlineprivate |
Definition at line 65 of file MaxFlowSTPlanarItaiShiloach.h.
|
private |
Definition at line 89 of file MaxFlowSTPlanarItaiShiloach.h.
|
private |
The number of edges visited from each node.
Definition at line 95 of file MaxFlowSTPlanarItaiShiloach.h.
|
private |
The flow reached thus far (monotonically increasing).
Definition at line 107 of file MaxFlowSTPlanarItaiShiloach.h.
|
private |
The predecessor of each node in the currently uppermost path.
Definition at line 98 of file MaxFlowSTPlanarItaiShiloach.h.
|
private |
A priority queue for storing all edges currently in a path.
Definition at line 104 of file MaxFlowSTPlanarItaiShiloach.h.
|
private |
The status of each node.
Definition at line 101 of file MaxFlowSTPlanarItaiShiloach.h.
|
private |
Whether each edge has was visited.
Definition at line 92 of file MaxFlowSTPlanarItaiShiloach.h.
