![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
#include <graph.h>
Public Types | |
typedef NodeIndexType | NodeIndex |
typedef ArcIndexType | ArcIndex |
Public Member Functions | |
BaseGraph () | |
BaseGraph (const BaseGraph &)=default | |
BaseGraph & | operator= (const BaseGraph &)=default |
virtual | ~BaseGraph ()=default |
NodeIndexType | num_nodes () const |
NodeIndexType | size () const |
ArcIndexType | num_arcs () const |
Returns the number of valid arcs in the graph. | |
IntegerRange< NodeIndex > | AllNodes () const |
BaseGraph implementation -------------------------------------------------—. | |
IntegerRange< ArcIndex > | AllForwardArcs () const |
bool | IsNodeValid (NodeIndexType node) const |
Returns true if the given node is a valid node of the graph. | |
bool | IsArcValid (ArcIndexType arc) const |
NodeIndexType | node_capacity () const |
Capacity reserved for future nodes, always >= num_nodes_. | |
ArcIndexType | arc_capacity () const |
Capacity reserved for future arcs, always >= num_arcs_. | |
virtual void | ReserveNodes (NodeIndexType bound) |
virtual void | ReserveArcs (ArcIndexType bound) |
void | Reserve (NodeIndexType node_capacity, ArcIndexType arc_capacity) |
void | FreezeCapacities () |
Static Public Attributes | |
static constexpr bool | kHasNegativeReverseArcs = HasNegativeReverseArcs |
static constexpr NodeIndexType | kNilNode |
static constexpr ArcIndexType | kNilArc |
Protected Member Functions | |
void | ComputeCumulativeSum (internal::Vector< NodeIndexType, ArcIndexType > *v) |
Functions commented when defined because they are implementation details. | |
void | BuildStartAndForwardHead (internal::SVector< ArcIndexType, NodeIndexType > *head, internal::Vector< NodeIndexType, ArcIndexType > *start, std::vector< ArcIndexType > *permutation) |
Protected Attributes | |
NodeIndexType | num_nodes_ |
NodeIndexType | node_capacity_ |
ArcIndexType | num_arcs_ |
ArcIndexType | arc_capacity_ |
bool | const_capacities_ |
Base class of all Graphs implemented here. The default value for the graph index types is int32_t since almost all graphs that fit into memory do not need bigger indices.
NodeIndexType and ArcIndexType can be any integer type, but can also be strong integer types (e.g. StrongInt). Strong integer types are types that behave like integers (comparison, arithmetic, etc.), and are (explicitly) constructible/convertible from/to integers.
typedef ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ArcIndex |
typedef NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::NodeIndex |
Typedef so you can use Graph::NodeIndex and Graph::ArcIndex to be generic but also to improve the readability of your code. We also recommend that you define a typedef ... Graph; for readability.
|
inline |
|
default |
|
virtualdefault |
IntegerRange< ArcIndexType > util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::AllForwardArcs | ( | ) | const |
IntegerRange< NodeIndexType > util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::AllNodes | ( | ) | const |
ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::arc_capacity | ( | ) | const |
Capacity reserved for future arcs, always >= num_arcs_.
|
protected |
Given the tail of arc #i in (*head)[i] and the head of arc #i in (*head)[~i]
Computes the outgoing degree of each nodes and check if we need to permute something or not. Note that the tails are currently stored in the positive range of the SVector head.
Abort early if we do not need the permutation: we only need to put the heads in the positive range.
Computes the forward arc permutation.
Restore in (*start)[i] the index of the first arc with tail >= i.
Permutes the head into their final position in head. We do not need the tails anymore at this point.
|
protected |
void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::FreezeCapacities | ( | ) |
FreezeCapacities() makes any future attempt to change the graph capacities crash in DEBUG mode.
|
inline |
|
inline |
NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::node_capacity | ( | ) | const |
|
inline |
|
inline |
Returns the number of valid nodes in the graph. Prefer using num_nodes(): the size() API is here to make Graph and vector<vector<int>> more alike.
|
default |
|
inline |
|
inlinevirtual |
Reimplemented in util::ReverseArcStaticGraph< NodeIndex, ArcIndex >.
|
inlinevirtual |
Changes the graph capacities. The functions will fail in debug mode if:
|
inline |
|
protected |
|
protected |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
protected |
|
protected |
|
protected |