A tree, where each node could have multiple parent

Question

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.

Answer 1

You have a many-to-many relationship between your owners and your territories (properties). I'm not sure what language you're working in, but this sort of thing can be easily represented and tracked in a relational database. (You'd probably want a table for each entity, and the relationship would probably require a third "junction" table. If it's necessary to be able to query "back in time", this could have some sort of "time index" column as well.)

If you are working in an object-oriented language, you might create two classes, Territory and Owner, where the Territory class has a property/member/field which is a collection of references/pointers to Owners and the Owner class has a similar collection of Territories. (One of these two collections may need to contain "weak" references depending on the language.)

In this case, some difficulty may arise if you want to be able to go back and look at the network state at some particular point earlier in time. (If this is what you need, say so and I (or someone else) can post a solution that works for that.)

I'm not sure what level of simplicity you are striving for, but in neither of these cases is updating the ownership relationships really that "hard". Maybe if you posted some code it might be easier to give you more concrete advice.

Answer 2

My question is two fold: Easy: What is a convenient name for this data structure such that I can google it myself?

What you have here is not a tree, it is a graph. A multimap will help you here. But any adjacency list or adjacency matrix will give you a good start.

Here is a video on adjacency matrix and list: Youtube on adjacency matrix and list

Hard: What am I doing wrong?

This is really hard to tell. Perhaps you did not model the relationship in a proper way. It is not that hard, given a good datastructure to start with.

And, as you asked for design patterns (but you probably found out yourself), the Composite pattern will let you model such an setting with ease.