Graph Class

Prerequisits

#include <Graph.h>

using namespace polymake;

Introduction

enum graph::kind { undirected, directed };
template <class NodeAttr=nothing, class 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 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.

Construction

Graph();

Create an empty graph with 0 nodes.

explicit Graph (int n);

Create a graph with n isolated nodes.

template <class OtherNodeAttr, class OtherEdgeAttr, graph::kind other_kind>

explicit Graph (const Graph<OtherNodeAttr, OtherEdgeAttr, other_kind>&);

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.

Modification

A GenericSet of integer non-negative indices or a Complement thereof.

template <class OtherNodeAttr, class OtherEdgeAttr, graph::kind other_kind>

Graph::operator= (const Graph<OtherNodeAttr, OtherEdgeAttr, other_kind>&);

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.

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 may be checked to 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 not be destroyed, too.

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.) It will get the old indices of remaining nodes assigned in the ascending order.

Data access

int Graph::nodes() const;

Tell the current number of nodes.

Sequential access

Depending on the const attribute of the original Graph object.

The exact result type can be referred to as typename Graph::neighborhood.

The exact result type can be referred to as typename Graph::neighborhood::row_type.

There are two pseudo-container STL-comforming classes that a Graph can be disguised as:

typename Graph::node_container& nodes (Graph&);

const typename Graph::node_container& nodes (Graph&) const;

A sequence of the nodes.

The iterator over node_container offers the following access methods:

const NodeAttr& operator* () const;

The attribute of the current node.

const typename Graph::out_edge_list& out_edges() const;

A list of the outgoing edges incident to the current node.

const typename Graph::in_edge_list& in_edges() const;

A list of the ingoing edges incident to the current node. In the undirected case, equivalent to out_edges().

const EdgeAttr& out_edge (int n2) const;

Create or find the edge going from the current node to n2.

const EdgeAttr& in_edge (int n2) const;

Create or find the edge going from n2 to the current node.

const EdgeAttr& edge (int n2) const;

A synonym for out_edge() and in_edge() in the undirected case.

int out_degree() const;

The number of outgoing edges incident to the given node. An abbreviaton for out_edges().size().

int in_degree() const;

The number of ingoing edges incident to the given node. An abbreviaton for in_edges().size().

int degree() const;

In undirected case, a synonym for out_degree() and in_degree(). In directed case, the sum of both.

const GenericSet& neighbors() const;

Indices of the nodes adjacent to the given one. In directed case, only outgoing edges are considered.

typename Graph::edge_container& edges (Graph&);

const typename Graph::edge_container& edges (Graph&) const;

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.

typename Graph::out_edge_list;

typename Graph::in_edge_list;

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 node_container iterator or from random-access functions.

The iterators over all edge lists described above offer the following access methods:

const EdgeAttr& operator* () const;

Attribute of the current edge.

int from_node() const;

int to_node() const;

Indices of the terminal nodes of the current edge.

const GenericIncidenceMatrix& neighborhood_matrix (const Graph&);

Another form of masquerading: "extract" the adjacency information, ignoring the attributes. The incidence matrix is obviously symmetric in the undirected case.

Random access

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(log(out_degree(n1))) time.

This operation takes O(out_degree(n1) * log(out_degree(n1)) + out_degree(n2) * log(out_degree(n2)) ) time.

NodeAttr& Graph::node (int n);

const NodeAttr& Graph::node (int n) const;

Random access to the attribute of the node n. The node index range check can be activated.

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 index range check can be activated.

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.

typename Graph::out_edge_list& Graph::out_edges (int n);

typename Graph::in_edge_list& Graph::in_edges (int n);

The list of outgoing and ingoing edges incident to the node n. In undirected case, both methods return the same object. The node index range check can be activated.

There are also const methods returning references to immutable edge lists.

const GenericSet& Graph::neighbors (int n);

Set of indices of nodes adjacent to the node n. The node index range check can be activated.

void Graph::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 node index range check can be activated.

Costs.

EdgeAttr& Graph::edge (int n1, int n2);

Find an edge connecting the nodes n1 and n2 or create one; return the reference to its attribute. The node index range check can be activated.

Costs.

const EdgeAttr& Graph::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 node index range check can be activated.

Costs.

bool Graph::edge_exists (int n1, int n2) const;

Check whether an edge connecting the nodes n1 and n2 exists. The node index range check can be activated.

Costs.

void Graph::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 node index range check can be activated.

Costs.

Input/output

std::ostream& operator<< (std::ostream&, const Graph&);

Print the graph to the output stream as a list of node-related items. Each item is a pair of the node attribute and the outgoing edge list, enclosed in parentheses. The edge list consists in its turn of pairs of target node index and edge attribute, also enclosed in parentheses.

If the node attribute is lacking (nothing), then it does not appear in the output, the parentheses are neither printed. The same applies to the edge attributes.

For an undirected graph, each edge is printed twice (in the lists of both terminal nodes) with identical attribute value.

explicit Graph (Poly&);

Poly& operator>> (Poly&, Graph&);

Read a property from the polymake server. Parse errors are reported by raising the std::iostream::failure exception in the constructor, or via std::iostream::fail() flag in the input operator.

It is allowed to construct the attributed graph from external data representing an attributeless graph (then the attributes are initialized with default constructor,) or vice versa (the attributes are simply ignored.)