|
|
| Graph () |
| | Create an empty Graph with 0 nodes.
|
| |
|
| Graph (Int n) |
| | Create a Graph with n isolated nodes (without edges).
|
| |
|
Graph & | operator= (const Graph &G2) |
| | assignment from Graph of the same type
|
| |
|
Graph & | operator= (const GenericGraph< Graph > &G2) |
| | assignment from GenericGraph
|
| |
|
template<typename Graph2 , typename TDir2 > |
| Graph & | operator= (const GenericGraph< Graph2, TDir2 > &G2) |
| | assignment from GenericGraph with other flavor of directedness
|
| |
|
Int | nodes () const |
| | number of nodes
|
| |
|
void | resize (Int n) |
| | resize the Graph to given number of nodes
|
| |
|
void | clear (Int n=0) |
| | clear all edges and resize (to zero nodes by default)
|
| |
|
bool | has_gaps () const |
| | true of nodes are not (known to be) consecutively ordered
|
| |
|
Int | dim () const |
| | "output dimension"; relevant for proper output in the polymake shell
|
| |
|
void | swap (Graph &G) |
| | swap function
|
| |
|
void | squeeze () |
| | force renumbering of the nodes in consecutive order
|
| |
|
void | delete_node (Int n) |
| | delete a node
|
| |
|
template<typename TPerm > |
| std::enable_if_t< isomorphic_to_container_of< TPerm, Int >::value > | permute_nodes (const TPerm &perm) |
| | permute the nodes
|
| |
|
template<typename TInvPerm > |
| std::enable_if_t< isomorphic_to_container_of< TInvPerm, Int >::value > | permute_inv_nodes (const TInvPerm &inv_perm) |
| | inverse permutation of nodes
|
| |
|
template<typename TPerm , typename TInvPerm > |
| std::enable_if_t< isomorphic_to_container_of< TPerm, Int >::value &&isomorphic_to_container_of< TInvPerm, Int >::value, Graph > | copy_permuted (const TPerm &perm, const TInvPerm &inv_perm) const |
| | permuted copy
|
| |
|
Int | edges () const |
| | number of edges
|
| |
|
Int | add_node () |
| | add a node; may reuse a currently unused node
|
| |
|
bool | invalid_node (Int n) const |
| | true if node is unused
|
| |
|
bool | node_out_of_range (Int n) const |
| | true if node number is higher than currently reserved maximum number of nodes
|
| |
|
Int | out_degree (Int n) const |
| | out-degree of a node
|
| |
|
Int | in_degree (Int n) const |
| | in-degree of a node
|
| |
|
Int | degree (Int n) const |
| | total degree of a node
|
| |
|
bool | node_exists (Int n) const |
| | true if node exists
|
| |
| Int | edge (Int n1, Int n2) |
| |
| Int | edge (Int n1, Int n2) const |
| |
| Int | add_edge (Int n1, Int n2) |
| |
|
bool | edge_exists (Int n1, Int n2) const |
| | Check whether there is an edge between the two given nodes.
|
| |
|
parallel_edge_iterator | all_edges (Int n1, Int n2) |
| | Return the iterator over all edges connecting two given nodes.
|
| |
|
parallel_edge_const_iterator | all_edges (Int n1, Int n2) const |
| | Return the iterator over all edges connecting two given nodes.
|
| |
|
void | delete_edge (Int n1, Int n2) |
| | Delete the edge (if it exists) connecting the two given nodes.
|
| |
|
void | delete_edge (const parallel_edge_iterator &where) |
| | Delete an edge pointed by the given iterator over a sequence of (parallel) edges.
|
| |
|
void | delete_all_edges (Int n1, Int n2) |
| | Delete all (parallel) edges connecting the two given nodes.
|
| |
| void | contract_edge (Int n1, Int n2) |
| |
|
out_edge_list_ref | out_edges (Int n) |
| | reference to list of outgoing edges
|
| |
|
const_out_edge_list_ref | out_edges (Int n) const |
| | constant reference to list of outgoing edges
|
| |
|
in_edge_list_ref | in_edges (Int n) |
| | reference to list of incoming edges
|
| |
|
const_in_edge_list_ref | in_edges (Int n) const |
| | constant reference to list of incoming edges
|
| |
|
out_adjacent_node_list_ref | out_adjacent_nodes (Int n) |
| | reference to list of nodes which are adjacent via out-arcs
|
| |
|
const_out_adjacent_node_list_ref | out_adjacent_nodes (Int n) const |
| | constant reference to list of nodes which are adjacent via out-arcs
|
| |
|
in_adjacent_node_list_ref | in_adjacent_nodes (Int n) |
| | reference to list of nodes which are adjacent via in-arcs
|
| |
|
const_in_adjacent_node_list_ref | in_adjacent_nodes (Int n) const |
| | constant reference to list of nodes which are adjacent via in-arcs
|
| |
|
adjacent_node_list_ref | adjacent_nodes (Int n) |
| | reference to list of all adjacent nodes
|
| |
|
const_adjacent_node_list_ref | adjacent_nodes (Int n) const |
| | constant reference to list of all adjacent nodes
|
| |
| void | enumerate_edges () const |
| |
Directed or undirected finite graphs.
NodeAttr and EdgeAttr specify the type of additional data associated with nodes and edges (sometimes also called node and edge attributes.) The default setting nothing denotes the absence of any attributes, it doesn't waste extra memory.
The nodes of the graph are referred to via integer indices, starting with 0; they are stored in a contiguous array. This allows constant-time random node access, while inserting or deleting of nodes incurs storage reallocation. However, due to some kind of forecasting strategy of memory allocation (similar to that deployed in std::vector), the amortized cost of node insertion is proportional to nodes log(nodes).
The edges are organized in incidence lists, which are implemented as a 2-d mesh of AVL trees. Hence, a random access to an edge (with given source and target nodes) takes a logarithmical time of the source node degree. Multiple edges (i.e., with the same source and target nodes) are not allowed; they could be modeled, however, by choosing some container class as the edge attribute.
The kind of the graph decides about how the incidence edge lists are organized. In the directed case each edge naturally appears in the outgoing list of its source node and in the ingoing list of its target node. In the undirected case the notions of outgoing and ingoing edges are the same; each edge manages to appear in the outgoing lists of both adjacent nodes, although it is stored only once. The @i skew case is a special variant of the indirect case, intended for numerical edge attributes only. Depending on the reading direction, the edge attribute changes its sign:
The whole data structure is attached to the Graph object via a smart pointer with reference counting.
1.8.17