#include <flow_graph.h>

Inheritance diagram for util::FlowGraph< NodeIndexType, ArcIndexType >:

Public Member Functions
	FlowGraph ()=default

	FlowGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)

NodeIndexType	Head (ArcIndexType arc) const

NodeIndexType	Tail (ArcIndexType arc) const

ArcIndexType	OppositeArc (ArcIndexType arc) const

util::IntegerRange< ArcIndexType >	OutgoingArcs (NodeIndexType node) const
	Iteration.

util::IntegerRange< ArcIndexType >	OutgoingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const

util::IntegerRange< ArcIndexType >	OutgoingOrOppositeIncomingArcs (NodeIndexType node) const

util::IntegerRange< ArcIndexType >	OutgoingOrOppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const

absl::Span< const NodeIndexType >	operator[] (NodeIndexType node) const

void	ReserveArcs (ArcIndexType bound) override

void	AddNode (NodeIndexType node)

ArcIndexType	AddArc (NodeIndexType tail, NodeIndexType head)

void	Build ()

void	Build (std::vector< ArcIndexType > *permutation)

void	SetDetectReverse (bool value)

void	SetSortByHead (bool value)

Public Member Functions inherited from util::BaseGraph< int32_t, int32_t, false >
	BaseGraph ()

	BaseGraph (const BaseGraph &)=default

BaseGraph &	operator= (const BaseGraph &)=default

virtual	~BaseGraph ()=default

int32_t	num_nodes () const

int32_t	size () const

int32_t	num_arcs () const
	Returns the number of valid arcs in the graph.

IntegerRange< NodeIndex >	AllNodes () const
	BaseGraph implementation -------------------------------------------------—.

IntegerRange< ArcIndex >	AllForwardArcs () const

bool	IsNodeValid (int32_t node) const
	Returns true if the given node is a valid node of the graph.

bool	IsArcValid (int32_t arc) const

int32_t	node_capacity () const
	Capacity reserved for future nodes, always >= num_nodes_.

int32_t	arc_capacity () const
	Capacity reserved for future arcs, always >= num_arcs_.

virtual void	ReserveNodes (int32_t bound)

virtual void	ReserveArcs (int32_t bound)

void	Reserve (int32_t node_capacity, int32_t arc_capacity)

void	FreezeCapacities ()

Additional Inherited Members
Public Types inherited from util::BaseGraph< int32_t, int32_t, false >
typedef int32_t	NodeIndex

typedef int32_t	ArcIndex

Static Public Attributes inherited from util::BaseGraph< int32_t, int32_t, false >
static constexpr bool	kHasNegativeReverseArcs

static const int32_t	kNilNode

static const int32_t	kNilArc

Protected Member Functions inherited from util::BaseGraph< int32_t, int32_t, false >
void	ComputeCumulativeSum (std::vector< int32_t > *v)
	Functions commented when defined because they are implementation details.

void	BuildStartAndForwardHead (SVector< int32_t > head, std::vector< int32_t > start, std::vector< int32_t > *permutation)

Protected Attributes inherited from util::BaseGraph< int32_t, int32_t, false >
int32_t	num_nodes_

int32_t	node_capacity_

int32_t	num_arcs_

int32_t	arc_capacity_

bool	const_capacities_

Detailed Description

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
class util::FlowGraph< NodeIndexType, ArcIndexType >

Graph specialized for max-flow/min-cost-flow algorithms. It follows the ortools/graph/graph.h interface.

For max-flow or min-cost-flow we need a directed graph where each arc from tail to head has a "reverse" arc from head to tail. In practice many input graphs already have such reverse arc and it can make a big difference just to reuse them.

This is similar to ReverseArcStaticGraph but handle reverse arcs in a different way. Instead of always creating a NEW reverse arc for each arc of the input graph, this will detect if a reverse arc was already present in the input, and do not create a new one when this is the case. In the best case, this can gain a factor 2 in the final graph size, note however that the graph construction is slighlty slower because of this detection.

A side effect of reusing reverse arc is also that we cannot anymore clearly separate the original arcs from the newly created one. So the algorithm needs to be able to handle that.

Todo: (user): Currently only max-flow handles this graph, but not min-cost-flow.

Definition at line 52 of file flow_graph.h.

Constructor & Destructor Documentation

