|
template<typename... arguments> |
node_indext | add_node (arguments &&... values) |
|
void | swap (grapht &other) |
|
bool | has_edge (node_indext i, node_indext j) const |
|
const nodet & | operator[] (node_indext n) const |
|
nodet & | operator[] (node_indext n) |
|
void | resize (node_indext s) |
|
std::size_t | size () const |
|
bool | empty () const |
|
const edgest & | in (node_indext n) const |
|
const edgest & | out (node_indext n) const |
|
void | add_edge (node_indext a, node_indext b) |
|
void | remove_edge (node_indext a, node_indext b) |
|
edget & | edge (node_indext a, node_indext b) |
|
void | add_undirected_edge (node_indext a, node_indext b) |
|
void | remove_undirected_edge (node_indext a, node_indext b) |
|
void | remove_in_edges (node_indext n) |
|
void | remove_out_edges (node_indext n) |
|
void | remove_edges (node_indext n) |
|
void | clear () |
|
void | shortest_path (node_indext src, node_indext dest, patht &path) const |
|
void | shortest_loop (node_indext node, patht &path) const |
|
void | visit_reachable (node_indext src) |
|
std::vector< node_indext > | get_reachable (node_indext src, bool forwards) const |
| Run depth-first search on the graph, starting from a single source node. More...
|
|
std::vector< node_indext > | get_reachable (const std::vector< node_indext > &src, bool forwards) const |
| Run depth-first search on the graph, starting from multiple source nodes. More...
|
|
void | disconnect_unreachable (node_indext src) |
| Removes any edges between nodes in a graph that are unreachable from a given start node. More...
|
|
void | disconnect_unreachable (const std::vector< node_indext > &src) |
| Removes any edges between nodes in a graph that are unreachable from a vector of start nodes. More...
|
|
std::vector< typename N::node_indext > | depth_limited_search (typename N::node_indext src, std::size_t limit) const |
| Run recursive depth-limited search on the graph, starting from multiple source nodes, to find the nodes reachable within n steps. More...
|
|
std::vector< typename N::node_indext > | depth_limited_search (std::vector< typename N::node_indext > &src, std::size_t limit) const |
| Run recursive depth-limited search on the graph, starting from multiple source nodes, to find the nodes reachable within n steps. More...
|
|
void | make_chordal () |
| Ensure a graph is chordal (contains no 4+-cycles without an edge crossing the cycle) by adding extra edges. More...
|
|
std::size_t | connected_subgraphs (std::vector< node_indext > &subgraph_nr) |
| Find connected subgraphs in an undirected graph. More...
|
|
std::size_t | SCCs (std::vector< node_indext > &subgraph_nr) const |
| Computes strongly-connected components of a graph and yields a vector expressing a mapping from nodes to components indices. More...
|
|
bool | is_dag () const |
|
std::list< node_indext > | topsort () const |
| Find a topological order of the nodes if graph is DAG, return empty list for non-DAG or empty graph. More...
|
|
std::vector< node_indext > | get_predecessors (const node_indext &n) const |
|
std::vector< node_indext > | get_successors (const node_indext &n) const |
|
void | output_dot (std::ostream &out) const |
|
void | for_each_predecessor (const node_indext &n, std::function< void(const node_indext &)> f) const |
|
void | for_each_successor (const node_indext &n, std::function< void(const node_indext &)> f) const |
|
template<class N = graph_nodet<empty_edget>>
class grapht< N >
A generic directed graph with a parametric node type.
The nodes of the graph are stored in the only field of the class, a std::vector named nodes
. Nodes are instances of class graph_nodet<E> or a subclass of it. Graph edges contain a payload object of parametric type E (which has to be default-constructible). By default E is instantiated with an empty class (empty_edget).
Each node is identified by its offset inside the nodes
vector. The incoming and outgoing edges of a node are stored as std::maps in the fields in
and out
of the graph_nodet<E>. These maps associate a node identifier (the offset) to the edge payload (of type E).
In fact, observe that two instances of E are stored per edge of the graph. For instance, assume that we want to create a graph with two nodes, A and B, and one edge from A to B, labelled by object e. We achieve this by inserting the pair (offsetof(B),e) in the map A.out
and the pair (offsetof(A),e) in the map B.in
.
Nodes are inserted in the graph using grapht::add_node(), which returns the identifier (offset) of the inserted node. Edges between nodes are created by grapht::add_edge(a,b), where a
and b
are the identifiers of nodes. Method add_edges
adds a default-constructed payload object of type E. Adding a payload objet e
to an edge seems to be only possibly by manually inserting e
in the std::maps in
and out
of the two nodes associated to the edge.
Definition at line 166 of file graph.h.
Computes strongly-connected components of a graph and yields a vector expressing a mapping from nodes to components indices.
For example, if nodes 1 and 3 are in SCC 0, and nodes 0, 2 and 4 are in SCC 1, this will leave subgraph_nr
holding { 1, 0, 1, 0, 1 }
, and the function will return 2 (the number of distinct SCCs). Lower-numbered SCCs are closer to the leaves, so in the particular case of a DAG, sorting by SCC number gives a topological sort, and for a cyclic graph the SCCs are topologically sorted but arbitrarily ordered internally.
- Parameters
-
[in,out] | subgraph_nr | should be pre-allocated with enough storage for one entry per graph node. Will be populated with the SCC indices of each node. |
- Returns
- the number of distinct SCCs.
Definition at line 832 of file graph.h.