C++ Reference: graph

Note: This documentation is automatically generated.

This file defines a generic graph interface on which most algorithms can be built and provides a few efficient implementations with a fast construction time. Its design is based on the experience acquired by the Operations Research team in their various graph algorithm implementations.

The main ideas are:
   - Graph nodes and arcs are represented by integers.
   - Node or arc annotations (weight, cost, ...) are not part of the graph
   class, they can be stored outside in one or more arrays and can be easily
   retrieved using a node or arc as an index.

Terminology:


   - An arc of a graph is directed and going from a tail node to a head node.
   - Some implementations also store 'reverse' arcs and can be used for
   undirected graph or flow-like algorithm.
   - A node or arc index is 'valid' if it represents a node or arc of
   the graph. The validity ranges are always [0, num_nodes()) for nodes and
   [0, num_arcs()) for forward arcs. Reverse arcs are elements of
   [-num_arcs(), 0) and are also considered valid by the implementations that
   store them.

Provided implementations:


   - ListGraph<> for the simplest api. Also aliased to util::Graph.
   - StaticGraph<> for performance, but require calling Build(), see below
   - CompleteGraph<> if you need a fully connected graph
   - CompleteBipartiteGraph<> if you need a fully connected bipartite graph
   - ReverseArcListGraph<> to add reverse arcs to ListGraph<>
   - ReverseArcStaticGraph<> to add reverse arcs to StaticGraph<>
   - ReverseArcMixedGraph<> for a smaller memory footprint

Utility classes & functions:


   - Permute() to permute an array according to a given permutation.
   - SVector<> vector with index range [-size(), size()) for ReverseArcGraph.

Basic usage:

   typedef ListGraph<> Graph;  // Choose a graph implementation.
   Graph graph;
   for (...) {
     graph.AddArc(tail, head);
   }
   ...
   for (int node = 0; node < graph.num_nodes(); ++node) {
     for (const int arc : graph.OutgoingArcs(node)) {
       head = graph.Head(arc);
       tail = node;  // or graph.Tail(arc) which is fast but not as much.
     }
   }

Iteration over the arcs touching a node:


   - OutgoingArcs(node): All the forward arcs leaving the node.
   - IncomingArcs(node): All the forward arcs arriving at the node.

And two more involved ones:


   - OutgoingOrOppositeIncomingArcs(node): This returns both the forward arcs
   leaving the node (i.e. OutgoingArcs(node)) and the reverse arcs leaving the
   node (i.e. the opposite arcs of the ones returned by IncomingArcs(node)).
   - OppositeIncomingArcs(node): This returns the reverse arcs leaving the node.

Note on iteration efficiency: When re-indexing the arcs it is not possible to

have both the outgoing arcs and the incoming ones form a consecutive range.

It is however possible to do so for the outgoing arcs and the opposite incoming arcs. It is why the OutgoingOrOppositeIncomingArcs() and OutgoingArcs() iterations are more efficient than the IncomingArcs() one.

If you know the graph size in advance, this already set the number of nodes, reserve space for the arcs and check in DEBUG mode that you don't go over the bounds:

   Graph graph(num_nodes, arc_capacity);

Storing and using node annotations: vector<bool> is_visited(graph.num_nodes(), false); ... for (int node = 0; node < graph.num_nodes(); ++node) { if (!is_visited[node]) ... }

Storing and using arc annotations:

   vector weights;
   for (...) {
     graph.AddArc(tail, head);
     weights.push_back(arc_weight);
   }
   ...
   for (const int arc : graph.OutgoingArcs(node)) {
     ... weights[arc] ...;
   }

More efficient version:

   typedef StaticGraph<> Graph;
   Graph graph(num_nodes, arc_capacity);  // Optional, but help memory usage.
   vector weights;
   weights.reserve(arc_capacity);  // Optional, but help memory usage.
   for (...) {
     graph.AddArc(tail, head);
     weights.push_back(arc_weight);
   }
   ...
   vector permutation;
   graph.Build(&permutation);  // A static graph must be Build() before usage.
   Permute(permutation, &weights);  // Build() may permute the arc index.
   ...

Encoding an undirected graph:

 is to add two arcs for each edge (one in each direction) to a directed graph.
 Otherwise you can do the following.
   typedef ReverseArc... Graph;
   Graph graph;
   for (...) {
     graph.AddArc(tail, head);  // or graph.AddArc(head, tail) but not both.
     edge_annotations.push_back(value);
   }
   ...
   for (const Graph::NodeIndex node : graph.AllNodes()) {
     for (const Graph::ArcIndex arc :
          graph.OutgoingOrOppositeIncomingArcs(node)) {
       destination = graph.Head(arc);
       annotation = edge_annotations[arc < 0 ? graph.OppositeArc(arc) : arc];
     }
   }
Note: The graphs are primarily designed to be constructed first and then used because it covers most of the use cases. It is possible to extend the interface with more dynamicity (like removing arcs), but this is not done at this point. Note that a "dynamic" implementation will break some assumptions we make on what node or arc are valid and also on the indices returned by AddArc(). Some arguments for simplifying the interface at the cost of dynamicity are:




   - It is always possible to construct a static graph from a dynamic one

     before calling a complex algo.

   - If you really need a dynamic graph, maybe it is better to compute a graph

     property incrementally rather than calling an algorithm that starts from

     scratch each time.


  

    

      

        

          

            Classes
          
        
      
BaseGraph
CompleteGraph
ListGraph
StaticGraph
SVector