-
Notifications
You must be signed in to change notification settings - Fork 2
Containers
François Hamonic edited this page Dec 20, 2023
·
4 revisions
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
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);
...