C++ Graph Implementations
In this section we shall deal with the implementation of graphs.
A graph object will store nodes and arcs. Nodes are held in some container. Beyond this, I can envision two schemes for relating nodes and arcs:
- Another container holds arcs, or
- Each node has pointers or some other reference to the nodes it is related through arcs. These pointers may additionally carry a weight.
Serialization of Graphs and Node Containers
If nodes are held in an array-like container (such as an std::vector or an std::deque, then they must be refered to by index, whereas if they are held in a doubly-linked list (std::list) or a singly-linked list (std::forward_list) they must be refered to by pointer.
Doubly- or singly-linked lists are very difficult to serialize because references to their elements (pointers) will become invalid, whereas array-like data types are easy as long as the order of their elements does not change during serialization.
Consequently, an arc should consist of a to-index or a from-index if held in a node, or a from- and a to-index if held in a container of arcs within a graph.
Should Arcs Be Held in Their Nodes?
This is called native graph processing and is said to exhibit index-free adjacency.
Some reasons for adopting index-free adjacency
are:
- Holding arcs in their nodes makes for fast, straightforward traversals. When at a node, just follow the link. Query times are independent of the total size of the graph.
- All arcs from a given node or to a given node are found together in that node, whereas if arcs are stored separately they are usually ordered by source or by destination, but not by both, unless an additional indexing data structure (an std::multimap<node_id_type,size_type>, for instance) is maintained, which comes at a cost.
- Deleting a node is straightforward. Within the node, follow all its from- and to-references and delete arc information (pointers or, as I suggest elsewhere, indeces) that refers back to the node to be deleted.
One reason against this scheme is:
- Arcs would be duplicated: for each arc, the source node would hold a reference to the destination node, and the destination node would hold a reference to the source node. In the case of weighted graphs, weights would be duplicated, too.
Deletion of Nodes Held in Array-like Containers
Array-based containers keep a non-public variable that records its size, typically accessed through getter (i.e. read-only)
Deletion of a node might be implemented like this:
- delete all arcs from or to the element to be deleted,
- copy the last element to the position where the one to be deleted is found,
- decrement the size hidden variable, and
- change all indeces of value
size() to the index of the deleted element.
Therefore, deletion of array elements can only be safely effected when it is known at compile time how to find all objects refering to elements of the array (by index, as reference by pointer is suicidal).
Sketching a graph Class
The following code sketches a node template class (Node) as a struct holding some contents and a bunch of pointers to other nodes. It is then used to implement a Tree template class and a directed, unidirectional (no pointers back to parent), possibly weighted Graph template class.
Here is a sketchy class for a node. It assumes
template struct UnWeightedArc:
template <class C, class ARC = UnWeightedArc<C> >
class Node {
vector<ARC> arcs;
C contents;
public:
// member functions and constructors
}
Here is a sketchy struct for a weighted arc:
template <class C, class W=float> struct WeightedArc {
typedef Node<C,WeightedArc<C,W> > node_type;
node_type* pDestNode;
W weight;
}
Of course, bidirectionality is easy to add, as well as events upon node visitation and link traversal, through deriving from Tree or Graph and redefining member functions such as
This is the header file (graph.h), with lots of inline definitions of member functions:
#ifndef GRAPH_H
#define GRAPH_H
#define DEBUG_GRAPH
#define DEBUG_STEP
// NOTE: LinkGraph::BreadthFirstIterator visits some nodes twice
/*
* Graphs and Trees may be implemented either
(1) as a container of nodes beside a container of arcs, or
(2) as a struct/class holding the root node,
as a node holds pointers to its children nodes, and so on.
(These classes and struct's have prefix "Link".)
*
* This file adopts the latter approach ("Link" prefix) and codes
a LinkTree<> and a LinkGraph<> class derived from LinkTree<>.
* LinkTree<> and LinkGraph<> are made up nodes (LinkNode<>'s).
* Actually, they only hold a root node,
although graphs do not a root node as such
(a node wherefrom to begin traversals).
* A LinkNode<> holds a contents and a vector or deque of arcs.
* A LinkNode<> must be indexable
because Depth First Search relies on a stack of indeces.
* Arcs are pointer-like structures and may carry a weight.
They point to a child node.
*/
#include <iostream> // used only in the implementation file
#include <iterator>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
// A graph node has content and holds 0 to n arcs
// A graph arc may have a weight and links to a node
/*
* Arcs are implemented as pointers to nodes.
* This requieres a forward declaration of LinkNode...
* Additionally...
* My arc struct's are LinkUnWeightedArc<C> and LinkWeightedArc<C>:
*/
template <class C, class ARC> struct LinkNode; // forward declaration of LinkNode<>
template <class C> struct LinkUnWeightedArc {
typedef LinkNode<C,LinkUnWeightedArc<C> > node_type;
node_type *pDestNode;
// member functions:
node_type& operator* () {return *pDestNode;};
node_type* operator->() {return pDestNode;};
// constructors:
LinkUnWeightedArc(node_type& n) : pDestNode(&n) {};
LinkUnWeightedArc(node_type* pN) : pDestNode(pN) {};
};
//template <class C, class WEIGHT> struct LinkWeightedArc; // forward declaration of 'LinkWeightedArc<>'
template <class C, class W=float> struct LinkWeightedArc {
typedef LinkNode<C,LinkWeightedArc<C,W> > node_type;
W weight;
node_type *pDestNode;
// member functions:
node_type& operator* () {return *pDestNode;};
node_type* operator->() {return pDestNode;};
// constructors:
LinkWeightedArc(node_type& n) : pDestNode(&n) {};
LinkWeightedArc(node_type* pN) : pDestNode(pN) {};
LinkWeightedArc(node_type& n, const W& w) : pDestNode(&n), weight(w) {};
LinkWeightedArc(node_type* pN, const W& w) : pDestNode(pN), weight(w) {};
};
// class LinkNode<>
template <class C, class ARC = LinkUnWeightedArc<C> >
class LinkNode {
vector<ARC> arcs;
C contents;
public:
typedef LinkNode<C,ARC> node_type;
typedef typename vector<ARC>::iterator iterator;
typedef typename vector<ARC>::const_iterator const_iterator;
// iterator interface:
iterator begin() {return arcs.begin();};
const_iterator begin() const {return arcs.begin();};
iterator end() {return arcs.end();};
const_iterator end() const {return arcs.end();};
// other member functions:
unsigned int size() const {return arcs.size();};
bool has_children() const {return !arcs.empty();};
C& get_contents() {return contents;};
const C& get_contents() const {return contents;};
// operators:
node_type& operator+=(node_type& n);
node_type& operator+=(ARC& a);
bool operator==(const LinkNode<C,ARC>& n) const {return this==&n;};
ARC& operator[](unsigned int idx) {return arcs[idx];};
const ARC& operator[](unsigned int idx) const {return arcs[idx];};
operator C() {return contents;}
// constructors:
LinkNode(const C& t) : contents(t) {};
LinkNode(const C& t, iterator b, iterator e) : contents(t), arcs(b,e) {};
}; // end of LinkNode<>
/*
* A LinkTree<> is a LinkGraph<> without cycles.
* Therefore a LinkTree<> must be a base class of LinkGraph<>.
* LinkGraph<> only adds code that checks that a node is not visited twice
*/
template <class C, class ARC = LinkUnWeightedArc<C>, class N=LinkNode<C,ARC> >
class LinkTree {
public:
typedef N node_type;
typedef const N const_node_type;
typedef LinkTree<C,ARC,N> tree_type;
N& rootNode; // may be a reference as long as initialized upon LinkGraph<> construction
LinkTree(N& n) : rootNode(n) {};
// LinkTree<>::iterator
class iterator : public ::iterator<forward_iterator_tag, C, ptrdiff_t, C*, C&> {
public:
// member functions:
virtual C& get_contents() =0;
virtual const C& get_contents() const =0;
virtual node_type* operator->() =0;
virtual const_node_type* operator->() const =0;
// comparison between iterators is made on "virtual bool end() const",
// which returns whether a traversal has ended:
virtual bool end() const =0;
bool operator==(const iterator& it) const {return end() == it.end();};
};
// class tree_type::BreadthFirstIterator:
class BreadthFirstIterator : public iterator {
protected:
queue<node_type*> frontier; // queue of pointers to nodes to be processed
node_type* pNode;
public:
BreadthFirstIterator& operator++();
//
C& get_contents() {return pNode->get_contents();};
const C& get_contents() const {return pNode->get_contents();};
node_type* operator->() {return pNode;};
const_node_type* operator->() const {return pNode;};
//
bool end() const {return frontier.empty();};
operator bool () const {return !frontier.empty();};
virtual BreadthFirstIterator& push_children(node_type* pN);
// constructors:
BreadthFirstIterator(node_type& n) : pNode(&n) {push_children(&n);};
BreadthFirstIterator(node_type* pN) : pNode(pN) {push_children(pN);};
}; // end of LinkTree<>::BreadthFirstIterator
// BreadthFirstIterator begin_breadth(node_type& n = tree_type::rootNode) const {return BreadthFirstIterator( n);};
BreadthFirstIterator begin_breadth(node_type* pN) const {return BreadthFirstIterator(pN);};
BreadthFirstIterator begin_breadth(node_type& n) const {return BreadthFirstIterator(&n);};
BreadthFirstIterator begin_breadth() {return BreadthFirstIterator(rootNode);};
/*
* LinkTree<>::Depth-First Iterator
defines struct step,
each of which holds:
- a pointer to the node that the iterator is at
- the index that gives the next node to be dropped into
(so that the next node is (*pNode)[index])),
- and the total number of children of the pointed-to node
* Further, a stack of steps (named 'state') is maintained
so that the top step's pointed-to node is the current node
*
*/
class DepthFirstIterator; // forward declaration
DepthFirstIterator begin_depth() const;
class DepthFirstIterator : public iterator {
public:
struct step {
unsigned int cur_idx; // which child of pNode's is to be visited next?
unsigned int total; // total number of pNode's children
N* pNode;
// member functions:
node_type* next_pChild() {return pNode->operator[](cur_idx).pDestNode ;};
const_node_type* next_pChild() const {return pNode->operator[](cur_idx).pDestNode ;};
node_type& next_child( ) {return *(pNode->operator[](cur_idx).pDestNode);};
const_node_type& next_child( ) const {return *(pNode->operator[](cur_idx).pDestNode);};
bool has_next_children() const {return cur_idx < total;}; // is cur_idx valid?
operator bool () const {return cur_idx < total;}; // is cur_idx valid?
step& operator++() {++cur_idx; return *this;}; // called upon backtracking
// constructors:
step(N& n);
step(N& n, unsigned int i);
step(N* pN);
step(N* pN, unsigned int i);
}; // end of struct 'LinkTree<>::DepthFirstIterator::step'
stack<step> state;
// member functions:
bool end() const {return state.size() == 1 && !state.top();};
operator bool() const {return state.size() > 1 || state.top();};
N* current_pNode() {return state.top().pNode;};
const N* current_pNode() const {return state.top().pNode;};
N& current_node() {return *(state.top().pNode);};
const N& current_node() const {return *(state.top().pNode);};
// check that top() 'has_next_children()' before calling next_pNode() and next_node(), which work blindly:
N* next_pNode() {return state.top().next_pChild();};
const N* next_pNode() const {return state.top().next_pChild();};
N& next_node() {return state.top().next_child();};
const N& next_node() const {return state.top().next_child();};
virtual C& get_contents() {return current_node().get_contents();};
virtual const C& get_contents() const {return current_node().get_contents();};
// operators:
bool operator==(const N& n) const {return current_node()==n;};
// bool operator==(const DepthFirstIterator& it) const {return current_node()==it.current_node();};
bool operator==(const DepthFirstIterator& it) const;
N& operator*() {return current_node();}
const N& operator*() const {return current_node();}
node_type* operator->() {return current_pNode();};
const_node_type* operator->() const {return current_pNode();};
// member functions for actually traversing a Tree<>:
bool has_next_children() const {return state.top().has_next_children();};
virtual DepthFirstIterator& sink();
virtual DepthFirstIterator& backtrack();
DepthFirstIterator& operator++(); // get iterator to point to or hold the next node
// through either sink()-ing or backtrack()-ing
// constructor:
DepthFirstIterator(N& n) {state.push(step(n));};
}; // end of struct 'LinkTree<>::DepthFirstIterator'
class StopDepthFirstIterator; // forward declaration
StopDepthFirstIterator begin_depth(unsigned int d) const;
class StopDepthFirstIterator : public DepthFirstIterator {
public:
const unsigned int depth;
bool has_next_children() const;
StopDepthFirstIterator& sink() { DepthFirstIterator::sink(); return *this;};
bool end() const {return DepthFirstIterator::end();};
StopDepthFirstIterator& backtrack() {DepthFirstIterator::backtrack(); return *this;};
StopDepthFirstIterator& operator++();
StopDepthFirstIterator(N& n, unsigned int d) : DepthFirstIterator(n), depth(d) {};
};
};
// class LinkGraph<> is derived from LinkTree<>
template <class C, class ARC = LinkUnWeightedArc<C>, class N=LinkNode<C,ARC> >
class LinkGraph : public LinkTree<C,ARC,N> {
public:
typedef N node_type;
typedef const N const_node_type;
typedef LinkTree<C,ARC,N> tree_type;
// constructor:
LinkGraph(N& n) : LinkTree<C,ARC,N>(n) {};
/*
* LinkGraph<C,ARC,N> iterators are derived from LinkTree<C,ARC,N>
* (depth-first, bound depth-first, and breadth-first).
* They rely on mixin class Visited
*/
class Visited {
protected:
set<const N*> pVisited; // pointers to all visited nodes
public:
void include(const N& n) {pVisited.insert(&n);};
void include(const N* pN) {pVisited.insert(pN);};
bool visited(const N* pN) const {return pVisited.find(pN) != pVisited.end();};
bool visited(const N& n) const {return pVisited.find(&n) != pVisited.end();};
};
// class BreadthFirstIterator:
class BreadthFirstIterator : public tree_type::BreadthFirstIterator, public Visited {
public:
BreadthFirstIterator& push_children(node_type* pN); // still unimplemented?
BreadthFirstIterator(node_type& n) : tree_type::BreadthFirstIterator( n) {}; //{push_children(&n);};
BreadthFirstIterator(node_type* pN) : tree_type::BreadthFirstIterator(pN) {}; //{push_children(pN);};
};
BreadthFirstIterator begin_breadth(node_type* pN) const {return BreadthFirstIterator(pN);};
BreadthFirstIterator begin_breadth(node_type& n) const {return BreadthFirstIterator(&n);};
BreadthFirstIterator begin_breadth() {return BreadthFirstIterator(tree_type::rootNode);};
// A LinkGraph<>::Depth-First Iterator:
class DepthFirstIterator; // forward declaration
DepthFirstIterator begin_depth() const;
class DepthFirstIterator : public tree_type::DepthFirstIterator, public Visited {
public:
DepthFirstIterator& sink();
DepthFirstIterator& backtrack(); // additionally increments top().cur_idx if next child has already been visited
DepthFirstIterator(N& n) : tree_type::DepthFirstIterator::DepthFirstIterator(n) {};
};
// class LinkGraph<>::StopDepthFirstIterator:
class StopDepthFirstIterator; // forward declaration
StopDepthFirstIterator begin_depth(unsigned int d) const;
class StopDepthFirstIterator : public DepthFirstIterator {
public:
const unsigned int depth;
StopDepthFirstIterator& sink() { DepthFirstIterator::sink(); return *this;};
bool end() const {return DepthFirstIterator::end();};
StopDepthFirstIterator& backtrack() {DepthFirstIterator::backtrack(); return *this;};
StopDepthFirstIterator& operator++();
StopDepthFirstIterator(N& n, unsigned int d) : DepthFirstIterator(n), depth(d) {};
};
};
#endif
All files of this project are found in a separate appendix.
Visualize Your Data With VTK
The Visualization Toolkit (VTK) is an open-source, freely available software system for 3D computer graphics, image processing, and visualization. It consists of a C++ class library and several interpreted interface layers including Tcl/Tk, Java, and Python. VTK supports a wide variety of visualization algorithms including scalar, vector, tensor, texture, and volumetric methods, as well as advanced modeling techniques such as implicit modeling, polygon reduction, mesh smoothing, cutting, contouring, and Delaunay triangulation. VTK has an extensive information visualization framework and a suite of 3D interaction widgets. The toolkit supports parallel processing and integrates with various databases on GUI toolkits such as Qt and Tk. VTK is cross-platform and runs on Linux, Windows, Mac, and Unix platforms.
VTK is part of Kitware's collection of commercially supported open-source platforms for software development.
VTK is Language Agnostic
The core functionality of VTK is written in C++ to maximize efficiency. That core is then wrapped into other language bindings to expose VTK's functionality to a wider audience. Currently, VTK's build system has built-in support to generate primary bindings to Python, Java, and Tcl. External bindings to Ada and C# are also available.