Is there some sort of algorithm to continue looping through an unknown amount of child members?

Question

I have the following object set up:

public class DrawingInstance
{
    public string DrawingNum;
    public string Rev;
    public string Title;
    public int LevelNum;
    public string RefDesc;
    public string DateRelease;
    public string DrawingType;
    public DrawingInstance ParentMember;
    public int PageInstance;

    public List<DrawingInstance> ChildMembers = new List<DrawingInstance>();
}

After gathering all of the data, I am currently accessing each child member one level at a time, like so:

for (int i = 0; i < drawingInstance.ChildMembers.Count; i++)
{
    for (int j = 0; j < drawingInstance.ChildMembers[i].ChildMembers.Count; j++)
    {
        ....
        ....
    }
}

The number of levels in the file being processed can be different each time.

Is there a way through recursion to loop through and traverse an infinite number of levels? I need to process them 1 level at a time. So all of the i's will be processed, then all of the j's for each i are processed, and so on. Currently I have 10 blocks of code for processing a possible of 10 levels, but I feel like there has to be a better way to go about this.

EDIT Thanks for the quick responses. Here is a more detailed look straight from my code that gives a little more insight into how I am currently processing the objects

//Level 0 Pages
        int _pageNum = PageNum;
        int startIdx = 0;
        int pageCount = 0;
        pageCount = GetVisioPageCount(_treeArray.ChildMembers.Count);
        for (int i = 0; i < pageCount; i++)
        {
            VisioSheetOutline tempSheet = new VisioSheetOutline();
            tempSheet = GetSingleSheet(_treeArray, startIdx, _pageNum, (i + 1));
            for (int cMember = 0; cMember < tempSheet.ChildPairs.Length; cMember++)
            {
                ParentDictionary.Add(tempSheet.ChildPairs[cMember].SingleInstance, tempSheet.SheetName);
            }
            SheetList.Add(tempSheet);
            _pageNum++;
            startIdx += 15;
        }


        //Level 1 Pages
        for (int i = 0; i < _treeArray.ChildMembers.Count; i++)
        {
            pageCount = 0;
            pageCount = GetVisioPageCount(_treeArray.ChildMembers[i].ChildMembers.Count);
            startIdx = 0;
            for (int j = 0; j < pageCount; j++)
            {
                VisioSheetOutline tempSheet = new VisioSheetOutline();
                tempSheet = GetSingleSheet(_treeArray.ChildMembers[i], startIdx, _pageNum, (i + 1));
                for (int cMember = 0; cMember < tempSheet.ChildPairs.Length; cMember++)
                {
                    ParentDictionary.Add(tempSheet.ChildPairs[cMember].SingleInstance, tempSheet.SheetName);
                }
                SheetList.Add(tempSheet);
                _pageNum++;
                startIdx += 15;
            }
        }

        //Level 2 Pages
        for (int i = 0; i < _treeArray.ChildMembers.Count; i++)
        {
            for (int j = 0; j < _treeArray.ChildMembers[i].ChildMembers.Count; j++)
            {
                pageCount = 0;
                pageCount = GetVisioPageCount(_treeArray.ChildMembers[i].ChildMembers[j].ChildMembers.Count);
                startIdx = 0;
                for (int k = 0; k < pageCount; k++)
                {
                    VisioSheetOutline tempSheet = new VisioSheetOutline();
                    tempSheet = GetSingleSheet(_treeArray.ChildMembers[i].ChildMembers[j], startIdx, _pageNum, (i + 1));
                    for (int cMember = 0; cMember < tempSheet.ChildPairs.Length; cMember++)
                    {
                        ParentDictionary.Add(tempSheet.ChildPairs[cMember].SingleInstance, tempSheet.SheetName);
                    }
                    SheetList.Add(tempSheet);
                    _pageNum++;
                    startIdx += 15;
                }
            }
        }

I am currently looking into a few of the suggestions that were made to see which one fits my particular need.

"Tree Traversal" is what you want: http://en.wikipedia.org/wiki/Tree_traversal — Ian Mercer, Nov 10 '14 at 17:47
http://programmers.stackexchange.com/a/226162/25199 without recusion, in case you go extra deep. — Jodrell, Nov 10 '14 at 18:14

score 3 · Accepted Answer · answered Nov 10 '14 at 17:49

3

Yes, as you suggested, you can easily deal with this using recursion; you just need a recursive function:

public void ProcessDrawingData(DrawingInstance instance)
{
     // Do processing
     foreach (DrawingInstance d in ChildMembers)
         ProcessDrawingData(d);
}

Call it with the parent instance. This won't do a true breadth-first traversal though, as the first child will execute its first childs children (first all the way down) and slowly unwind.

answered Nov 10 '14 at 17:49

BradleyDotNET

60,462
10
96
117

The processing should probably be done after the recursive call... – smac89 Nov 10 '14 at 17:50
@Smac89 He wanted "i"s before "j"s which to my interpretation was doing the processing first. It just depends on when you want to "visit" the node. – BradleyDotNET Nov 10 '14 at 17:51
This may work, but be wary that depending on the depth of the tree, you might blow your stack doing this. The alternative is to do a `while(true)` loop to avoid a new frame. Also beware that SO exceptions vary depending on whether your platform is x86 or x64, so test both if needed. (IIRC, the x64 JIT is more likely to do a tail call optimization). – vcsjones Nov 10 '14 at 17:51
@vcsjones Of course, thats always a potential issue doing tree traversal via recursion. Thank you for the caveat though! – BradleyDotNET Nov 10 '14 at 17:52

score 1 · Answer 2 · answered Nov 10 '14 at 17:50

1

Microsoft's Ix-Main package contains a number of LINQ extensions, including the Expand method which will flatten a hierarchical layout:

IEnumerable<DrawingInstance> rootList = ...;
IEnumerable<DrawingInstance> flattened = rootList.Expand(x => x.ChildMembers);

answered Nov 10 '14 at 17:50

Cory Nelson

29,236
5
72
110

Does that recursively flatten? – BradleyDotNET Nov 10 '14 at 17:51
Yes, it is recursive. – Cory Nelson Nov 10 '14 at 17:52
Very cool; recursive `SelectMany`. +1 for something I didn't know about! – BradleyDotNET Nov 10 '14 at 17:53

score 0 · Answer 3 · answered Nov 10 '14 at 17:49

0

You can use the foreach() statement. This will iterate through a group that you need, assuming the object implements IEnumerable.

In your case, try this:

foreach(DrawingInstance di in ChildMembers)
{
   // Do something with di.
}

EDIT

If you need to do this repeatedly, you should have some sort of a recursive method that takes a DrawingInstance, like this:

public void RecursiveMethod(DrawingInstance d)
{
   foreach(DrawingInstance di in d.ChildMembers)
   {
      RecursiveMethod(di);
   }
}

I don't know your project, so it is up to you to figure out the base case, or if this recursive edit is what you actually want.

answered Nov 10 '14 at 17:49

AdamMc331

16,492
10
71
133

Not the downvoter, but the original suggestion wasn't useful (since he needs to go multiple levels; not obvious from his title). With the edit, its fine, though it effectively duplicates my answer (granted, you explain `foreach` better). Also; he's using `List` so it definitely implements `IEnumerable` :) It could just be that the downvoter didn't come back to see your edit. – BradleyDotNET Nov 10 '14 at 18:02
@BradleyDotNET that's probably true. Not the best solution here, I will take that, but if my answer is incorrect I would take it down. – AdamMc331 Nov 10 '14 at 18:06

Is there some sort of algorithm to continue looping through an unknown amount of child members?

3 Answers3