2

I'm having a difficulty to figure out relating an item to classes properly.

For example, I have a business directory website that shows profiles of different companies according to the products/services they offer. "LG" company, for instance, produces smartphones, TVs, blenders, etc.

I want the company to show up on each category accordingly and each parent category to show number of companies that it holds [i.e. Electronics(243) there are 243 companies that produce electronics].

Suppose I have:

 1. Electronics (243)        
    - Computers (14)
    - Smartphones (8)        // one of the 8 is LG 
    - TVs (10)               // one of the 10 is LG
 2. Kitchen tools (120)
    - Blenders (4)
    - etc.

I want the parent category to show the total number of ... [unique] ... companies in it. If LG company produces TVs and Smartphones, the parent category counts one company two times, hence giving wrong information. User might think there are 2 companies in this category, while there is only one.

How can I avoid duplicates ?

8
  • You're right. There will be the possibility of companies being counted two or more times in two or more categories. But, I have to ask, what's wrong with that?
    – MetaFight
    Commented Oct 29, 2016 at 14:17
  • I want the parent category to show the total number of the companies in it. If LG company produces TVs and Smartphones, the parent category counts one company two times, hence giving wrong information. User might think there are 2 companies in this category, while there is only one.
    – Nurbek
    Commented Oct 29, 2016 at 14:49
  • 1
    Oh, I understand better now. So, you're asking how to remove non-distinct company entries from your sum?
    – MetaFight
    Commented Oct 29, 2016 at 15:04
  • 1
    And the obvious recounting the companies from each level, doesn't meet your needs?
    – Erik Eidt
    Commented Oct 29, 2016 at 15:17
  • @MetaFight Yes, I was interested if it is possible at all
    – Nurbek
    Commented Oct 29, 2016 at 15:35

2 Answers 2

1

This looks like a job for the Set Abstract Data Type!

Provided each company can be retrieved across sub categories simply accumulate them in a set structure as you iterate through them. Those that have already been discovered will be discarded from the structure. When finished ask the structure what for its cardinality (count or length).

This idea is supported in many languages. You didn't list yours but I'd be surprised if it didn't already exist in some form. The idea is well documented if you find you must implement it yourself.

Some languages do not automatically provide the hash needed for this to all objects (looking at you java). If you construct your own objects for this be sure that's dealt with. However, you likely can get by with strings that even java provides with a hash.

As for it not looking right, simply explain what you're showing them:

Departments (unique companies)

  1. Electronics (18)
    • Computers (14)
    • Smartphones (8)
    • TVs (10)
  2. Kitchen tools (12)
    • Blenders (4)
    • etc.
1

Your requirements

  • you have a tree of categories
  • you have companies; companies are assigned to at lest one category; they can be assigned to several ones
  • you want to count companies assigned to any category node, making sure that each company is counted only once:
    • for leaf categories you count the exact number of assigned companies
    • for parent categories, you have to take into account companies that are assigned to the category itself, and the companies assigned to all the children, making sure not to count any company twice
    • mathematically, in the root category would count the total number of companies.

Possible solution

Your data model shall represent the direct relation of companies and categories (nodes).

You then need to build the transitive closure of this relation:

  • For a leaf node, the closure set would contain all the companies in direct relation.
  • For a parent node, the closure set would contain all the companies in direct relation with that node and all the companies in the closure sets of its children. Please note that in a set, by definition, every element appears at most once; technically you would do here union of sets.

You could follow two practical approaches for the implementation:

  • You can implement this in your OOP model, by building a closure-set container for each node. Up to you to decide if you build this closure set on demand, or if you maintain it every time you add a new association.
  • You can also do this in the RDBMS using a closure table.

To achieve your intend goal, you then would just count the companies in the closure set of each category .

Additional reading

Many articles here are about transitive closures in a graph or a tree at the node level (i.e. the closure would contain all the nodes that are reachable by one or several move down in the tree). You'd need to adapt these to put in the closure not the node itself, but the companies that are connected to each of these nodes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.