mapservice.cs

This is a document about routing [a spatial analysis - network]

                        if (l2 < len)
                        {
                            t = n2;
                            len = l2;
                        }
                        if (l3 < len)
                        {
                            t = n3;
                            len = l3; 
                        }
                    }
                Draw(t, new Pen(Color.Violet));
                return t;
            }
        }
        #endregion

        #region dijkstra shortest path algorithm
        private Hashtable reach = new Hashtable();
        private Hashtable dist = new Hashtable();
        private Hashtable route = new Hashtable();
        private void InitDistRouteTables(string start)
        {           
            // set the initial distance and route for each city in the graph
            foreach (Node n in graph.Nodes)
            {
                dist[n.Key]=Int32.MaxValue;
                route[n.Key]=null;
            }

            // set the initial distance of start to 0
            dist[start]= 0;
        }
        private void Relax(string uCity, string vCity, int cost)
        {
            int distTouCity = (int)dist[uCity];
            int distTovCity = (int)dist[vCity];

            if (distTovCity > distTouCity + cost)
            {
                // update distance and route
                dist[vCity] = distTouCity + cost;
                route[vCity] = uCity;
                reach[vCity] = null;
            }
        }
        private string GetMin(Hashtable nodes)
        {
            // find the node in nodes with the smallest distance value
            int minDist = Int32.MaxValue;//Double.MaxValue;
            string minNode = "";
            foreach (string key in nodes.Keys)
            {
                if (((int)dist[key]) <= minDist)
                {
                    minDist = (int)dist[key];
                    minNode = key;
                }
            }

            return minNode;
        }
        public int  GetShortestPath(Node start, Node end)
        {           
            //add temporaty nodes to graph
            int len=-1;
            EdgeToNeighbor edge1=null,edge2=null;
            Node start0 = SnapEdge(start);
            Node end0 = SnapEdge(end);
            if (start0.Data != null)
            {
                graph.AddNode(start0);
                edge1 = (EdgeToNeighbor)start0.Data;
            }
            if (end0.Data != null)
            {
                graph.AddNode(end0);
                edge2 = (EdgeToNeighbor)end0.Data;
            }
            if (edge1 != null || edge2 != null)
            {
                if (edge1 == edge2) //same edge
                {
                    Node p1 = edge1.Source;
                    Node p2 = edge1.Neighbor;
                    if (Common.Len(p1, start0) < Common.Len(p1, end0))
                    {
                        graph.AddEdge(p1, start0, edge1.IsTwoWay);
                        graph.AddEdge(start0, end0, edge1.IsTwoWay);
                        graph.AddEdge(end0, p2, edge1.IsTwoWay);
                    }
                    else
                    {
                        graph.AddEdge(p1, end0, edge1.IsTwoWay);
                        graph.AddEdge(end0, start0, edge1.IsTwoWay);
                        graph.AddEdge(start0, p2, edge1.IsTwoWay);
                    }
                }
                else
                {
                    if (edge1 != null)
                    {
                        Node p1 = edge1.Source;
                        Node p2 = edge1.Neighbor;
                        graph.AddEdge(p1, start0, edge1.IsTwoWay);
                        graph.AddEdge(start0, p2, edge1.IsTwoWay);
                    }
                    if (edge2 != null)
                    {
                        Node p1 = edge2.Source;
                        Node p2 = edge2.Neighbor;
                        graph.AddEdge(p1, end0, edge2.IsTwoWay);
                        graph.AddEdge(end0, p2, edge2.IsTwoWay);
                    }
                }
            }
            
            InitDistRouteTables(start0.Key);		// initialize the route & distance tables

            string u = start0.Key;
            reach[u]=null;
            do
            {
                u = GetMin(reach);
                foreach (EdgeToNeighbor edge in graph.Nodes[u].Neighbors)
                    Relax(u, edge.Neighbor.Key, edge.Cost);		// relax each edge                
                reach.Remove(u);			// remove it from the set Q
            }	
            while (reach.Count > 0 && u != end0.Key);

            Pen pen = new Pen(Color.Red);
            Draw(start, start0, pen);
            Draw(end, end0, pen);
            Draw(start0, new Pen(Color.Blue));
            Draw(end0, new Pen(Color.Yellow));
            if (route[end0.Key] != null)
            {
                Node n1 = null;
                Node n2 = graph.Nodes[end0.Key];
                while (n2.Key != start0.Key)
                {
                    n1 = n2;
                    n2 = graph.Nodes[(string)route[n2.Key]];
                    if (n1 != null && n2 != null)
                        Draw(n1, n2, pen);
                }                
                len = (int)dist[end0.Key];
            }

            //remove temporaty nodes to graph
            if (edge1 != null)
            {
                edge1.Source.Neighbors.Remove(start0);
                edge1.Neighbor.Neighbors.Remove(start0);
                graph.Remove(start0);
            }
            if (edge2 != null)
            {
                edge2.Source.Neighbors.Remove(end0);
                edge2.Neighbor.Neighbors.Remove(end0);
                graph.Remove(end0);
            }

            return len;
        }
        #endregion

        #region geocoding     
        public Node GeoCode(int number, string name)
        {
            name = name.ToUpper();
            if (roads.ContainsKey(name))
            {
                Road road = (Road)roads[name];
                for (int i = 0; i < road.Segments.Count; i++)
                {
                    Segment segment = (Segment)road.Segments[i];
                    if ((number + segment.FromLeft) % 2 == 0 &&
                            segment.FromLeft <= number && number <= segment.ToLeft)
                        return GeoCode(segment, (int)((number - segment.FromLeft + 1) * 
                            segment.Len / (segment.ToLeft - segment.FromLeft + 2)));
                    else if ((number + segment.FromRight) % 2 == 0 &&
                            segment.FromRight <= number && number <= segment.ToRight)
                        return GeoCode(segment, (int)((number - segment.FromRight + 1) * 
                            segment.Len / (segment.ToRight - segment.FromRight + 2)));
                }
            }
            return null;
        }

        private Node GeoCode(Segment segment, int d)
        {
            int d1=0;
            int d2=0;
            for(int i=0; i<segment.Nodes.Count-1;i++)
            {
                Node n1=(Node)segment.Nodes[i];
                Node n2=(Node)segment.Nodes[i+1];
                d2=d1+Common.Len(n1,n2);
                if(d1<=d && d<=d2)
                {
                    Node n = Common.GetNode(n1, n2, d - d1, d2 - d);
                    Draw(n, new Pen(Color.Cyan));
                    return n;
                }
                d1 = d2;
            }
            return null;
        }
        #endregion
    }
}