There's a real production project related to real estate properties around the world. The data has a structure of nested nodes. E.g. end nodes which have no outgoing edges (red) are properties and all nodes which have outgoing edges (blue) are just names of groups for those properties like "in Germany" or "residential apartments" group names. So in terms of graphs it is a closed and directional tree-like graph with terminal states as real-estate properties and all transitional nodes as group-names.

I am sure there is an efficient way to count the number of all terminal nodes (aka "properties", red) which belong to a given parent node (aka "group-name", blue). I just do not know what algorithms can be used to efficiently calculate this with as little CPU/Memory capacity as possible. Can you please suggest?

enter image description here

  • 2
    $\begingroup$ The picture looks more like a DAG (directed acyclic graph) than a tree. I'm not sure if I understand the problem, but in trees this kind of queries about the number of something in a subtree can be usually answered efficiently. In DAGs, however there are some quite natural problems of this kind that do not have better than O(n^2) algorithms assuming strong exponential hypothesis. I can elaborate on this if you clarify the question. $\endgroup$ – Laakeri Oct 1 '20 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.