◆ FlowGraph() [1/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

util::FlowGraph< NodeIndexType, ArcIndexType >::FlowGraph ( )

default

◆ FlowGraph() [2/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

util::FlowGraph< NodeIndexType, ArcIndexType >::FlowGraph	(	NodeIndexType	num_nodes,
		ArcIndexType	arc_capacity )

inline

Definition at line 65 of file flow_graph.h.

Member Function Documentation

◆ AddArc()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

ArcIndexType util::FlowGraph< NodeIndexType, ArcIndexType >::AddArc	(	NodeIndexType	tail,
		NodeIndexType	head )

inline

Definition at line 141 of file flow_graph.h.

◆ AddNode()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

void util::FlowGraph< NodeIndexType, ArcIndexType >::AddNode ( NodeIndexType node )

inline

Definition at line 137 of file flow_graph.h.

◆ Build() [1/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

void util::FlowGraph< NodeIndexType, ArcIndexType >::Build ( )

inline

Definition at line 148 of file flow_graph.h.

◆ Build() [2/2]

template<typename NodeIndexType, typename ArcIndexType>

void util::FlowGraph< NodeIndexType, ArcIndexType >::Build ( std::vector< ArcIndexType > * permutation )

Step 1 we only keep a "canonical version" of each arc where tail <= head. This will allow us to detect reverse as duplicates instead.

Step 2, compute the perm to sort by tail then head. This is something we do a few times here, we compute the permutation with a kind of radix sort by computing the degree of each node.

Identify arc pairs that are reverse of each other and fill reverse for them. The others position will stay at -1.

Find the next candidate without reverse if there is a gap.

Create the extra reversed arcs needed.

Fix the initial swap.

Just create a reverse for each arc.

It seems better to put all the reverse first instead of last in the adjacency list, so lets do that here. Note that we need to fix the permutation returned to the user in this case.

With this, we should have almost exactly the same behavior as ReverseArcStaticGraph().

Do we sort each OutgoingArcs(node) by head ? Or is it better to keep all new reverse arc before or after ?

Todo: (user): For now we only support sorting, or all new reverse after and keep the original arc order.

Create the final heads_.

No longer needed.

We now create reverse_, this needs the permutation on both sides.

Definition at line 314 of file flow_graph.h.

◆ Head()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

NodeIndexType util::FlowGraph< NodeIndexType, ArcIndexType >::Head ( ArcIndexType arc ) const

inline

Definition at line 71 of file flow_graph.h.

◆ operator[]()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

absl::Span< const NodeIndexType > util::FlowGraph< NodeIndexType, ArcIndexType >::operator[] ( NodeIndexType node ) const

inline

Definition at line 124 of file flow_graph.h.

◆ OppositeArc()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

ArcIndexType util::FlowGraph< NodeIndexType, ArcIndexType >::OppositeArc ( ArcIndexType arc ) const

inline

Each arc has a reverse. If not added by the client, we have created one, see Build().

Definition at line 92 of file flow_graph.h.

◆ OutgoingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

util::IntegerRange< ArcIndexType > util::FlowGraph< NodeIndexType, ArcIndexType >::OutgoingArcs ( NodeIndexType node ) const

inline

Iteration.

Definition at line 100 of file flow_graph.h.

◆ OutgoingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

util::IntegerRange< ArcIndexType > util::FlowGraph< NodeIndexType, ArcIndexType >::OutgoingArcsStartingFrom	(	NodeIndexType	node,
		ArcIndexType	from ) const

inline

Definition at line 103 of file flow_graph.h.

◆ OutgoingOrOppositeIncomingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

util::IntegerRange< ArcIndexType > util::FlowGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcs ( NodeIndexType node ) const

inline

These are needed to use with the current max-flow implementation. We don't distinguish direct from reverse arc anymore, and this is just the same as OutgoingArcs()/OutgoingArcsStartingFrom().

Definition at line 115 of file flow_graph.h.

◆ OutgoingOrOppositeIncomingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

util::IntegerRange< ArcIndexType > util::FlowGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcsStartingFrom	(	NodeIndexType	node,
		ArcIndexType	from ) const

inline

Definition at line 119 of file flow_graph.h.

◆ ReserveArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

void util::FlowGraph< NodeIndexType, ArcIndexType >::ReserveArcs ( ArcIndexType bound )

inlineoverride

Definition at line 131 of file flow_graph.h.

◆ SetDetectReverse()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

void util::FlowGraph< NodeIndexType, ArcIndexType >::SetDetectReverse ( bool value )

inline

This influence what Build() does. If true, we will detect already existing pairs of (arc, reverse_arc) and only construct new reverse arc for the one that we couldn't match. Otherwise, we will construct a new reverse arc for each input arcs.

Definition at line 155 of file flow_graph.h.

◆ SetSortByHead()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

void util::FlowGraph< NodeIndexType, ArcIndexType >::SetSortByHead ( bool value )

inline

This influence what Build() does. If true, the order of each outgoing arc will be sorted by their head. Otherwise, it will be in the original order with the newly created reverse arc afterwards.

Definition at line 160 of file flow_graph.h.

◆ Tail()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

NodeIndexType util::FlowGraph< NodeIndexType, ArcIndexType >::Tail ( ArcIndexType arc ) const

inline

Note: we could trade memory for speed if this happens to be hot. However, it is expected that most user will access arcs via for (const int arc : graph.OutgoingArcs(tail)) {} in which case all arcs already have a known tail.

Definition at line 78 of file flow_graph.h.

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

ortools/graph/flow_graph.h

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ FlowGraph() [1/2]

◆ FlowGraph() [2/2]

Member Function Documentation

◆ AddArc()

◆ AddNode()

◆ Build() [1/2]

◆ Build() [2/2]

◆ Head()

◆ operator[]()

◆ OppositeArc()

◆ OutgoingArcs()

◆ OutgoingArcsStartingFrom()

◆ OutgoingOrOppositeIncomingArcs()

◆ OutgoingOrOppositeIncomingArcsStartingFrom()

◆ ReserveArcs()

◆ SetDetectReverse()

◆ SetSortByHead()

◆ Tail()