template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasReverseArcs = false>
class util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >
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.
- Note
- The type can be unsigned, except for the graphs with reverse arcs where the ArcIndexType must be signed, but not necessarily the NodeIndexType.
Definition at line 190 of file graph.h.
template<typename NodeIndexType , typename ArcIndexType , bool HasReverseArcs>
BaseGraph implementation -------------------------------------------------—.
Allows nice range-based for loop: for (const NodeIndex node : graph.AllNodes()) { ... } for (const ArcIndex arc : graph.AllForwardArcs()) { ... }
Definition at line 969 of file graph.h.
template<typename NodeIndexType , typename ArcIndexType , bool HasReverseArcs>
| void util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >::BuildStartAndForwardHead |
( |
SVector< NodeIndexType > * | head, |
|
|
std::vector< ArcIndexType > * | start, |
|
|
std::vector< ArcIndexType > * | permutation ) |
|
protected |
Given the tail of arc #i in (*head)[i] and the head of arc #i in (*head)[~i]
- Reorder the arc by increasing tail.
- Put the head of the new arc #i in (*head)[i].
- Put in start[i] the index of the first arc with tail >= i.
- Update "permutation" to reflect the change, unless it is NULL.
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.
- Note
- this temporarily alters the start vector.
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.
Definition at line 1034 of file graph.h.
template<typename NodeIndexType , typename ArcIndexType , bool HasReverseArcs>
| void util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >::ComputeCumulativeSum |
( |
std::vector< ArcIndexType > * | v | ) |
|
|
protected |
Functions commented when defined because they are implementation details.
Computes the cumulative sum of the entry in v. We only use it with in/out degree distribution, hence the Check() at the end.
Definition at line 1017 of file graph.h.
1.12.0