Generic graph

This is a (in my opinion) super general graph class that contains some redundant information, but makes graph operations simpler and easier to understand. It's not optimal, but that's not the point.

First off, a graph contains 2 kinds of elements: nodes and edges. So there are actually 3 classes outlined below. Schematically, the way the node and edge pointers work is shown in the figure below.

Edge class

#define DISABLE_AUTO_ID 1

template <class N, class E>

class _edge{
public:
	E val;
	int _visit;

	int visit;
	bool directed;
	_node<N,E>* from;

	_node<N,E>* to;
	int id;
	static int nextid;

	_edge();
	_edge(const E &value);
	_edge(const E &value, _node<N,E>* fromNode, _node<N,E>* toNode);
	_edge(const E &value, bool isdirected);
	_edge(const E &value, bool isdirected, _node<N,E>* fromNode, _node<N,E>* toNode);

	_edge(int setid);
	_edge(int setid, const E &value);
	_edge(int setid, const E &value, _node<N,E>* fromNode, _node<N,E>* toNode);
	_edge(int setid, const E &value, bool isdirected);
	_edge(int setid, const E &value, bool isdirected, _node<N,E>* fromNode, _node<N,E>* toNode);
};

You first notice the template contains two elements. One is the datatype for the node data payload (suck as a struct for x and y coordinates of a point), and the second is for the edge data payload (suck as a struct containing length and speed factors).

The data inside the class is as follows: val is the data payload, id is a unique identifier for the node (although it need not actually be unique). The pointers from and to are pointers to the nodes that the edge connects. The boolean directed specifies whether or not the edge is directed (so that the from and to identifiers have some significance).

The remaining variables are mainly for internal use. visit and _visit are temporary variables used for traversing a graph (the underlined one is reserved for graph methods, and the non-underlined version should be used by external functions wishing to traverse the graph). These are usually used as booleans to mark off whether an edge has been visited or not (although you can use them for counting visits). The static nextid stores the next available id if you want the graph to automatically assign id values for you. This can be disabled with the preprocessor option shown on top.

The constructors are largely self explanatory. If they're not, see the source code to see what they do. You could always just call the default constructor and set the values yourself since everything's public anyway.

Node class

#define DISABLE_AUTO_ID 1
#define VL_GRAPH_NODE_PAYLOAD /* */

template <class N, class E>

class _node{
public:
	VL_GRAPH_NODE_PAYLOAD
	N val;
	int _visit;

	int visit;
	list<_edge<N,E>* > edges;

	int id;
	static int nextid;

	_node();
	_node(const N &value);
	_node(int setid);
	_node(int setid, const N &value);
	
	void add(const E &eval, const N &nval);
	void add(_edge<N,E>* e, _node<N,E>* n);

	void append(const E &eval, const N &nval);
	void append(_edge<N,E>* e, _node<N,E>* n);

	void prepend(const E &eval, const N &nval);
	void prepend(_edge<N,E>* e, _node<N,E>* n);

	void add(int i, const E &eval, const N &nval); // index i is NOT directed-sensitive
	void add(int i, _edge<N,E>* e, _node<N,E>* n); // index i is NOT directed-sensitive

	void remove(_node<N,E>* n);

	void unlink(_node<N,E>* n);
	void unlink_all();
	
	_node<N,E>* operator[](int index); // use negative indices for arbitrary indexing of neighbors, positive for directed-sensitive indexing

};

And now, we look at the node class. The node class contains val, visit, _visit, id, and nextid with the same uses as in the edge class. The only differences are edges which is a linked list of edges that this node is connected to, and VL_GRAPH_NODE_PAYLOAD which is a #define that allows one to define actual member payloads for the node class, rather than bundling it all up in a struct for val. This is quite useful for implementation of algorithms that need some temporary storage, but which should not go into val for code that makes more logical sense.

The methods are mostly for managing the links between nodes and edges. add adds a given node as a neighbor using the provided edge. The top two versions let you specify the member data or an actual pointer to the objects. The other two add methods are not actually implemented but should allow you to add the edge at a particular index of the edges list. append and prepend methods are the same as add but add to the front and back of the edges list.

The remove method should scan the edge connectivity list for the given neighbor node and if it is indeed a neighbor, delete it. It is currently not implemented because deletion is handled by the user and not the object. Which leads into the unlink methods. It does what remove should do, except it simply deletes the connecting edge and nullifies the corresponding pointers in the nodes. unlink_all unlinks all neighboring nodes.

The remaining method is the neighbor indexing operator. It will essentially just index the edge connectivity list for the corresponding neighbor node. There is a nuance in that if the edges are directed, then positive indices respect directionality and negative indices don't.

Graph class

template <class N, class E>
class graph{
public:
	_node<N,E> *_start;

	iList<_node<N,E> > *_nodes;
	iList<_edge<N,E> > *_edges;

	graph();
	graph(const graph<N,E> &G);
	~graph();
	void _deletenodes(_node<N,E>* n);

	void _unvisit(_node<N,E>* n);
	void unvisit();
	void _unvisit_nodes(_node<N,E>* n);
	void unvisit_nodes();
	void _unvisit_edges(_node<N,E>* n);
	void unvisit_edges();
	
	const graph<N,E>& operator= (const graph<N,E> &G);

	int nodes() const;
	int edges() const;

	void add(_node<N,E>* S, const E &eval, const N &nval);
	void add(_node<N,E>* S, _edge<N,E>* e, _node<N,E>* n);
	void append(_node<N,E>* S, const E &eval, const N &nval);
	void append(_node<N,E>* S, _edge<N,E>* e, _node<N,E>* n);
	void prepend(_node<N,E>* S, const E &eval, const N &nval);
	void prepend(_node<N,E>* S, _edge<N,E>* e, _node<N,E>* n);
	void add(int i, _node<N,E>* S, const E &eval, const N &nval); // index i is NOT directed-sensitive
	void add(int i, _node<N,E>* S, _edge<N,E>* e, _node<N,E>* n); // index i is NOT directed-sensitive
	void remove(_node<N,E>* n);

	void _printnodes(output &out, _node<N,E>* n);
	void print(output &outputter);
};

This is the container class, and it contain mostly methods for working with the elements within it. The class stores a pointer to any starting node, although this is not usually necessary unless the built in output functions are used. There are also lists of all nodes and edges in the graph.

The visit methods are for resetting the visit variables back to zero in the nodes and edges once they have been used. The deconstructor uses _deletenodes to recursively delete every node and edge from the start node. If no start node is specified, the graph is not actually deleted from memory. Also, if the graph is not well connected, parts of it will not be traversed or deleted.

There is an assignment operator that is not yet implemented for duplicating a graph.

The nodes() and edges() methods return the length of the nodes and edges lists, respectively. The print functions at the bottom output the graph in a nice format, but it is recommended that custom output functions be used since the payload values do not have outputter overloads.

The large block of methods with the same name as those in the node class simply call the corresponding function on the first argument node with the remaining arguments.