Containers

Graph structures

Static digraph

static_digraph is a type of graph, whose vertices and arcs are consecutive integers starting from 0, that cannot be modified but allows all common lookup operations with better performances:

• iterate over vertices
• iterate over arcs
• find the source and sink of a given arc
• iterate over outgoing arcs of a given vertex
• iterate over incoming arcs of a given vertex

Construct a static_digraph:

// initialize a static_digraph builder for 8 vertices (0 to 7)
static_digraph_builder<static_digraph> builder(8);

// add the arcs
builder.add_arc(3, 4);
builder.add_arc(1, 7);
builder.add_arc(5, 2);
...
auto [graph] = builder.build();
// graph is a static_digraph

Constructing a static_digraph with data attached to the arcs:

// initialize a static_digraph builder for 8 vertices (0 to 7)
static_digraph_builder<static_digraph, double> builder(8);

// add the arcs
builder.add_arc(3, 4, 11.46);
builder.add_arc(1, 7, 6.0);
builder.add_arc(5, 2, 8.75);
...
// build the graph
auto [graph, length_map] = builder.build();
// graph is a static digraph
// length_map is a std::vector<double>
static_assert(output_mapping_of<decltype(length_map), arc_t<static_digraph>, double>);

Mutable digraph

mutable_digraph is a type of graph, whose vertices and arcs are integers greater than 0, that allows all common lookup and update operations:

• iterate over vertices
• iterate over arcs
• find the source and sink of a given arc
• iterate over outgoing arcs of a given vertex
• iterate over incoming arcs of a given vertex
• create and remove vertices
• create and remove arcs
• change the source or target of a given arc

Removing vertices or arcs does not change the integers values corresponding to the remaining vertices or arcs. Thus, the integers associated to vertices or arcs are not guaranteed to be consecutive.

Construct a mutable_digraph:

mutable_digraph graph;
auto a = create_vertex(graph);
auto b = create_vertex(graph);
auto c = create_vertex(graph);
...
auto ab = create_arc(graph, a, b);
auto ac = create_arc(graph, a, c);
auto cb = create_arc(graph, c, b);
...

Data structures

D-ary heap

template <typename Q>
concept priority_queue = std::semiregular<Q> &&
    requires(Q q, typename Q::value_type v) {
    q.push(v);
    { q.top() } -> std::same_as<typename Q::value_type>;
    q.pop();
    { q.size() } -> std::same_as<typename Q::size_type>;
    { q.empty() } -> std::convertible_to<bool>;
    q.clear();
};

template <typename Q>
concept updatable_priority_queue = priority_queue<Q> &&
    requires(Q q, typename Q::id_type i, typename Q::priority_type p) {
    { q.contains(i) } -> std::convertible_to<bool>;
    { q.priority(i) } -> std::same_as<typename Q::priority_type>;
    q.promote(i, p);
    q.demote(i, p);
};

d_ary_heap<D, _Entry, _PriorityComparator, _EntryPriorityMap>

• D: The degree of the heap, i.e., the number of children per node.
• _Entry: The type of elements stored in the heap.
• _PriorityComparator: A comparison function type (default: std::greater<_Entry>)
• _EntryPriorityMap: A mapping associating an entry to its priority (default: views::identity_map)

updatable_d_ary_heap<D, _Entry, _PriorityComparator, _IndicesMap, _EntryPriorityMap, _EntryIdMap>

• D: The degree of the heap, i.e., the number of children per node.
• _Entry: The type of elements stored in the heap.
• _PriorityComparator: A comparison function type (default: std::greater<_Entry>)
• _IndicesMap : A mapping associating each entry’s unique identifier to its index in the heap (default: std::unordered_map<_Entry, std::size_t>)
• _EntryPriorityMap: A mapping associating each entry to its priority (default: views::identity_map)
• _EntryIdMap : A mapping associating each entry to an unique identifier (default: views::identity_map)