 |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
#include <graph.h>
Classes | |
| struct | OutgoingArcIteratorTag |
| Do not use directly. More... | |
Public Types | |
| using | OutgoingArcIterator |
| using | OutgoingHeadIterator = ArcHeadIterator<ListGraph, OutgoingArcIterator> |
| Public Types inherited from util::BaseGraph< int32_t, int32_t, false > | |
| typedef int32_t | NodeIndex |
| typedef int32_t | ArcIndex |
Public Member Functions | |
| ListGraph () | |
| ListGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity) | |
| void | AddNode (NodeIndexType node) |
| ArcIndexType | AddArc (NodeIndexType tail, NodeIndexType head) |
| void | Build () |
| void | Build (std::vector< ArcIndexType > *permutation) |
| NodeIndexType | Tail (ArcIndexType arc) const |
| Returns the tail/head of a valid arc. | |
| NodeIndexType | Head (ArcIndexType arc) const |
| ArcIndexType | OutDegree (NodeIndexType node) const |
| BeginEndWrapper< OutgoingArcIterator > | OutgoingArcs (NodeIndexType node) const |
| BeginEndWrapper< OutgoingArcIterator > | OutgoingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const |
| BeginEndWrapper< OutgoingHeadIterator > | operator[] (NodeIndexType node) const |
| void | ReserveNodes (NodeIndexType bound) override |
| void | ReserveArcs (ArcIndexType bound) override |
| bool | IsArcValid (ArcIndexType arc) const |
| Public Member Functions inherited from util::BaseGraph< int32_t, int32_t, false > | |
| BaseGraph () | |
| 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 | |
| Static Public Attributes inherited from util::BaseGraph< int32_t, int32_t, false > | |
| static constexpr bool | kHasNegativeReverseArcs |
| static constexpr int32_t | kNilNode |
| static constexpr int32_t | kNilArc |
| Protected Member Functions inherited from util::BaseGraph< int32_t, int32_t, false > | |
| void | ComputeCumulativeSum (internal::Vector< int32_t, int32_t > *v) |
| Functions commented when defined because they are implementation details. | |
| void | BuildStartAndForwardHead (internal::SVector< int32_t, int32_t > *head, internal::Vector< int32_t, 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_ |
Basic graph implementation without reverse arc. This class also serves as a documentation for the generic graph interface (minus the part related to reverse arcs).
This implementation uses a linked list and compared to StaticGraph:
All graphs should be -compatible, but we haven't tested that.
| using util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator |
| using util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator = ArcHeadIterator<ListGraph, OutgoingArcIterator> |
|
inline |
|
inline |
Reserve space for the graph at construction and do not allow it to grow beyond that, see FreezeCapacities(). This constructor also makes any nodes in [0, num_nodes) valid.
| ArcIndexType util::ListGraph< NodeIndexType, ArcIndexType >::AddArc | ( | NodeIndexType | tail, |
| NodeIndexType | head ) |
Adds an arc to the graph and returns its current index which will always be num_arcs() - 1. It will also automatically call AddNode(tail) and AddNode(head). It will fail in DEBUG mode if the capacities are fixed and this cause the graph to grow beyond them.
| void util::ListGraph< NodeIndexType, ArcIndexType >::AddNode | ( | NodeIndexType | node | ) |
|
inline |
Some graph implementations need to be finalized with Build() before they can be used. After Build() is called, the arc indices (which had been the return values of previous AddArc() calls) may change: the new index of former arc #i will be stored in permutation[i] if #i is smaller than permutation.size() or will be unchanged otherwise. If you don't care about these, just call the simple no-output version Build().
| void util::ListGraph< NodeIndexType, ArcIndexType >::Build | ( | std::vector< ArcIndexType > * | permutation | ) |
| NodeIndexType util::ListGraph< NodeIndexType, ArcIndexType >::Head | ( | ArcIndexType | arc | ) | const |
|
inline |
|
inline |
| ArcIndexType util::ListGraph< NodeIndexType, ArcIndexType >::OutDegree | ( | NodeIndexType | node | ) | const |
Graph jargon: the "degree" of a node is its number of arcs. The out-degree is the number of outgoing arcs. The in-degree is the number of incoming arcs, and is only available for some graph implementations, below.
ListGraph<>::OutDegree() works in O(degree).
|
inline |
|
inline |
Advanced usage. Same as OutgoingArcs(), but allows to restart the iteration from an already known outgoing arc of the given node. If from is kNilArc, an empty range is returned.
|
override |
|
override |
| NodeIndexType util::ListGraph< NodeIndexType, ArcIndexType >::Tail | ( | ArcIndexType | arc | ) | const |
1.14.0