A tree, where each node could have multiple parents

user_1119810 0
Viewed 24362

Here's a theoretical/pedantic question: imagine properties where each one could be owned by multiple others. Furthermore, from one iteration of ownership to the next, two neighboring owners could decide to partly combine ownership. For example:

territory 1, t=0: a,b,c,d
territory 2, t=0: e,f,g,h

territory 1, t=1: a,b,g,h
territory 2, t=1: g,h

That is to say, c and d no longer own property; and g and h became fat cats, so to speak.

I'm currently representing this data structure as a tree where each child could have multiple parents. My goal is to cram this into the Composite design pattern; but I'm having issues getting a conceptual footing on how the client might go back and update previous ownership without mucking up the whole structure.

My question is twofold.

  1. Easy: What is a convenient name for this data structure such that I can google it myself?

  2. Hard: What am I doing wrong? When I code I try to keep the mantra, "Keep it simple, Stupid," in my head, and I feel I am breaking this credo.

tree composite graph-theory oop design-patterns
3 Answers

Hard to tell without more information regarding the business rules. Though I've plenty of experience designing graphs where each node could potentially have numerous parents.

A common structure is the Directed Acyclic Graph. Essential rules here are that no path through the graph can cycle back onto itself. For example take the path "A/B/C/B", this would not be valid as B repeats twice.

  1. Valid:- "A/B/C", "D/E/C", node C has two parents E and B.
  2. Invalid:- "A/B/C/B", node B repeats in the same path causing a cycle.
user_60123370
Related