Directed Acyclic Graphs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace DirectedAcyclicGraphs
{
    //class for representing a graph node
    public class GraphNode<T>
    {
        //class fields
        private T data;
        private List<GraphNode<T>> DependentNodes = new List<GraphNode<T>>();
        private List<GraphNode<T>> AntecedentNodes = new List<GraphNode<T>>();

        //class constructors
        //1). Constructor when just data is supplied
        public GraphNode(T data)
        {
            this.data = data;
            DependentNodes = new List<GraphNode<T>>();
            AntecedentNodes = new List<GraphNode<T>>();
        }
        //2). constructor when data and neighbours are supplied
        public GraphNode(T data, List<GraphNode<T>> Dependents, List<GraphNode<T>> Antecedents)
        {
            this.data = data;
            DependentNodes = Dependents ?? new List<GraphNode<T>>();
            AntecedentNodes = Antecedents ?? new List<GraphNode<T>>();
        }

        //properties
        public IEnumerable<GraphNode<T>> Dependents
        {
            get { return DependentNodes; }
        }
        public IEnumerable<GraphNode<T>> Antecedents
        {
            get { return AntecedentNodes; }
        }
        public T NodeData
        {
            get { return data; }
        }

        //methods to add and remove precedents / dependents
        public void AddDependent(GraphNode<T> NewDependent)
        {
            DependentNodes.Add(NewDependent);
            NewDependent.AddOnlyAntecedent(this);
        }
        private void AddOnlyDependent(GraphNode<T> NewDependent)
        {
            DependentNodes.Add(NewDependent); //no need to add antecedents -- this prevents an infinote recursive loop
        }
        public bool DeleteDependent(GraphNode<T> RemoveDependent)
        {
            return DependentNodes.Remove(RemoveDependent) && RemoveDependent.DeleteAntecedent(this);
        }
        public void AddAntecedent(GraphNode<T> NewAntecedent)
        {
            AntecedentNodes.Add(NewAntecedent);
            NewAntecedent.AddOnlyDependent(this);
        }
        private void AddOnlyAntecedent(GraphNode<T> NewAntecedent)
        {
            AntecedentNodes.Add(NewAntecedent); //no need to add dependents -- this prevents an infinote recursive loop
        }
        public bool DeleteAntecedent(GraphNode<T> RemoveAntecedent)
        {
            return AntecedentNodes.Remove(RemoveAntecedent) && RemoveAntecedent.DeleteDependent(this);
        }
        public GraphNode<T> CopyNodeData()
        {
            return new GraphNode<T>(this.data);
        }
    }

    //class for repsesenting a graph
    public class DirectedAcyclicGraph<T>
    {
        //class fields
        private Dictionary<GraphNode<T>, bool> GraphNodesStatus = new Dictionary<GraphNode<T>, bool>();
        private List<GraphNode<T>> GraphNodes = new List<GraphNode<T>>();
        private EqualityComparer<GraphNode<T>> GraphNodeEqualityComparer = EqualityComparer<GraphNode<T>>.Default;

        //class constructors
        public DirectedAcyclicGraph()
        {}
        public DirectedAcyclicGraph(EqualityComparer<GraphNode<T>> Comparer)
        {
            GraphNodeEqualityComparer = Comparer;
        }
        //single node graph construction
        public DirectedAcyclicGraph(GraphNode<T> starterNode) : this(starterNode, EqualityComparer<GraphNode<T>>.Default)
        {
        }
        public DirectedAcyclicGraph(GraphNode<T> starterNode, EqualityComparer<GraphNode<T>> Comparer)
        {
            GraphNodeEqualityComparer = Comparer;
            //we need to get the node's antecedent and pedents count multiple times in this method. So convert enumerable to list for direct access (constant time) to count of antecedents
            List<GraphNode<T>> Dependents = starterNode.Dependents.ToList(), Antecedents = starterNode.Antecedents.ToList();
            if (Antecedents.Count != 0 || Dependents.Count != 0)
            {
                throw new ArgumentException("The starter node " + starterNode.NodeData.ToString() + " has non-zero antecedents/deendents, which is invalid for a one node graph. It has " + Antecedents.Count + " antecedents and " + Dependents.Count + " dependents.");
            }
            GraphNodes.Add(starterNode);
            GraphNodesStatus.Add(starterNode, false);
        }
        //multiple node graph construction
        public DirectedAcyclicGraph(List<GraphNode<T>> Nodes) : this(Nodes, EqualityComparer<GraphNode<T>>.Default)
        {
        }
        public DirectedAcyclicGraph(List<GraphNode<T>> Nodes, EqualityComparer<GraphNode<T>> Comparer)
        {
            GraphNodeEqualityComparer = Comparer;
            //check for duplicates
            List<GraphNode<T>> DuplicateNodes = Nodes.GroupBy(x => x).Where(g => g.Count() > 1).Select(y => y.Key).ToList();
            if(DuplicateNodes.Count > 0)
            {
                throw new ArgumentException("There are "+ DuplicateNodes.Count +" duplicate nodes in the input list of nodes supplied for creating the graph --  " + string.Join(",", DuplicateNodes.Select(x => x.ToString()))  );
            }
            GraphNodes.AddRange(Nodes);
            Nodes.ForEach(x => GraphNodesStatus[x] = false);
            CheckGraphForCycles();
        }

        //methods
        //add node
        private void AddGraphNode(GraphNode<T> NewNode)
        {
            //check this is not present in the graph already
            if (GraphNodes.Contains(NewNode, GraphNodeEqualityComparer))
            {
                throw new ArgumentException("The node " + NewNode.NodeData.ToString() + " is already present in the graph, it cannot be added");
            }
            //Add it
            GraphNodes.Add(NewNode);
            GraphNodesStatus[NewNode] = false;
            CheckGraphForCycles();
            //make all the dependent nodes dirty
            UnvisitChildNodes(NewNode);
        }
        //check entire graph for cycles
        private void CheckGraphForCycles()
        {
            //check for cycles
            bool bCycleFound = false;
            List<GraphNode<T>> VerifiedNodes = new List<GraphNode<T>>();
            foreach (GraphNode<T> graphNode in GraphNodes)
            {
                Stack<GraphNode<T>> DependencyPath = new Stack<GraphNode<T>>();
                bCycleFound = CheckDependentsForCycle(graphNode, graphNode, DependencyPath, VerifiedNodes);
                if (bCycleFound)
                {
                    throw new ArgumentException("Cyclic dependency found in the following dependencies : " + string.Join("-*-", DependencyPath.Select(x => x.NodeData.ToString())));
                }
                else
                {
                    VerifiedNodes.Add(graphNode);
                }
            }
        }
        //checking for cyclic dependencies for individual node
        private bool CheckDependentsForCycle(GraphNode<T> StartGraphNode, GraphNode<T> CurrentGraphNode, Stack<GraphNode<T>> DependencyPath, List<GraphNode<T>> VerifiedNodes)
        {
            bool bCycleFound = false;
            DependencyPath.Push(CurrentGraphNode);
            if (CurrentGraphNode.Dependents.Contains(StartGraphNode, GraphNodeEqualityComparer))
            {
                bCycleFound = true;
            }
            else
            {
                foreach (GraphNode<T> CurrentDependent in CurrentGraphNode.Dependents.Where(x => !VerifiedNodes.Contains(x)))
                {
                    if (CheckDependentsForCycle(StartGraphNode, CurrentDependent, DependencyPath, VerifiedNodes))
                    {
                        bCycleFound = true;
                        break;
                    }
                }
                //if no cycle was found till this point then bCycleFound will always be false
                //pop the current dependent from the stack
                DependencyPath.Pop();
            }
            return bCycleFound;
        }
        //visit complete graph
        public void VisitFullGraphSingleAction(Action<GraphNode<T>> VisitingAction)
        {
            //mark all the nodes as unvisited
            GraphNodes.ForEach(x => GraphNodesStatus[x] = false);
            //get the nodes which have no dependents (i.e. starter nodes)
            List<GraphNode<T>> StarterNodes = GraphNodes.Where(x => !x.Antecedents.Any()).ToList();
            VisitStarterNodes(VisitingAction, StarterNodes);   //We need to wait via the waiting tasks -- which are just launching the first nodes of thre graph in parallel. Otherwise graph calculation will end in an instant
        }
        private void VisitStarterNodes(Action<GraphNode<T>> VisitingAction, List<GraphNode<T>> StarterNodes)
        {
            // launch the starter node tasks in parallel
            List<Task> WaitingTasks = new List<Task>();
            foreach (GraphNode<T> VisitingNode in StarterNodes)
            {
                //this will visit all the starter nodes asynchronously (i.e. in parallel)
                Task WaiterTask = Task.Run(() => VisitNodeSingleAction(VisitingNode, VisitingAction));
                WaitingTasks.Add(WaiterTask);
            }
            Task.WaitAll(WaitingTasks.ToArray());
        }
        //recursively visit a node and perform an action
        private void VisitNodeSingleAction(GraphNode<T> VisitingNode, Action<GraphNode<T>> VisitingAction)
        {
            //execute the Action for that node
            VisitingAction(VisitingNode);
            List<Task> WaitingTasks = new List<Task>();
            lock (this)
            {
                GraphNodesStatus[VisitingNode] = true;
                //VisitedNodes.Add(VisitingNode);
                //now get the list of valid dependent nodes to visit
                List <GraphNode<T>> ValidChildrenToVisit = VisitingNode.Dependents.Where(x => !GraphNodesStatus[x]).Where
                (x => x.Antecedents.ToList().TrueForAll(y => GraphNodesStatus[y])).ToList();
                // launch the valid dependent nodes in parallel (use a waiter task to exit the function only after all dependent nodes have finished execution)
                foreach (GraphNode<T> ValidChild in ValidChildrenToVisit)
                {
                    Task WaiterTask = Task.Run(() => VisitNodeSingleAction(ValidChild, VisitingAction));
                    WaitingTasks.Add(WaiterTask);
                }
            }
            Task.WaitAll(WaitingTasks.ToArray());   //Wait for the waiting tasks to complete -- i.e. the depent nodes complete executuon before leaving the function
        }
        //unvisit complete graph
        public void UnvisitFullGraph()
        {
            //mark all the nodes as unvisited
            GraphNodes.ForEach(x => GraphNodesStatus[x] = false);
        }
        //unvisit child nodes
        private void UnvisitChildNodes(GraphNode<T> UnvisitNode)
        {
            GraphNodesStatus[UnvisitNode] = false;
            foreach(GraphNode<T> DependentNode in UnvisitNode.Dependents)
            {
                UnvisitChildNodes(DependentNode);
            }
        }
        //visit the unvisited nodes (smart visiting)
        public void SmartVisitFullGraphSingleAction(Action<GraphNode<T>> VisitingAction)
        {
            //find out the nodes which are dirty
            IEnumerable<GraphNode<T>> NodesToVisit = GraphNodes.Where(Node => !GraphNodesStatus[Node]);
            //now find out which of them are starter nodes for calculations
            List<GraphNode<T>> StarterNodes = NodesToVisit.Where(DirtyNode => DirtyNode.Antecedents.All(y => GraphNodesStatus[y])).ToList();
            //now kick off calculation for all the starter nodes
            VisitStarterNodes(VisitingAction, StarterNodes);
        }
    }
}