Public Types | |
|
typedef graph::node_container < _dir > | node_container |
| node type | |
| typedef node_container & | node_container_ref |
| node reference type | |
| typedef const node_container & | const_node_container_ref |
| constant node reference type | |
Public Member Functions | |
| 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 dir2> | |
| Graph & | operator= (const GenericGraph< Graph2, dir2 > &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 Iterator> | |
| void | permute_nodes (Iterator perm) |
| permute the nodes as specified by an iterator | |
| template<typename Iterator> | |
| void | permute_inv_nodes (Iterator perm) |
| inverse permutation of nodes | |
| template<typename Perm, typename InvPerm> | |
| Graph | copy_permuted (const Perm &perm, const InvPerm &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) |
| return the number of the edge between two given nodes; edge is created if it did not exist before | |
| int | edge (int n1, int n2) const |
| return the number of the edge between two given nodes; no edge creation | |
| bool | edge_exists (int n1, int n2) const |
| true if there is an edge between the two given nodes | |
| void | delete_edge (int n1, int n2) |
| delete the edge (if it exists) between the two given nodes | |
| void | contract_edge (int n1, int n2) |
| contract the edge between the two given nodes; second node unused afterwards | |
| 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 | |
Friends | |
| Graph | renumber_nodes (const Graph &me) |
| renumber the nodes | |
| void | relocate (Graph *from, Graph *to) |
| relocate the data | |
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 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: { edge(n1,n2) == -edge(n2,n1) }.
The whole data structure is attached to the Graph object via a smart pointer with reference counting.
1.5.6