operations_research::SubDagComputer Class Reference

#include <constraint_solveri.h>

Public Member Functions
	DEFINE_STRONG_INT_TYPE (ArcId, int)
	DEFINE_STRONG_INT_TYPE (NodeId, int)
	SubDagComputer ()=default
ArcId	AddArc (NodeId tail, NodeId head)
void	BuildGraph (int num_nodes)
const std::vector< ArcId > &	ComputeSortedSubDagArcs (NodeId node)

Detailed Description

After building a Directed Acyclic Graph, allows to generate sub-DAGs reachable from a node. Workflow:

• Call AddArc() repeatedly to add arcs describing a DAG. Nodes are allocated on the user side, they must be nonnegative, and it is better but not mandatory for the set of nodes to be dense.
• Call BuildGraph(). This precomputes all the information needed to make subsequent requests for sub-DAGs.
• Call ComputeSortedSubDagArcs(node). This returns a view to arcs reachable from node, in topological order. All arcs must be added before calling BuildGraph(), and ComputeSortedSubDagArcs() can only be called after BuildGraph(). If the arcs form a graph that has directed cycles,
• in debug mode, BuildGraph() will crash.
• otherwise, BuildGraph() will not crash, but ComputeSortedSubDagArcs() will only return a subset of arcs reachable by the given node.

Definition at line 2737 of file constraint_solveri.h.

Constructor & Destructor Documentation

SubDagComputer()

operations_research::SubDagComputer::SubDagComputer ( )

default

Member Function Documentation

AddArc()

ArcId operations_research::SubDagComputer::AddArc ( NodeId tail, NodeId head )

inline

Adds an arc between node 'tail' and node 'head'. Nodes must be nonnegative. Returns the index of the new arc, those are used to identify arcs when calling ComputeSortedSubDagArcs().

Definition at line 2745 of file constraint_solveri.h.

BuildGraph()

void operations_research::SubDagComputer::BuildGraph

(

int

num_nodes

)

Finishes the construction of the DAG. 'num_nodes' is the number of nodes in the DAG and must be greater than all node indices passed to AddArc().

Definition at line 2887 of file local_search.cc.

ComputeSortedSubDagArcs()

const std::vector< SubDagComputer::ArcId > & operations_research::SubDagComputer::ComputeSortedSubDagArcs

(

NodeId

node

)

Computes the arcs of the sub-DAG reachable from node returns a view of those arcs in topological order.

Compute indegrees of nodes of the sub-DAG reachable from node.

Generate arc ordering by iteratively removing zero-indegree nodes.

Invariant: indegree_of_node_ must be all 0, or the graph has a cycle.

Definition at line 2945 of file local_search.cc.

DEFINE_STRONG_INT_TYPE() [1/2]

operations_research::SubDagComputer::DEFINE_STRONG_INT_TYPE	(	ArcId	,
		int	)

DEFINE_STRONG_INT_TYPE() [2/2]

operations_research::SubDagComputer::DEFINE_STRONG_INT_TYPE	(	NodeId	,
		int	)

---

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

• ortools/constraint_solver/constraint_solveri.h
• ortools/constraint_solver/local_search.cc