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);
}
}
}
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);
}
}
}