To find subcategories using C#?

Question

In an application a category can contain subcategories. And each subcategory can contain subcategories. A category can also be subcategories to one or more categories. If we are given the Category class.how can we implement a property that returns the count of UNIQUE subcategories for a category and ALL its UNIQUE subcategories?

Code Snippet

public class Category
{
 public List<Category> Subcategories = new List<Category>();
 public int UniqueSubcategoriesCount
 {
  get
  {
    //How to implement
    /*My Thoughts.
     1. use the CategoryID field to find the unique ones.
     2. Implement the Equals()function to   compare the CategoryID.
     3. To find the subcategories with in the categories we need to loop recursively./*
  }
 }
}

Any other ideas are welcomed.

Determine a uniqueness factor for each category and count the amount of distinct subcategories based on this factor. That's the best answer you can get without any code to show us. — Jeroen Vannevel, Mar 14 '14 at 21:26
Read about [recursive](http://en.wikipedia.org/wiki/Recursion) functions. — Yair Nevet, Mar 14 '14 at 21:27
@Jeroen: Could the reference itself be ID enough? E.g. put them in a Dictionary or HashSet and then Count(). (I'm not sure whether the OP can have several instances of the same Category.) — Peter - Reinstate Monica, Mar 14 '14 at 21:43
@PeterSchneider: it's hard to answer that without knowing how the application works. If the categories themselves are simply retrieved from a central repository then this should be okay but if they are somewhere constructed then this might cause trouble. For the sake of clarity I would not rely on reference equality but always implement a correct value equality. — Jeroen Vannevel, Mar 14 '14 at 22:18
Is it possible to have a circular reference between two or more categories? — Dialecticus, Mar 14 '14 at 23:18
You want the transitive nonreflexive closure of the subcategory relation, yes? — Eric Lippert, Mar 14 '14 at 23:30

score 0 · Answer 1 · edited May 23 '17 at 12:27

0

Based on what I understand from your question, you could try something like this:

//Category implementation
public class Category
{
    public List<Category> SubCategories { get; set; }
    public int CategoryID { get; set; }

    public static int count = 0;

    public Category()
    {
        SubCategories = new List<Category>();
    }

    public void Add(Category cat)
    {
        SubCategories.Add(cat);
    }

    public IEnumerable<Category> AllSubCategories()
    {
        var stack = new Stack<Category>();
        stack.Push(this);

        while (stack.Count > 0)
        {
            Category cat = stack.Pop();
            yield return cat;

            foreach (Category nextCat in cat.SubCategories)
                stack.Push(nextCat);
        }

    }

}

...

//Testing the code
Category top = new Category() { CategoryID = 1 };
top.Add(new Category() { CategoryID = 2 });
top.Add(new Category() { CategoryID = 5 });
top.Add(new Category() { CategoryID = 3 });
top.Add(new Category() { CategoryID = 1 });
top.Add(new Category() { CategoryID = 2 });
top.Add(new Category() { CategoryID = 4 });

Category tmp = new Category() { CategoryID = 1 };
top.Add(tmp);

tmp.Add(new Category() { CategoryID = 1 });
tmp.Add(new Category() { CategoryID = 7 });
tmp.Add(new Category() { CategoryID = 6 });

Category tmp2 = new Category() { CategoryID = 7 };
tmp.Add(tmp2);

Category tmp3 = new Category() { CategoryID = 4 };
tmp2.Add(tmp3);

Category tmp4 = new Category() { CategoryID = 3 };
tmp3.Add(tmp4);

Category tmp5 = new Category() { CategoryID = 1 };
tmp4.Add(tmp5);

Category tmp6 = new Category() { CategoryID = 9 };
tmp5.Add(tmp6);

var Result = top.AllSubCategories().GroupBy(c => c.CategoryID).Select(g => g.First()).ToList();

Cheers

EDIT #1: I think I should give credit to Jon Skeet for this idea: https://stackoverflow.com/a/2055946/172769

Just in case anyone is wondering where it came from.

EDIT #2: Based on comments from Eric Lippert about bad performace of nested iterators, I changed my code to use an "unwind to stack" method that I got from: https://stackoverflow.com/a/1043363/172769

edited May 23 '17 at 12:27

Community

1
1

answered Mar 14 '14 at 22:29

Luc Morin

5,302
20
39

Note that this solution is worst case quadratic in time and linear in stack. You can make it linear in time and heap, constant in stack – Eric Lippert Mar 14 '14 at 23:32
@EricLippert I know you mean well, but I have no clue what you're talking about. It would certainly benefit me (and others), if you could provide an example, maybe your own version of the solution, and explain how each of your affirmations is demonstrated by your example. – Luc Morin Mar 14 '14 at 23:59
See Wes dyers article on nested iterator blocks for a good analysis. – Eric Lippert Mar 15 '14 at 00:39
Briefly: suppose the subcategory tree is deep but not broad. Count how many times you yield something. Do you see the relationship between depth and number of yields? – Eric Lippert Mar 15 '14 at 00:42
@EricLippert I find that when deepening the levels, without broadening them (each level having 1 item), I get n(n+1)/2 yields. I understand on the surface, but it hasn't sunken in yet. I must read some more to understand the inner workings of this. – Luc Morin Mar 15 '14 at 01:57
Right, that's why it is in the worst case quadratic in time. – Eric Lippert Mar 15 '14 at 03:49
@EricLippert please comment my new attempt. – Luc Morin Mar 15 '14 at 09:29
You got it; that's now worst case linear in heap because the explicit stack is now being used instead of the call stack. And the number of yields is equal to the number of items yielded, so it is linear in time. The downside is of course that the code is longer and less elegant. C-Omega would automatically rewrite nested iterators into the more efficient form but that feature was never added to C#. – Eric Lippert Mar 16 '14 at 01:05
@EricLippert it's stuff like this that make me realize how little I really know about formal programming. – Luc Morin Mar 16 '14 at 16:19

score 0 · Answer 2 · answered Mar 15 '14 at 00:01

Does this do what you want?

public class Category
{
    public int CategoryID;
    public List<Category> Subcategories = new List<Category>();
    public int UniqueSubcategoriesCount
    {
        get
        {
            return this.GetUniqueSubcategories().Count();
        }
    }

    private IEnumerable<Category> GetUniqueSubcategories()
    {
        return
            this
                .GetSubcategories()
                .ToLookup(x => x.CategoryID)
                .SelectMany(xs => xs.Take(1));
    }

    private IEnumerable<Category> GetSubcategories()
    {
        return this.Subcategories
            .Concat(this.Subcategories
                .SelectMany(x => x.GetSubcategories()));
    }
}

To find subcategories using C#?

2 Answers2