/*
 * Copyright (c) 2005-2006 Erik Tigerholm <eriktigerholm@gmail.com>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
using System;
using System.Collections.Generic;
using System.Text;

namespace OpenTraffic.Model.Graph
{
    public class FindTrees<TV, TE>
        where TV : Vertex
        where TE : GraphEdge<TV>
    {
        private Graph<TV, TE> graph;

        public FindTrees(Graph<TV, TE> graph)
        {
            this.graph = graph;
        }

        public Dictionary<int, int> Run()
        {
            int npart = 0;
            Dictionary<int, int> part = new Dictionary<int, int>();
            Dictionary<TV, bool> notVisited = new Dictionary<TV, bool>();
            foreach (TV v in graph.Nodes)
            {
                notVisited.Add(v, true);
            }
            while (notVisited.Count != 0)
            {
                List<TV> lists = new List<TV>();
                IEnumerator<KeyValuePair<TV, bool>> e = notVisited.GetEnumerator();
                e.MoveNext();
                TV i = e.Current.Key;
                lists.Add(i);
                notVisited.Remove(i);
                npart++;
                while (lists.Count != 0)
                {
                    TV j = lists[0];
                    lists.RemoveAt(0);
                    part.Add(j.Id, npart);
                    foreach (TE edge in graph.AdjLinks[j])
                    {
                        if (notVisited.ContainsKey(edge.Target))
                        {
                            lists.Add(edge.Target);
                            notVisited.Remove(edge.Target);
                        }

                    } 
                    foreach (TE edge in graph.RevAdjLinks[j])
                    {
                        if (notVisited.ContainsKey(edge.Source))
                        {
                            lists.Add(edge.Source);
                            notVisited.Remove(edge.Source);
                        }

                    }
     
                }
            }
            return part;
        }
    }
}