Shortest part in a string with Dijkstra algo

Jul 20, 2010 at 6:55 PM

Does anyone know how to save or get the complete path for the root vertex using this dijstra algo.

I have the following code:

 

    class NewDijkstra
    {


        string nodeTable, edgeTable;
        String[] nodes;
        String[] edges;

        DataSQL ds = new DataSQL();
        DataTable dt;
        DataTable hn;
        private List<Node> nodeList;
        public List<Node> QNodeList;
        private List<Node> ListofNeighbors;
        public string homeNode;
        public Edge<string>[] edge = null;
        AdjacencyGraph<string, Edge<string>> graph;
        Dictionary<Edge<string>, double> edgeCost;
        DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra;
        QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver;
        VertexDistanceRecorderObserver<string, Edge<string>> distObserver;


        public NewDijkstra(String nodeTable, String edgeTable)
        {
            this.nodeTable = nodeTable;
            this.edgeTable = edgeTable;
            getAllNodes();
            graph = new AdjacencyGraph<string, Edge<string>>(true);
            setUpDikjstra();

            getAllEdges();

            dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));

            // Attach a Vertex Predecessor Recorder Observer to give us the paths
            predecessorObserver = new QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>>();
            predecessorObserver.Attach(dijkstra);

            // attach a distance observer to give us the shortest path distances
            distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
            distObserver.Attach(dijkstra);

            homeNode = nodes[0];

            // Run the algorithm with A set to be the source
            dijkstra.Compute(homeNode);

            foreach (KeyValuePair<string, Edge<string>> kvp in predecessorObserver.VertexPredecessors)
            {
                Console.WriteLine("If you want to get to {0} you have to enter through the in edge {1}", kvp.Key, kvp.Value);


            }

            foreach (KeyValuePair<string, double> kvp in distObserver.Distances)
                Console.WriteLine("Distance from root to node {0} is {1}", kvp.Key, kvp.Value);

            //This is where i want to save the complete path to each node in a string of arrays 


        }


        private void setUpDikjstra()
        {


            foreach (String str in nodes)
            {
                graph.AddVertex(str);
            }


        }








        private void setUpListOfNodes()
        {
            //set up list of nodes  
            hn = ds.sqlQuery("SELECT nodeName FROM " + nodeTable + " WHERE TYPE='home'");
            DataRow homeRow = hn.Rows[0];
            homeNode = homeRow[0].ToString().Trim();


            nodeList.Add(new Node(homeNode, 0, null, true));

            for (int i = 0; i < nodes.Length; i++)
            {
                if (nodes[i] == homeNode)
                    continue;


                nodeList.Add(new Node(nodes[i], 2147483647, null));
            }
        }
        private void getAllEdges()
        {
            dt = ds.sqlQuery("SELECT * FROM " + edgeTable + " ORDER BY ID");

            int k = 0;
            edge = new Edge<string>[dt.Rows.Count];
            foreach (DataRow dr in dt.Rows)
            {

                // edge[k] = dr["id"].ToString().Trim();

                edge[k] = new Edge<string>(dr["source"].ToString().Trim(), dr["target"].ToString().Trim());
                k++;
            }

            foreach (Edge<string> addEdge in edge)
            {
                graph.AddEdge(addEdge);
            }

            edgeCost = new Dictionary<Edge<string>, double>(graph.EdgeCount);

            foreach (Edge<string> addEdge in edge)
            {
                edgeCost.Add(addEdge, 1);

            }

        }
        private void getAllNodes()
        {

            dt = ds.sqlQuery("SELECT * FROM " + nodeTable + " ORDER BY ID");
            nodes = new String[dt.Rows.Count];
            int k = 0;
            foreach (DataRow dr in dt.Rows)
            {
                //Console.WriteLine(k);
                nodes[k] = dr["nodeName"].ToString().Trim();
                Console.WriteLine("node# " +  k + "_: "+nodes[k]);
                k++;
            }
        }


    }