AdjacencyGraph & AlgorithmExtensions.Roots

Topics: bug, graph
Nov 26, 2009 at 12:37 PM

Hello,

I'm creating an AdjacencyGraph and using the AlgorithmExtensions.Roots method to try to find all of the "exit-only" nodes.  Looking through the code a bit, this seems to be what the algorithm is intended for.  However, given a graph, {A->B,B->C}, I would expect Roots to return A, and I'm getting an empty list.  If this is an API misunderstanding on my part, appoligies for the bother.  Here's the code I'm using:

        static void Main(string[] args)
        {
            AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(false);
            graph.AddVertex("A");
            graph.AddVertex("B");
            graph.AddVertex("C");

            graph.AddEdge(new Edge<string>("A", "B"));
            graph.AddEdge(new Edge<string>("B", "C"));

            var roots = graph.Roots();

            Console.WriteLine("Roots:");
            foreach (string vertex in roots)
            {
                Console.WriteLine("\t" + vertex);
            }
            Console.WriteLine("End Roots");

            var topologicalSort = AlgorithmExtensions.TopologicalSort<string, Edge<string>>(graph);
            Console.WriteLine("Topological (nmake) Sort Order:");
            foreach(string vertex in topologicalSort)
            {
                Console.WriteLine("\t" + vertex);
            }
            Console.WriteLine("End Topological Sort");

            Console.WriteLine("Press any key to exit.");
            Console.ReadKey();
        }

Thanks for your time!

Rich

Coordinator
Nov 29, 2009 at 12:43 AM

Thanks for the repro, I will investigate.

 

Coordinator
Nov 29, 2009 at 3:55 AM

There was a bug in the roots implementation. I've checked in a fix.

Coordinator
Nov 29, 2009 at 3:55 AM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
Nov 29, 2009 at 10:14 AM

Thanks for the quick investigation and turn around on this Peli - I really appreciate it!

Cheers,

Rich