This operation takes O(log(out_degree(n1) + in_degree(n2))) time when a new edge is created,
and O(log(out_degree(n1))) when an existing edge is found.
Both variants (with and without const) are available.
The exact result type can be referred to as typename Graph::in_neighbor_list_ref
or typename Graph::const_in_neighbor_list_ref.
This assertion is checked only in the INDEX_CHECKS compilation mode.
Depending on the const attribute of the original Graph object.
The exact result type can be referred to as typename Graph::out_neighbor_list_ref
or typename Graph::const_out_neighbor_list_ref.
Either a functor class satisfying the extended requirements
for unary operations, or
an untyped template of such a class wrapped into BuildUnary or BuildUnaryIt
(preferably expressed via the convenience typedef from namespace polymake::operations.
The concrete graph type hidden behind the GenericGraph.
Either a functor class satisfying the extended requirements
for binary operations, or
an untyped template of such a class wrapped into BuildBinary or BuildBinaryIt
(preferably expressed via the convenience typedef from namespace polymake::operations.
This operation takes O(log(out_degree(n1))) time.
The exact result type can be referred to as typename Graph::neighbor_list_ref
or typename Graph::const_neighbor_list_ref.
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 binary balanced 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 REFCOUNT.
If a directed graph is constructed from an undirected one, the adjacent nodes will be connected
by pairs of oppositely directed edges, both having equal attributes.
If an undirected graph is constructed from a directed one, two nodes will be adjacent if there was
at least one edge in the source graph connecting the prototype nodes.
The same conversion rules as for the analogous constructors apply.
void std::swap(Graph&, Graph&);
Exchange the data efficiently.
void Graph::resize(int n);
Change the number of nodes to n. If it is increased, new isolated nodes are created,
and their attributes initialized with the default constructor of NodeAttr.
If it is decreased, the nodes with indices >=n are destroyed together with all incident edges.
void Graph::clear(int n=0);
Make the graph empty, optionally allocate n new isolated nodes.
int Graph::add_node();
template <typename Data>
int Graph::add_node (const Data&);
Append a new isolated node, return its index. The second variant stores the given data in the
attribute of the created node.
Delete the node(s) with given indices and all incident edges, renumber the remaining nodes.
Node indices must lie within the valid range.
This operation costs O(#nodes * average node degree), since the node array is reallocated.
If you are not concerned about the contingency of the valid node indices, you can avoid this performance penalty
by using the following expression: GRAPH.out_edges(n).clear(); GRAPH.in_edges(n).clear();
(The second call is superfluous in the undirected case.) This will remove all incident edges, but let the
node in the graph. The node attribute data will neither be destroyed.
Remove all isolated nodes (that is, without incident edges,) and renumber the rest. If you need to know
the exact mapping between the old and new node indices, you can supply an output iterator
(e.g., back_inserter of a std::list.) The old indices of remaining nodes
will be assigned to it in the ascending order.
A graph is not a container in the STL sense, since its structure is more complex than a plain linear sequence of data items.
There are, however, various access functions, which allow to visit some graph components in a sequential order, thus yielding
STL-conforming pseudo-containers.
All access functions described below are applicable to any member of the GenericGraph family.
Depending on the nature of the source graph, they can return either a masqueraded reference to the graph or a temporary
pseudo_container object. The exact return types are exported by the source graph class under the names NAME_ref
and const_NAME_ref. To get the pure pseudo-container type (without reference), use the corresponding typename
without _ref suffix.
Explore the graph as a sequence of its edges. Each edge is visited once, whether in directed or undirected case.
The exact visiting order results from the internal data representation, one should not rely upon it.
An iterator over the edge container points at the edge attribute, typename Graph::edge_attr.
This iterator also offers methods from_node() and to_node(), returning the indices of the source and target node of the
current edge.
Treate the graph like a sequence of incident edge lists, but ignoring the node attributes.
An iterator yields the list of outgoing or ingoing edges incident to the current node.
int out_degree (int n) const;
int in_degree (int n) const;
Get the number of outgoing and ingoing edges incident to the node n.
An abbreviaton for out_edges(n).size() and in_edges(n).size() correspondingly.
The node must already exist.
int degree (int n) const;
In undirected case, a synonym for out_degree(n) and in_degree(n).
In directed case, the sum of both.
Graph objects, like other PTL containers, can be read from and written to persistent storage via the
GenericIO interface. However, the GenericGraph classes have additional masquerading functions allowing
to exchange the incidence structure separately from attribute values. In the following examples G denotes
a GenericGraph<...,NodeAttr,EdgeAttr> object, and source and target some objects implementing
the GenericInput and GenericOutput interface, e.g. born by Poly::give() and Poly::take().
source >> ignore_node_attrs(G);
Reads the incidence structure and edge attributes of Graph<nothing,EdgeAttr> ,
the node attributes of G are initialized with default constructor NodeAttr().
source >> ignore_node_attrs<OtherNodeAttr>(G);
Reads the incidence structure and edge attributes of Graph<OtherNodeAttr,EdgeAttr> ,
the node attributes of G are initialized with default constructor NodeAttr().
target << ignore_node_attrs(G);
Stores the graph as Graph<nothing,EdgeAttr> , omitting the node attributes.
The IndexedSubgraph implements the induced subgraph of any graph object belonging to the GenericGraph family. As usual in
PTL, an IndexedSubgraph is a leight-weight proxy object which merely narrows the view onto the original graph; no data is being
copied.
#include <IndexedGraph.h>
using namespace polymake;
Select an induced subgraph by the given set of node indices.
The nodes are not renumbered. For example, IndexedSubgraph::node(n) and G.node(n) would refer to the same node
attribute.
The random access methods are constrained to the selected nodes. For example, an attempt to create
an edge leading to a node not contained in the node subset raises an exception.
Like above, but the selected nodes appears renumbered as 0, 1, ... nodes.size()-1.
The random access methods are available only if both the source graph (masqueraded as its node_container) and the node subset are random access containers.