5.7. ordered_graph.hpp

Full path: graph_canon/ordered_graph.hpp

template<typename GraphT, typename IndexMapT, bool WithInEdges = false>
class ordered_graph

A graph adaptor that ensures iteration order in correspondence with a given vertex index map.

Requires Graph to model a VertexListGraph and an IncidenceGraph, and IndexMap a ReadableProperyMap. The ordered graph models those concepts as well as AdjacencyGraph. If WithInEdges is true, and Graph models a BidirectionalGraph, then the ordered graph will model the BidirectionalGraph concept as well.

When iterating through the range of vertices, adjacency vertices, and inverse-adjacent vertices, the vertices will appear in sorted order with respect to the given index map. When iterating through out-edges and in-edges, the edges will appear in sorted order with respect to the index of the neighbouring vertices. If the adapted graph has parallel edges, those will be ordered according to a predicate given to the constructor.

using Graph = GraphT

The type of the underlying graph.

using IndexMap = IndexMapT

The type of the vertex index map representing the order to use for iteration.

template<typename EdgeLess>
ordered_graph(const Graph &g, IndexMap idx, EdgeLess edge_less)

Construct an ordered graph from a graph and a given index map (the graph is stored by reference). The binary edge predicate edge_less is used when the graph has parallel edges (hint: give always_false() for simple graphs).

const Graph &get_graph() const

Returns

a reference to the adapted graph.

IndexMap get_index_map() const

Returns

a copy of the stored index map.

template<bool WithInEdges, typename Graph, typename IndexMap, typename EdgeLess>
ordered_graph<Graph, IndexMap, WithInEdges> make_ordered_graph(const Graph &g, IndexMap idx, EdgeLess edge_less)

Returns

ordered_graph<Graph, IndexMap, WithInEdges>(g, idx, edge_less)