tbf/SchematicDrawing/Graph.cs

///
/// Copyright (c) 2020 Sensus Slovensko a.s.
///
using System;
using System.Diagnostics;
using System.Collections.Generic;

namespace SchematicDrawing
{
    public class Graph
    {
        public bool Completed;

        IList<GNode> nodes;
        GNode startNode;
        int secondaryStartNodesCount;

        MinHeap minHeap;
        GNode currentNode;

        public Graph()
        {
            nodes = new List<GNode>();
            startNode = null;
            secondaryStartNodesCount = 0;
            minHeap = new MinHeap();
            Completed = false;
        }

        public void Clear()
        {
            nodes.Clear();
            startNode = null;
            secondaryStartNodesCount = 0;
            Completed = false;
        }

        /// <summary>
        /// Add a node to the list of graph nodes
        /// </summary>
        /// <param name="node">Graph node</param>
        public void AddNode(GNode node, bool isStartNode = false, bool isSecondaryStartNode = false)
        {
            if (isStartNode && startNode == null)
            {
                startNode = node;
                nodes.Insert(0, node);
            }
            else if (isStartNode || isSecondaryStartNode)
            {
                secondaryStartNodesCount++;
                nodes.Insert(startNode != null ? 1 : 0, node);
            }
            else
            {
                nodes.Add(node);
            }
        }

        /// <summary>
        /// Add an edge to the list of edges of node1.
        /// </summary>
        /// <param name="node1">Node 1 (start)</param>
        /// <param name="node2">NOde 2 (end)</param>
        /// <param name="defaultDist">Default distance (when closed)</param>
        /// <param name="routeCouple">Way the route affects this edge</param>
        /// <returns>Added graph edge</returns>
        public GEdge AddEdge(GNode node1, GNode node2, int defaultDist, RouteCouple routeCouple = RouteCouple.None)
        {
            GEdge gedge = new GEdge(node1, node2, defaultDist, routeCouple);
            node1.AddEdge(gedge);
            return gedge;
        }

        /// <summary>
        /// Run Dijkstra shortest path algorithm to determine schematic drawing coloring
        /// </summary>
        public void RunDijkstraAlgo()
        {
            if (nodes == null || startNode == null) return;

            /// Reset all nodes
            minHeap.ResetAndBuild(nodes, secondaryStartNodesCount);

            currentNode = minHeap.ExtractMinNode();
            do
            {
                /// Consider all unvisited neighbors of the current node
                foreach (var e in currentNode.Edges)
                {
                    int distViaCurrNode = (e.Dist == int.MaxValue) ? int.MaxValue : currentNode.Dist + e.Dist;
                    if (distViaCurrNode < e.EndNode.Dist)
                    {
                        e.EndNode.Dist = distViaCurrNode;
                        minHeap.SiftUp(e.EndNode.HeapIx);
                    }
                }

                currentNode = minHeap.ExtractMinNode();
            }
            while (currentNode.Dist < int.MaxValue && currentNode != null);
        }
    }
}