Aşağıdaki gibi bir kod yazdım. Test ettim. İşe yarıyor. Benim uygulamamda çok derin dallanmalar olmadığında kontrol fonksiyonunu recursive bıraktım.
Önce ağdaki her nokta için gidiş yönünde tanımlı linklerin listesini yapıp sonra fonksiyonumuza veriyoruz. Fonksiyon sırayla her noktadan başlayıp depth-first tarama ile ağı tarıyor. Tararken yolunu kaydediyor. Daha önce uğradığı bir noktaya tekrar uğruyorsa kapalı bir devre bulmuş demektir. Bulamazsa bu noktadan başlayınca kapalı devre çıkmıyor deyip işaretliyor ve tekrar o noktaya gelirse ikinci kez kontrol etmeden sonuç döndürüyor.
Kapalı devre bulma için ağ sınıfı kodu :
public class NetworkEngin
{
public struct NetworkNode
{
public List<int> outLinkList;
}
private List<NetworkNode> networkStr;
private bool[] visited;
public NetworkEngin(List<NetworkNode> networkStructure)
{
networkStr = networkStructure;
}
public bool LoopControl()
{
visited = new bool[networkStr.Count];
for (int i = 0; i < networkStr.Count; i++)
{
if (LoopCheck(i, new List<int>()))
return true;
}
return false;
}
public bool LoopCheck(int nodeNo, List<int> path)
{
if (visited[nodeNo]) return false;
foreach (int j in networkStr[nodeNo].outLinkList)
{
if (path.Contains(j))
return true;
else
{
List<int> newPath = new List<int>(path);
newPath.Add(j);
if (LoopCheck(j, newPath)) return true;
}
}
visited[nodeNo] = true;
return false;
}
}
Örnek kullanım:
private void Load()
{
List<NetworkEngin.NetworkNode> networkStructure = new List<NetworkEngin.NetworkNode>();
networkStructure.Add(new NetworkEngin.NetworkNode() { outLinkList = new List<int>() { 1, 2 } });
networkStructure.Add(new NetworkEngin.NetworkNode() { outLinkList = new List<int>() { 2, 3, 4 } });
networkStructure.Add(new NetworkEngin.NetworkNode() { outLinkList = new List<int>() { 3, 4 } });
networkStructure.Add(new NetworkEngin.NetworkNode() { outLinkList = new List<int>() { } });
networkStructure.Add(new NetworkEngin.NetworkNode() { outLinkList = new List<int>() { 3 } });
NetworkEngin NE = new NetworkEngin(networkStructure);
MessageBox.Show(NE.LoopControl().ToString());
}
Decompiling the code of universe.
Listening the cosmic background radiation.
Swimming in Inter Stellar Medium.
|
Del.icio.us
Digg
Facebook
Furl
Google
Blink
Simpy
Spurl
Y! MyWeb