FatTree.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using QuickGraph;
using QuickGraph.Algorithms;
using QuickGraph.Algorithms.RankedShortestPath;
using QuickGraph.Graphviz;
using tree;

namespace tree
{
    public class Node
    {
        private static int globalIds = 0;
        private static int GetNextId()
        {
            globalIds += 1;
            return globalIds;
        }
        public static Dictionary<int, Node> Nodes = new Dictionary<int, Node>();

        public int id;
        public int level;
        public int number;
        public string name;
        public Node(int level, int number, string name)
        {
            this.level = level;
            this.number = number;
            id = GetNextId();
            this.name = name;
            Nodes.Add(id, this);
        }

        public override string ToString()
        {
            return $"{name} l:{level} n:{number}";
        }
    }

    public class FatTree
    {
        public BidirectionalGraph<Node, Edge<Node>> graph =
            new BidirectionalGraph<Node, Edge<Node>>();

        public List<Node> CoreSwitchList = new List<Node>();
        public List<Node> AggSwitchList = new List<Node>();
        public List<Node> EdgeSwitchList = new List<Node>();
        public List<Node> HostList = new List<Node>();
        private int _iAggLayerSwitch;
        private int _iEdgeLayerSwitch;
        private int _iHost;
        private int _iCoreLayerSwitch;

        public FatTree(int k, int density)
        {
            var pod = k;
            _iCoreLayerSwitch = (int)Math.Pow((k / 2), 2);
            _iAggLayerSwitch = k * k / 2;
            _iEdgeLayerSwitch = k * k / 2;
            _iHost = _iEdgeLayerSwitch * density;

            addNodes(_iCoreLayerSwitch, 1, CoreSwitchList, "core");
            addNodes(_iAggLayerSwitch, 2, AggSwitchList, "aggr");
            addNodes(_iEdgeLayerSwitch, 3, EdgeSwitchList, "edge");
            addNodes(_iHost, 4, HostList, "host");
            createLinks(pod, density);
        }

        private void addNodes(int number, int level, List<Node> switch_list, string name)
        {
            for (int x = 0; x < number; x++)
            {
                var node = new Node(level, x, name);
                switch_list.Add(node);
                graph.AddVertex(node);
            }

        }

        private void createLinks(int pod, int density)
        {
            int end = pod / 2;
            for (int x = 0; x < _iAggLayerSwitch; x += end)
            {
                for (int i = 0; i < end; i++)
                {
                    for (int j = 0; j < end; j++)
                    {
                        var core_ind = i * end + j;
                        var agg_ind = x + i;
                        addLink(
                            CoreSwitchList[core_ind],
                            AggSwitchList[agg_ind]);

                    }

                }
            }
            for (int x = 0; x < _iAggLayerSwitch; x += end)
            {
                for (int i = 0; i < end; i++)
                {
                    for (int j = 0; j < end; j++)
                    {
                        addLink(
                            AggSwitchList[x + i],
                            EdgeSwitchList[x + j]);
                    }

                }
            }
            for (int x = 0; x < _iEdgeLayerSwitch; x += 1)
            {
                for (int i = 0; i < density; i++)
                {
                    addLink(
                        EdgeSwitchList[x],
                        HostList[density * x + i]);
                }
            }
        }

        private void addLink(Node a, Node b)
        {
            graph.AddEdge(new Edge<Node>(a, b));
            graph.AddEdge(new Edge<Node>(b, a));

        }

        public void Draw()
        {
            var graphViz = new GraphvizAlgorithm<Node, Edge<Node>>(graph,
                @".\", QuickGraph.Graphviz.Dot.GraphvizImageType.Png);

            graphViz.FormatVertex += (sender, args) => FormatVertex(sender, args);
            //graphViz.FormatEdge += FormatEdge;

            graphViz.Generate(new FileDotEngine(), "figure");

            Console.ReadKey();

        }

        private static void FormatVertex(object sender, FormatVertexEventArgs<Node> e)
        {
            e.VertexFormatter.Label = $"{e.Vertex}";
        }
        private static void FormatEdge(object sender, FormatEdgeEventArgs<Node, Edge<Node>> e)
        {
            e.EdgeFormatter.Head.Label = $"{e.Edge.Target}";  
            e.EdgeFormatter.Tail.Label = $"{e.Edge.Source}"; 
        }
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            var t = new FatTree(4, 4);
            var test1 =
                new HoffmanPavleyRankedShortestPathAlgorithm<Node, Edge<Node>>(t.graph, E => 1.0);

            test1.ShortestPathCount = 5;
            test1.SetRootVertex(t.HostList.First());
            

            test1.Compute(t.HostList.First(), t.HostList.Last());
            Console.WriteLine("Paths Found = " + test1.ComputedShortestPathCount);
            foreach (var path in test1.ComputedShortestPaths)
            {
                Console.WriteLine("Path price: " + path.Count());
                foreach (var edge in path)
                {
                    Console.WriteLine(
                        $"From {edge.Source}  -> To {edge.Target} ");
                }
            }
            t.Draw();
            Console.ReadLine();
        }
    }
}