Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MaxFlowSTPlanarItaiShiloach< TCap > Class Template Reference

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< edgem_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< NodeTypem_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...
 
EpsilonTestm_et
 Pointer to the used EpsilonTest. More...
 
EdgeArray< TCap > * m_flow
 Pointer to (extern) flow array. More...
 
const Graphm_G
 Pointer to the given graph. More...
 
const nodem_s
 Pointer to the source node. More...
 
const nodem_t
 Pointer to the sink node. More...
 

Detailed Description

template<typename TCap>
class ogdf::MaxFlowSTPlanarItaiShiloach< TCap >

Computes a max flow in s-t-planar network via uppermost paths.

Definition at line 49 of file MaxFlowSTPlanarItaiShiloach.h.

Member Enumeration Documentation

◆ EdgePathType

template<typename TCap >
enum ogdf::MaxFlowSTPlanarItaiShiloach::EdgePathType
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 94 of file MaxFlowSTPlanarItaiShiloach.h.

◆ NodeType

template<typename TCap >
enum ogdf::MaxFlowSTPlanarItaiShiloach::NodeType
strongprivate

Each node has a certain type depending on its participation in any path.

Enumerator
New 
Path 
Done 

Definition at line 83 of file MaxFlowSTPlanarItaiShiloach.h.

Constructor & Destructor Documentation

◆ ~MaxFlowSTPlanarItaiShiloach()

template<typename TCap >
ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::~MaxFlowSTPlanarItaiShiloach ( )
inline

Free allocated ressources.

Definition at line 125 of file MaxFlowSTPlanarItaiShiloach.h.

Member Function Documentation

◆ appendEdge()

template<typename TCap >
void ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::appendEdge ( const edge  e)
inlineprivate

Appends an edge to the current path.

Parameters
eThe edge to be added, must not be part of any path so far

Definition at line 312 of file MaxFlowSTPlanarItaiShiloach.h.

◆ computeFlowAfterValue()

template<typename TCap >
void ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::computeFlowAfterValue ( )
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 198 of file MaxFlowSTPlanarItaiShiloach.h.

◆ computeValue()

template<typename TCap >
TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::computeValue ( const EdgeArray< TCap > &  originalCapacities,
const node source,
const node target 
)
inlinevirtual

Computes the maximal flow from source to sink.

Assumes the graph to be s-t-planary embedded.

Parameters
originalCapacitiesthe positive capacity of each edge
sourcethe source node
targetthe sink node

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 138 of file MaxFlowSTPlanarItaiShiloach.h.

◆ dropEdge()

template<typename TCap >
void ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::dropEdge ( const edge  e)
inlineprivate

Removes a single edge from the current path.

Note that the edge is not actually removed from the graph.

Parameters
eThe edge to be removed, must be part of a path

Definition at line 332 of file MaxFlowSTPlanarItaiShiloach.h.

◆ findUppermostPath()

template<typename TCap >
bool ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::findUppermostPath ( const edge  saturatedEdge)
inlineprivate

Establishes the next uppermost path.

Parameters
saturatedEdgeThe edge saturated most recently

Definition at line 221 of file MaxFlowSTPlanarItaiShiloach.h.

◆ getPathType()

template<typename TCap >
EdgePathType ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::getPathType ( const edge  e) const
inlineprivate

Performs an alternating backtracking from source and target to determine whether the new node is part of the source or target path.

Parameters
eThe newly encountered edge from the old node to a new one.

Definition at line 361 of file MaxFlowSTPlanarItaiShiloach.h.

◆ shiftPriority()

template<typename TCap >
TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::shiftPriority ( TCap  priority)
inlineprivate

see unshiftedPriority

Parameters
priorityoriginal priority
Returns
shifted priority

Definition at line 75 of file MaxFlowSTPlanarItaiShiloach.h.

◆ unshiftedPriority()

template<typename TCap >
TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::unshiftedPriority ( edge  e)
inlineprivate

To work with unsigned, we need a priority shifting of the elements in the priority queue.

Parameters
eedge in m_prioritizedEdges
Returns
unshifted priority

Definition at line 58 of file MaxFlowSTPlanarItaiShiloach.h.

◆ unshiftedTopPriority()

template<typename TCap >
TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::unshiftedTopPriority ( )
inlineprivate

see unshiftedPriority

Returns
unshifted priority of top element

Definition at line 66 of file MaxFlowSTPlanarItaiShiloach.h.

Member Data Documentation

◆ m_commonFaceAdj

template<typename TCap >
adjEntry ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_commonFaceAdj
private

Definition at line 101 of file MaxFlowSTPlanarItaiShiloach.h.

◆ m_edgeCounter

template<typename TCap >
NodeArray<int> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_edgeCounter
private

The number of edges visited from each node.

Definition at line 107 of file MaxFlowSTPlanarItaiShiloach.h.

◆ m_partialFlow

template<typename TCap >
TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_partialFlow
private

The flow reached thus far (monotonically increasing).

Definition at line 119 of file MaxFlowSTPlanarItaiShiloach.h.

◆ m_pred

template<typename TCap >
NodeArray<edge> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_pred
private

The predecessor of each node in the currently uppermost path.

Definition at line 110 of file MaxFlowSTPlanarItaiShiloach.h.

◆ m_prioritizedEdges

template<typename TCap >
PrioritizedMapQueue<edge, TCap>* ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_prioritizedEdges = nullptr
private

A priority queue for storing all edges currently in a path.

Definition at line 116 of file MaxFlowSTPlanarItaiShiloach.h.

◆ m_status

template<typename TCap >
NodeArray<NodeType> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_status
private

The status of each node.

Definition at line 113 of file MaxFlowSTPlanarItaiShiloach.h.

◆ m_visited

template<typename TCap >
EdgeArray<bool> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_visited
private

Whether each edge has was visited.

Definition at line 104 of file MaxFlowSTPlanarItaiShiloach.h.


The documentation for this class was generated from the following file: