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.
This assertion is checked only in the INDEX_CHECKS compilation mode.
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.
The exact result type can be referred to as typename Graph::neighborhood::col_type.
Depending on the const attribute of the original Graph object.
The exact result type can be referred to as typename Graph::neighborhood.
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.
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 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 placing some container class in the edge attributes.
The whole data structure is attached to the Graph object via a smart pointer with reference counting.
Unlike other top-level container classes in Polymake Template Library, Graph does not belong to any
generic family: There are simply no other graph classes yet. This may change in the future releases.
Create a graph isomorphical to the given one, with possible attribute conversion.
If a directed graph is constructed from an undirected one, the adjacent nodes will be connected
by pairs of oppositely directed edges, having equal attribute.
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 constructor 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 be neither 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 sequence of all 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.
Containers of edges incident to some fixed node, implemented as balanced binary trees.
In undirected case, both types are identical. The edges are visited in the ascending order of the opposite node indices.
References to these containers are obtained either via the
Graph::node_container iterator or from the random-access functions Graph::out_edges,Graph::in_edges.
The iterators over all edge lists described above offer the following access methods:
Another form of masquerading: "extract" the adjacency information, ignoring the attributes.
Obviously, the incidence matrix is symmetric in the undirected case.
int Graph::out_degree (int n) const;
int Graph::in_degree (int n) const;
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 Graph::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, Graph has additional masquerading functions allowing
to exchange the incidence structure separately from attribute values. In the following examples G denotes
a Graph<NodeAttr,EdgeAttr> object, and source and target some objects implementing
the GenericInput and GenericOutput interface, e.g. born by give() and 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.