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 operation takes O(out_degree(n1) * log(out_degree(n1)) + out_degree(n2) * log(out_degree(n2)) ) time.
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.
A GenericSet of integer non-negative indices or a Complement thereof.
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.

Prerequisits

#include <Graph.h>
using namespace polymake; 

Introduction

enum graph::kind { undirected, directed, skew }; template <typename NodeAttr=nothing, typename EdgeAttr=nothing, graph::kind kind=undirected> class Graph;

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.

Generic type

template <typename _Graph, typename NodeAttr=typename _Graph::node_attr, typename EdgeAttr=typename _Graph::edge_attr, graph::kind _dir=Graph::dir> class GenericGraph;

The GenericClass for all graph classes. Defines the following types and constants:

node_attr NodeAttr, the node attribute type
edge_attr EdgeAttr, the edge attribute type
dir _dir, the kind of the graph, as described above
top_type _Graph, the concrete graph object behind the generic reference
generic_type GenericGraph<_Graph> itself
persistent_type Graph<node_attr, edge_attr, dir>

Construction

Graph();
Create an empty graph with 0 nodes.
explicit Graph (int n);
Create a graph with n isolated nodes (without edges).
template <typename OtherGraph, graph::kind other_kind> Graph (const GenericGraph<OtherGraph, NodeAttr, EdgeAttr, other_kind>&);
Create a graph isomorphical to the given one.
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.
template <typename OtherGraph, typename OtherNodeAttr, typename OtherEdgeAttr, graph::kind other_kind> explicit Graph (const GenericGraph<OtherGraph, OtherNodeAttr, OtherEdgeAttr, other_kind>&);
Copying with attribute conversion is also possible, but requires an explicit constructor call.

Modification

template <typename OtherGraph, graph::kind other_kind> Graph::operator= (const GenericGraph<OtherGraph, NodeAttr, EdgeAttr, other_kind>&); template <typename OtherGraph, typename OtherNodeAttr, typename OtherEdgeAttr, graph::kind other_kind> Graph::operator= (const GenericGraph<OtherGraph, OtherNodeAttr, OtherEdgeAttr, other_kind>&);
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.
void Graph::delete_node(int n); template <typename Set> void Graph::delete_nodes(const Set&);
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.
void Graph::squeeze(); template <typename node_index_consumer> void Graph::squeeze(node_index_consumer nc);
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.

Data access

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.

typename Graph::const_node_container_ref nodes (const GenericGraph&);
Explore the graph as a sequence of its nodes.
An iterator over the node container points at the node attribute, typename Graph::node_attr.
This iterator also replicates all random access methods of the source graph, substituting the current node as the first argument:
node_it.out_edges() == G.out_edges(node_it.index()); node_it.out_edge(n2) == G.edge(node_it.index(), n2); node_it.degree() == G.degree(node_it.index());
and so on.
typename Graph::const_edge_container_ref edges (const GenericGraph&);
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.
typename Graph::const_out_edge_list_container_ref out_edge_lists (const GenericGraph&); typename Graph::const_in_edge_list_container_ref in_edge_lists (const GenericGraph&);
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.
typename Graph::const_neighborhood_matrix_ref neighborhood_matrix (const GenericGraph&);
Get an incidence matrix describing the node adjacency relation.

Random access

The following methods are defined for the persistent class Graph, as well as for the induced subgraph classes IndexedSubgraph.

int nodes() const;
Tell the current number of nodes.
const NodeAttr& node (int n) const;
Get the attribute of the node n. The node must already exist.
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.
typename Graph::const_out_edge_list_ref out_edges (int n) const; typename Graph::const_in_edge_list_ref in_edges (int n) const;
The list of outgoing and ingoing edges incident to the node n. In undirected case, both methods return the same object. The node must already exist.
GenericSet out_neighbors (int n) const; GenericSet in_neighbors (int n) const;
Indices of nodes connected by outgoing / ingoing edges to the node n. The node must already exist.
GenericSet neighbors (int n) const;
Indices of nodes adjacent to the node n. Defined for undirected graphs only.
void create_edge (int n1, int n2, const EdgeAttr& d);
Create an edge from the node n1 to the node n2 (if not already there), store d as its attribute.
The nodes must already exist.
EdgeAttr& edge (int n1, int n2);
Find an edge connecting the nodes n1 and n2 or create one; return the reference to its attribute.
The nodes must already exist.
const EdgeAttr& edge (int n1, int n2) const;
Find an edge connecting the nodes n1 and n2, return its attribute. Raise a no_match exception if the edge does not exist.
The nodes must already exist.
bool edge_exists (int n1, int n2) const;
Check whether an edge connecting the nodes n1 and n2 exists.
The nodes must already exist.
void delete_edge(int n1, int n2);
Remove the edge from node n1 to node n2. Nodes are not deleted, even if they lose all incident edges.
The nodes must already exist.

Input/output

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.
source >> ignore_edge_attrs(G); source >> ignore_edge_attrs<OtherEdgeAttr>(G); target << ignore_edge_attrs(G);
The same as above, but skipping the edge attributes.
source >> ignore_attrs(G); source >> ignore_attrs<OtherNodeAttr,OtherEdgeAttr>(G); target << ignore_attrs(G);
The same as above, but skipping all attributes. The graph being stored in the last line, looks like Graph<nothing,nothing> .

Subgraph

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; 
template <typename GraphRef, typename SetRef, typename Options=void> class IndexedSubgraph; template <typename _Graph, typename _Set> IndexedSubgraph<const _Graph&, const _Set&> select_subgraph(GenericGraph<const _Graph>& G, const Set& nodes);
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.
template <typename _Graph, typename _Set> IndexedSubgraph<const _Graph&, const _Set&, Renumber<True> > induced_subgraph(const GenericGraph<_Graph>& G, const Set& nodes);
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.