fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public class Test {
  6.     public static void Main()
  7.     {
  8.         var graph = GenerateGraph(50, 0.4);
  9.         var source = graph.Nodes.First();
  10.  
  11.         Console.WriteLine("Nodes: {0}, Edges: {1}", graph.NodeCount, graph.EdgeCount);
  12.  
  13.         BellmanFord(graph, source);
  14.  
  15.         BellmanFordQueue(graph, source);
  16.     }
  17.  
  18.     private static IEnumerable<PathFindNode> BellmanFord(Graph graph, Node origin)
  19.     {
  20.         var nodes = new Dictionary<Node, PathFindNode>();
  21.  
  22.         foreach (var node in graph.Nodes)
  23.         {
  24.             var pfNode = new PathFindNode(node, null, double.PositiveInfinity);
  25.             if (node == origin) pfNode.Distance = 0;
  26.             nodes[node] = pfNode;
  27.         }
  28.  
  29.         int checks = 0;
  30.         int relaxes = 0;
  31.         foreach (var node in graph.Nodes)
  32.         {
  33.             foreach (var edge in graph.Edges)
  34.             {
  35.                 checks++;
  36.                 var source = nodes[edge.Source];
  37.                 var destination = nodes[edge.Destination];
  38.                 if (source.Distance + edge.Weight < destination.Distance)
  39.                 {
  40.                     relaxes++;
  41.                     destination.Distance = source.Distance + edge.Weight;
  42.                     destination.Predecessor = source;
  43.                 }
  44.             }
  45.         }
  46.         Console.WriteLine("BF original: {0} checks, {1} relaxes", checks, relaxes);
  47.  
  48.         foreach (var edge in graph.Edges)
  49.         {
  50.             var source = nodes[edge.Source];
  51.             var destination = nodes[edge.Destination];
  52.             if (source.Distance + edge.Weight < destination.Distance)
  53.             {
  54.                 throw new Exception("Graph contains a negative-weight cycle");
  55.             }
  56.         }
  57.  
  58.         return nodes.Values
  59.             .OrderBy(pfn => pfn.Node.Index)
  60.             .AsEnumerable();
  61.     }
  62.  
  63.  
  64.     private static IEnumerable<PathFindNode> BellmanFordQueue(Graph graph, Node source)
  65.     {
  66.         var nodes = new Dictionary<Node, PathFindNode>();
  67.  
  68.         foreach (var node in graph.Nodes)
  69.         {
  70.             var pfNode = new PathFindNode(node, null, double.PositiveInfinity);
  71.             if (node == source) pfNode.Distance = 0;
  72.             nodes[node] = pfNode;
  73.         }
  74.  
  75.         var active = new Queue<PathFindNode>();
  76.         active.Enqueue(nodes[source]);
  77.  
  78.         int checks = 0;
  79.         int relaxes = 0;
  80.         while (active.Count > 0)
  81.         {
  82.             var node = active.Dequeue();
  83.             foreach (var edge in node.Node.Edges)
  84.             {
  85.                 checks++;
  86.                 var destination = nodes[edge.Destination];
  87.                 if (node.Distance + edge.Weight < destination.Distance)
  88.                 {
  89.                     relaxes++;
  90.                     destination.Distance = node.Distance + edge.Weight;
  91.                     destination.Predecessor = node;
  92.                     active.Enqueue(destination);
  93.                 }
  94.             }
  95.         }
  96.         Console.WriteLine("BF with queue: {0} checks, {1} relaxes", checks, relaxes);
  97.  
  98.         // Checking for negative-weight cycles does not make sense, since they would
  99.         // pull the algorithm into an infinite loop. 
  100.  
  101.         return nodes.Values
  102.             .OrderBy(pfn => pfn.Node.Index)
  103.             .AsEnumerable();
  104.     }
  105.  
  106.     private static Random _rnd = new Random();
  107.     private static Graph GenerateGraph(int nodeCount, double edgeProbability)
  108.     {
  109.         var graph = new Graph();
  110.         var nodes = Enumerable.Range(0, nodeCount).Select(_ => graph.AddNode()).ToList();
  111.  
  112.         for (int i = 0; i < nodeCount; i++)
  113.         for (int j = i + 1; j < nodeCount; j++)
  114.         if (_rnd.NextDouble() < edgeProbability)
  115.         {
  116.             nodes[i].Add(nodes[j], 1 + 99*_rnd.NextDouble());
  117.         }
  118.  
  119.         return graph;
  120.     }
  121. }
  122.  
  123. public class PathFindNode
  124. {
  125.     public Node Node { get; private set; }
  126.     public PathFindNode Predecessor { get; set; }
  127.     public double Distance { get; set; }
  128.  
  129.     public PathFindNode(Node node, PathFindNode predecessor = null, double distance = 0)
  130.     {
  131.         Node = node;
  132.         Predecessor = predecessor;
  133.         Distance = distance;
  134.     }
  135. }
  136.  
  137. public class Graph
  138. {
  139.     private SortedList<int, Edge> _edges = new SortedList<int, Edge>();
  140.     public IEnumerable<Edge> Edges { get { return _edges.Values.AsEnumerable(); } }
  141.     public int EdgeCount { get { return _edges.Count; } }
  142.  
  143.     private SortedList<int, Node> _nodes = new SortedList<int, Node>();
  144.     public IEnumerable<Node> Nodes { get { return _nodes.Values.AsEnumerable(); } }
  145.     public int NodeCount { get { return _nodes.Count; } }
  146.  
  147.     public Node AddNode()
  148.     {
  149.         var node = new Node(this);
  150.         _nodes[node.Index] = node;
  151.         return node;
  152.     }
  153.  
  154.     public Edge AddEdge(Node n1, Node n2, double weight)
  155.     {
  156.         if (n1.Graph != this || n2.Graph != this || n1 == n2) throw new Exception();
  157.         var edge = new Edge(this, n1, n2, weight);
  158.         _edges[edge.Index] = edge;
  159.         n1.Add(edge);
  160.         return  edge;
  161.     }
  162. }
  163.  
  164. public class Edge : IEquatable<Edge>
  165. {
  166.     private static int _indexCounter = 0;
  167.  
  168.     public int Index { get; private set; }
  169.     public Graph Graph { get; private set; }
  170.     public Node Source { get; private set; }
  171.     public Node Destination { get; private set; }
  172.     public double Weight { get; private set; }
  173.  
  174.     public Edge(Graph graph, Node source, Node destination, double weight)
  175.     {
  176.         Index = _indexCounter++;
  177.         Graph = graph;
  178.         Source = source;
  179.         Destination = destination;
  180.         Weight = weight;
  181.     }
  182.  
  183.     public bool Equals(Edge other)
  184.     {
  185.         return other != null && Index == other.Index;
  186.     }
  187.  
  188.     public override bool Equals(object other)
  189.     {
  190.         return Equals(other as Edge);
  191.     }
  192.  
  193.     public override int GetHashCode()
  194.     {
  195.         return Index;
  196.     }
  197. }
  198.  
  199. public class Node : IEquatable<Node>
  200. {
  201.     private static int _indexCounter = 0;
  202.     public int Index { get; private set; }
  203.  
  204.     private SortedList<int, Edge> _edges = new SortedList<int, Edge>();
  205.     public IEnumerable<Edge> Edges { get { return _edges.Values.AsEnumerable(); } }
  206.  
  207.     public Graph Graph { get; private set; }
  208.  
  209.     public Node(Graph graph)
  210.     {
  211.         Index = _indexCounter++;
  212.         Graph = graph;
  213.     }
  214.  
  215.     public void Add(Edge edge)
  216.     {
  217.         if (edge.Source != this || edge.Graph != Graph) throw new ArgumentException("edge");
  218.         _edges[edge.Destination.Index] = edge;
  219.     }
  220.  
  221.     public Edge Add(Node node, double weight)
  222.     {
  223.         return Graph.AddEdge(this, node, weight);
  224.     }
  225.  
  226.     public bool IsConnectedTo(Node other)
  227.     {
  228.         return _edges.ContainsKey(other.Index);
  229.     }
  230.  
  231.     public bool Equals(Node other)
  232.     {
  233.         return other != null && Index == other.Index;
  234.     }
  235.  
  236.     public override bool Equals(object other)
  237.     {
  238.         return Equals(other as Node);
  239.     }
  240.  
  241.     public override int GetHashCode()
  242.     {
  243.         return Index;
  244.     }
  245. }
  246.  
Success #stdin #stdout 0.07s 34344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Nodes: 50, Edges: 495
BF original: 24750 checks, 101 relaxes
BF with queue: 678 checks, 82 relaxes
https://ideone.com/qwp2zP
Bellman-Ford algorithm - http://stackoverflow.com/q/16743927/
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!