I am facing a problem that requires me get nodes that are within a ring. I wrote a recursie method but it is not doing what I want so I need some help on this one.
The picture below explains what I am looking for since I am having a hard time explaining it.
given the root node 0, I would like to get the ring from those nodes which is basically 0 , 1 , 2 , 7, 8, 9
keep in mind that each node contains list of nodes connected to it, so node 0 has both node 1, and node 9 as connected to it. so everything is there, but I cant get the correct logic to get that ring. here is the method I wrote but unfortunatly it is not working for all diagrams.
private bool SetMainRingList(StructureFeature strct, StructureFeature root, List<StructureFeature> mainRing) {
if ((strct.Equals(root) && mainRing.Contains(strct))) {
return false;
}
var children = strct.GetConnectedStructures();
if ((children.Contains(root) && mainRing.Contains(strct))) {
return false;
}
mainRing.Add(strct);
foreach (var structureFeature in children) {
if (mainRing.Contains(structureFeature)) {
var strcture = mainRing.Find(x => x.Oid == structureFeature.Oid);
if (strcture.ParentFeature == null)
continue;
if (strcture.ParentFeature.Equals(root)) {
bool skip = false;
var crntChildren = strcture.GetConnectedStructures();
foreach (var childContainerse in crntChildren) {
if (!mainRing.Contains(childContainerse)) {
skip = true;
break;
}
}
if (!skip)
return false;
}
continue;
}
structureFeature.ParentFeature = strct;
var leaf = SetMainRingList(structureFeature, root, mainRing);
var exchangeSite = structureFeature as ExchangeStructure;
if (leaf && ReferenceEquals(exchangeSite, null)) {
mainRing.Remove(structureFeature);
} else {
return false;
}
}
return true;
}
from what i understood,you have a graph and need to get the nodes participating in the cycle.
Here you can use bridge finding algorithms and delete the corresponding node forming the bridge.so the nodes left at last will form the ring.