|
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.
|
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.
|
void | disconnect_unreachable (node_indext src) |
| Removes any edges between nodes in a graph that are unreachable from a given start node.
|
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.
|
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.
|
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.
|
void | make_chordal () |
| Ensure a graph is chordal (contains no 4+-cycles without an edge crossing the cycle) by adding extra edges.
|
std::size_t | connected_subgraphs (std::vector< node_indext > &subgraph_nr) |
| Find connected subgraphs in an undirected graph.
|
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.
|
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.
|
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.