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.
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.
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().
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.
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).
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)) { ... }
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["`ListGraph` is a C++ class representing a graph data structure using lists to store node and arc information."],["It provides methods to add nodes and arcs, with automatic node creation when adding arcs."],["The `Build` method might be required for some implementations before graph usage and can reorder arc indices."],["`ListGraph` allows iteration over outgoing arcs of a node and retrieval of node degrees."],["Space for the graph can be reserved during construction using `num_nodes` and `arc_capacity`."]]],["The `ListGraph` class in C++ allows for graph manipulation. Key actions include `AddArc` to add an arc between nodes, automatically creating nodes if needed. `AddNode` adds a node, expanding the graph if the node is new. `Build` finalizes the graph structure, potentially re-indexing arcs. Methods like `OutDegree`, `OutgoingArcs`, and `Head`/`Tail` provide information about a node's connections. Constructors, `ReserveArcs` and `ReserveNodes` allow setting capacity of the graph.\n"]]