// © Copyright 1997. Joseph Bergin. All rights reserved.

#ifndef Graph_H
#define Graph_h

#include <vector.h>
#include <deque.h>

template <class T> class DiGraph;

template <class T>
class GraphNode
{	public:	// No public constructor.  
		T value;
		T operator*(){ return value; }

	private:
		int _index;
			// Invariant.  The value of _index is always the location
			// of the node within its graph's implementing structure.  
		bool _mark;
		
		//vector < GraphIterator<T> > _neighbors;
		vector < vector< GraphNode<T> >::iterator > _neighbors;
		//vector < DiGraph<T>::iterator > _neighbors;
		void mark(){_mark = true;}
		void unmark(){_mark = false;}
		bool marked(){return _mark;}
		
		GraphNode(const T& t = T()):value(t), _index(-1), _mark(false), _neighbors(){}
		GraphNode(const T& t, int index):value(t), _index(index), _mark(false), _neighbors(){}

	friend class DiGraph<T>;
	friend class vector< GraphNode<T> >; //Lets us keep default constructor private. 
};

template <class T> // Requires T support operator<<.
ostream& operator<<(ostream& os, const GraphNode<T>& gn)
{	os << gn.value;
	return os;
}

/*
template <class T>
class GraphIterator // Forward Iterator. Could be RandomAccess. 
{	typedef GraphNode<T> node;
	typedef vector<node>::iterator pointer;
	public:
		node& operator*()
		{	return *_here;
		}
		
		bool operator==(const GraphIterator<T>& gi)const
		{	return _here == gi._here;
		}
		
		node& operator++()
		{	_here++;
			return *_here;
		}
		
		node& operator++(int)
		{	node& result = *_here;
			_here++;
			return result;
		}
	private:
		pointer _here;
		
		GraphIterator(pointer where = NULL)
		:	_here(where)
		{
		}
		
		pointer operator()()
		{	return _here;
		}
		
	friend class DiGraph<T>;		
	friend class vector<GraphIterator<T> >;
};
*/

template <class T>
class DiGraph // Directed graphs.  
{	public:
		typedef T value_type;
		typedef GraphNode<T> node;
		//typedef GraphIterator<T> iterator;
		typedef vector<node>::iterator iterator;
		typedef vector<node>::const_iterator const_iterator;
		
		DiGraph():_vertices(){}
		
		// Create GraphNodes using the following member. 
		node& newGraphNode(const T& t)
		{	_vertices.push_back(node(t, _vertices.size()) );
			return _vertices.back();
		}
		
		// Connect two nodes created with the above member.  The arc is directed.  
		void arc( node& from, node& to)
		{	from._neighbors.push_back(iterator(&to));
		}

		iterator begin()const { return iterator(_vertices.begin());}
		iterator end ()const { return iterator(_vertices.end());}
		
		// Returns a depth first listing of the nodes of the graph from node gn.  
		vector< iterator > depthFirst(node& gn)
		{	vector<  iterator > result;
			unmark();
			depthFirst_aux(iterator(&gn), result);
			return result;
		}

		void archive(ostream& out)
		{	typedef pair<node *, node * > pr;
			typedef deque< pr > deq;
			deq arcs;
			
			for(iterator i = begin(); i != end(); ++i)
			{	out<< i->value<<endl;
				for(vector<node *>::iterator j = i->_neighbors.begin(); j != i->_neighbors.end(); ++j)
					arcs.push_back(pr( i, (*j)) );
			}
			while(! arcs.empty())
			{	pr p = arcs.front(); arcs.pop_front();
				out<<'('<<p.first->_index<<','<<p.second->_index<<')'<<endl;		
			}
		}
		
	private:
		vector< node > _vertices;
		
		void unmark()
		{	for(iterator i = begin(); i != end(); ++i)
				(*i).unmark();
		}
		
		void depthFirst_aux(iterator gi, vector< iterator >& A)
		{	if(! (*gi).marked())
			{	(*gi).mark();
				A.push_back(gi);
				for
				(	vector<iterator>::iterator i = gi->_neighbors.begin();
					i != gi->_neighbors.end();
					++i
				)
					depthFirst_aux(*i,A);
			}
		}
		
//	friend ostream& operator<<(ostream& os, const DiGraph<T>& g);

};

template <class T> // Requires T support operator<<.  
ostream& operator<<(ostream& os, const DiGraph<T>& g)
{	for(DiGraph<T>::iterator i = g.begin(); i!= g.end(); ++i)
		os<< (*i).value<<" ";
	return os;
}

#endif