using System;
using System.Collections.Generic;
using System.Text;

namespace GraphTest
{
	public delegate bool VertexMapper<T> (T left, T right);
	public delegate K VertexKeyer<T, K> (T data);
	
	public class DirectedGraph<T, K>
	{
		Dictionary<K, Vertex<T>> vertices;
		Dictionary<K, Dictionary<K, int>> edges;
		
		VertexMapper<T> mapFun;
		VertexKeyer<T, K> keyFun;
		
		public DirectedGraph(VertexMapper<T> mapFun, VertexKeyer<T, K> hashFun)
		{
			vertices = new Dictionary<K, Vertex<T>>();
			edges=new Dictionary<K,Dictionary<K,int>>();
			this.mapFun=mapFun;
			this.keyFun=hashFun;
		}
		
		public void addVertex (T obj)
		{
			Vertex<T> newV=new Vertex<T>(obj);
			foreach (Vertex<T> v in vertices.Values)
			{
				if (mapFun(obj, v.Data))
					addEdge(newV, v);
				if (mapFun(v.Data, obj))
					addEdge(v, newV);
			}
			vertices[keyFun(newV.Data)]=newV;
		}
		
		public void removeVertex (T obj)
		{
			K k=keyFun(obj);
			vertices.Remove(k);
			edges.Remove(k);
		}
		
		public T[] getAdjacent (T obj)
		{
			K leftKey=keyFun(obj);
			T[] result=new T[edges[leftKey].Keys.Count];
			int counter=0;
			foreach (K rightKey in edges[leftKey].Keys)
			{
				result[counter]=vertices[rightKey].Data;
				counter++;
			}
			return result;
		}

		public IEnumerable<T> adjacent(T obj)
		{
			K leftKey = keyFun(obj);
			foreach (K rightKey in edges[leftKey].Keys)
				yield return vertices[rightKey].Data;
		}

		public IEnumerable<T> leafDescendants(T obj)
		{
			K leftKey = keyFun(obj);
			Queue<K> fringe = new Queue<K>();
			foreach (K key in edges[leftKey].Keys)
				fringe.Enqueue(key);
			while (fringe.Count > 0)
			{
				K key = fringe.Dequeue();
				if (edges.ContainsKey(key))
					foreach (K dK in edges[key].Keys)
						fringe.Enqueue(dK);
				else
					yield return vertices[key].Data;
			}
		}

		public IEnumerable<T> allDescendants(T obj)
		{
			K leftKey = keyFun(obj);
			Queue<K> fringe = new Queue<K>();
			foreach (K key in edges[leftKey].Keys)
				fringe.Enqueue(key);
			while (fringe.Count > 0)
			{
				K key = fringe.Dequeue();
				if (edges.ContainsKey(key))
					foreach (K dK in edges[key].Keys)
						fringe.Enqueue(dK);
				yield return vertices[key].Data;
			}
		}
		
		private void addEdge (Vertex<T> left, Vertex<T> right)
		{
			K hLeft=keyFun(left.Data);
			K hRight=keyFun(right.Data);
			if (!edges.ContainsKey(hLeft))
				edges[hLeft]=new Dictionary<K, int>();
			edges[hLeft][hRight]=1;
		}
		
		private void addEdge (Vertex<T> left, Vertex<T> right, int weight)
		{
			K hLeft=keyFun(left.Data);
			K hRight=keyFun(right.Data);
			if (!edges.ContainsKey(hLeft))
				edges[hLeft]=new Dictionary<K, int>();
			edges[hLeft][hRight]=weight;
		}
	}
	
	class Vertex<T>
	{
		T data;
		
		public Vertex(T data)
		{
			this.data=data;
		}
		
		public T Data
		{
			get {return data;}
		}
	}
	
	struct Edge<T>
	{
		Vertex<T> left, right;
		
		public Edge(Vertex<T> left, Vertex<T> right)
		{
			this.left=left;
			this.right=right;
		}
	}
}

/*	public delegate bool VertexMapper<T> (T left, T right);
	
	public class DAG<T>
	{
		List<Vertex<T>> vertices;
		List<Edge<T>> edges;
		
		VertexMapper<T> mapFun;
		
		public DAG(VertexMapper<T> mapFun)
		{
			vertices=new List<Vertex<T>>();
			edges=new List<Edge<T>>();
			this.mapFun=mapFun;
		}
		
		public void addVertex (T obj)
		{
			Vertex<T> newV=new Vertex<T>(obj);
			foreach (Vertex<T> v in vertices)
			{
				if (mapFun(obj, v.Data))
					edges.Add(new Edge<T>(newV, v));
				if (mapFun(v.Data, obj))
					edges.Add(new Edge<T>(v, newV));
			}
			vertices.Add(newV);
		}
		
		public void 
	}
	
	class Vertex<T>
	{
		T data;
		
		public Vertex(T data)
		{
			this.data=data;
		}
		
		public T Data
		{
			get {return data;}
		}
	}
	
	struct Edge<T>
	{
		Vertex<T> left, right;
		
		public Edge(Vertex<T> left, Vertex<T> right)
		{
			this.left=left;
			this.right=right;
		}
	}*/