using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace MyCodeSnippets.CodingInterview.Chapter4_Trees
{
[TestClass]
public class Task_4_2_CheckIfNodesConnected
{
[TestMethod]
public void IsNodesConnectedTest()
{
var node1 = new DirectedGraphNode<int>(1);
var node2 = new DirectedGraphNode<int>(2);
var node3 = new DirectedGraphNode<int>(3);
var node4 = new DirectedGraphNode<int>(4);
var node5 = new DirectedGraphNode<int>(5);
var node6 = new DirectedGraphNode<int>(6);
var node7 = new DirectedGraphNode<int>(7);
var node8 = new DirectedGraphNode<int>(8);
var node9 = new DirectedGraphNode<int>(9);
var graph = new List<DirectedGraphNode<int>>()
{
node1, node2, node3, node4, node5, node6, node7, node8, node9
};
node1.ConnectedNodes.Add(node2);
node1.ConnectedNodes.Add(node3);
node3.ConnectedNodes.Add(node5);
node5.ConnectedNodes.Add(node7);
node7.ConnectedNodes.Add(node9);
node5.ConnectedNodes.Add(node1);
node5.ConnectedNodes.Add(node3);
node4.ConnectedNodes.Add(node1);
Assert.IsTrue(IsNodesConnected(node1, node3));
CleanUpGraph(graph);
Assert.IsTrue(IsNodesConnectedClassicBreadthFirstSearch(node1, node3));
CleanUpGraph(graph);
Assert.IsFalse(IsNodesConnected(node1, node4));
CleanUpGraph(graph);
Assert.IsFalse(IsNodesConnectedClassicBreadthFirstSearch(node1, node4));
CleanUpGraph(graph);
Assert.IsTrue(IsNodesConnected(node1, node9));
CleanUpGraph(graph);
Assert.IsTrue(IsNodesConnectedClassicBreadthFirstSearch(node1, node9));
}
private static void CleanUpGraph(List<DirectedGraphNode<int>> graph)
{
foreach (var node in graph)
{
node.IsVisited = false;
}
}
public static bool IsNodesConnected<T>(DirectedGraphNode<T> nodeFrom, DirectedGraphNode<T> to)
{
if (nodeFrom == null || to == null)
{
return false;
}
if (nodeFrom == to)
{
return true;
}
foreach (var graphNode in nodeFrom.ConnectedNodes)
{
if (graphNode.IsVisited)
{
continue;
}
if (graphNode == to)
{
return true;
}
}
foreach (var graphNode in nodeFrom.ConnectedNodes)
{
if (graphNode.IsVisited)
{
continue;
}
graphNode.IsVisited = true;
var result = IsNodesConnected<T>(graphNode, to);
if (result)
{
return true;
;
}
}
return false;
}
public static bool IsNodesConnectedClassicBreadthFirstSearch<T>(DirectedGraphNode<T> nodeFrom, DirectedGraphNode<T> to)
{
if (nodeFrom == null || to == null)
{
return false;
}
if (nodeFrom == to)
{
return true;
}
var queue = new Queue<DirectedGraphNode<T>>();
queue.Enqueue(nodeFrom);
while (queue.Any())
{
var item = queue.Dequeue();
if (item == to)
{
return true;
}
item.IsVisited = true;
foreach (var node in item.ConnectedNodes)
{
if (node.IsVisited)
{
continue;
}
if (node == to)
{
return true;
}
queue.Enqueue(node);
}
}
return false;
}
}
public class DirectedGraphNode<T>
{
public List<DirectedGraphNode<T>> ConnectedNodes = new List<DirectedGraphNode<T>>();
public T Data;
public bool IsVisited = false;
public DirectedGraphNode(T data)
{
Data = data;
}
}
}