using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Marvin.Examples.Dijkstra___Manhattan { public class Subgraph { public Subgraph(TNode node, IEnumerable>> graph) : this(node,new Graph(graph)){ } private Subgraph(TNode node, Graph graph) { this.node = node; this.graph = graph; this.graph.UpdateDistance(node,0.0); } role graph : Graph { double DistanceBetween(TNode node, TNode other){ return self.Nodes[node][other]; } void RemoveNode(){ graph.Nodes.Remove(node); } void UpdateDistance(TNode n,double distance){ self.Distances[n] = distance; } } role node : TNode { IDictionary Neighbors(){ return graph.Nodes[self]; } double Distance(){ return graph.Distances[self]; } void IsPreviousOf(TNode n){ if(!graph.Previous.ContainsKey(n)){ graph.Previous.Add(n,default(TNode)); } graph.Previous[n] = self; } double DistanceTo(TNode other){ return graph.DistanceBetween(self,other); } TNode NeighborWithShortestPath(){ return graph.Distances.Where(n=> graph.Nodes.ContainsKey(n.Key)) .OrderBy(n => n.Value).FirstOrDefault().Key; } } interaction Dictionary FindShortestPath() { var neighbors = node.Neighbors().Keys; if(!neighbors.Any()) return graph.Previous; foreach(var v in neighbors) { var alt = node.Distance() + node.DistanceTo(v); if(alt < graph.Distances[v]) { graph.UpdateDistance(v,alt); node.IsPreviousOf(v); } } graph.RemoveNode(); var u = node.NeighborWithShortestPath(); new Subgraph(u, graph).FindShortestPath(); return graph.Previous; } class Graph { private readonly Dictionary _dist = new Dictionary(); private readonly Dictionary _previous = new Dictionary(); public Graph(IEnumerable>> graph){ this.nodes = (graph as IDictionary>); if(this.nodes == null){ this.nodes = new Dictionary>(); foreach(var pair in nodes) { this.nodes.Add(pair.Key,pair.Value); } } foreach(var node in nodes.Keys){ _dist.Add(node,double.PositiveInfinity); } } role nodes : IDictionary> { } public IDictionary> Nodes{ get { return nodes;} } public Dictionary Distances{ get{ return _dist;} } public Dictionary Previous{ get{ return _previous;} } } } }