C++ Reference: class ListGraph

This documentation is automatically generated.

Method
AddArc

Return type: ArcIndexType

Arguments: 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. Note: Self referencing arcs and duplicate arcs are supported.

AddNode

Return type: void

Arguments: NodeIndexType node

If node is not a valid node, sets num_nodes_ to node + 1 so that the given node becomes valid. It will fail in DEBUG mode if the capacities are fixed and the new node is out of range.

Build

Return type: void

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(). Note that some implementations become immutable after calling Build().

Build

Return type: void

Arguments: std::vector<ArcIndexType>* permutation

ListGraph

ListGraph

Arguments: NodeIndexType num_nodes, ArcIndexType arc_capacity

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.

OutDegree

Return type: ArcIndexType

Arguments: NodeIndexType node

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).

OutgoingArcs

Return type: BeginEndWrapper<OutgoingArcIterator>

Arguments: NodeIndexType node

Allows to iterate over the forward arcs that verify Tail(arc) == node. This is meant to be used as: for (const ArcIndex arc : graph.OutgoingArcs(node)) { ... }

OutgoingArcsStartingFrom

Return type: BeginEndWrapper<OutgoingArcIterator>

Arguments: NodeIndexType node, ArcIndexType from

Advanced usage. Same as OutgoingArcs(), but allows to restart the iteration from an already known outgoing arc of the given node.

ReserveArcs

Return type: void

Arguments: ArcIndexType bound

ReserveNodes

Return type: void

Arguments: NodeIndexType bound

Tail

Return type: NodeIndexType

Arguments: ArcIndexType arc

Returns the tail/head of a valid arc.