C# - Every possible path in a Curve Network given the Root

Given a 3D network of curves and point (root) at one of the end points of the network, I have been trying to get all the possible paths from it.

To illustrate what I mean:

Ideally after running the algorithm starting from the root I would get the following:
List A <C0, C1,C2,C4,C7>
List B <C0,C1,C3,C5,C7>
List C <C0,C1,C3,C6,C8>

Problem is I am only managing to get the following:

List A <C0,C1,C2,C4,C7,C3,C5,C6,C8>

I attach the code I have written. ( In this code as it is a 3D curve Network I add an extra condition so the path always moves up on the Z axis, meaning that at the end I would get all the connections as long as they move progressively up in Z direction)

I have been looking at some graph theory algorithms but I have not been able to decipher them.

Any help would be greatly appreciated.All possible paths.gh (8.7 KB)

If you traverse the tree recursively you’ll have very simple logic. When you encounter a Y branch you just take on path (Path[0]) and when that path is consumed you take the next path (Path[1]) and that’s all the logic needed in the traverser.

If C7 must not be visited repeatedly you will have to make a “paths_visited” list to keep track of where the traverser has already been.

// Rolf

Thank you the reply Rolf. This is what I have been trying to do, but there is something wrong in the logic of my code which does not give me the desired result.

BTW: when you do recursive things is advisable to use DataTrees for the result (or some other suitable collection) where each branch samples the nodes on a per loop basis (as Rolf noticed use a bool[ ] visited = new bool[node.Count] for never dating the same girl twice).

For instance this allows you to pick (with the cross hair) any node in a graph as the root and then reorders the graph with respect that root.

The only thing that you need is the node/node connectivity: for a given loop get the nodes in the tree in branch (loop-1) and for each add the new (not visited) neighbor nodes in branch(loop) … blah, blah.

2 Likes

 private void RunScript(List<Line> lines, Line line, ref object A)
{
  unifyDirs(lines);
  var ways = new List<List<Line>>(){new List<Line>(){line}};
  var dt = new DataTree<Line>();
  bool finished;
  do
  {
    finished = true;
    var temps = new List<List<Line>>();
    foreach(List<Line> way in ways)
    {
      var hasNext = false;
      foreach(Line ln in lines)
      {
        if(ln.From == way[way.Count - 1].To)
        {
          hasNext = true;
          temps.Add(new List<Line>(way){ln});
        }
        finished = !(finished || hasNext);
      }
      if (!hasNext) dt.AddRange(new List<Line>(way), new GH_Path(dt.BranchCount));
    }
    ways = temps;
  } while(!finished);
  A = dt;
}
// <Custom additional code> 
void unifyDirs(List < Line > lines)
{
  for(var i = 0; i < lines.Count; i++)
  {
    var line = lines[i];
    if(line.ToZ < line.FromZ)
    {
      line.Flip();
      lines[i] = line;
    }
  }
}
// </Custom additional code> 

Paths.gh (11.4 KB)

3 Likes

Thank you very much Mahdiyar, this is exactly what I was trying to achieve. I will go over it to try and understand the code behind it.