template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
class util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >
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 194 of file graph.h.
template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
BaseGraph implementation -------------------------------------------------—.
Allows nice range-based for loop: for (const NodeIndex node : graph.AllNodes()) { ... } for (const ArcIndex arc : graph.AllForwardArcs()) { ... }
Definition at line 968 of file graph.h.
template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
| void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::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 1042 of file graph.h.
template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
| void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::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 1024 of file graph.h.
template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
| virtual void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ReserveNodes |
( |
NodeIndexType | bound | ) |
|
|
inlinevirtual |
Changes the graph capacities. The functions will fail in debug mode if:
- const_capacities_ is true.
- A valid node does not fall into the new node range.
- A valid arc does not fall into the new arc range. In non-debug mode, const_capacities_ is ignored and nothing will happen if the new capacity value for the arcs or the nodes is too small.
Reimplemented in util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator, util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator, util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::IncomingArcIterator, util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcIterator, util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator, util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator, util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcIterator, and util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator.
Definition at line 251 of file graph.h.
1.13.2