Design pattern for constructing and linking up objects that form a graph

Question

I am working on a simple library that will help me work with prescription drugs. For instance, DrugBank contains a list of FDA approved drugs, and, importantly, how these drugs interact with one another. So, for instance, we might have drug A, which might then interact with drugs B and C in some way.

In a previous project doing something similar, my approach consisted of two steps: 1. I would load and construct the objects from the file, and store the interacting drug IDs into some list. Then 2., after constructing all the objects and putting them in a global dictionary, I would iterate over each object and replace the string IDs with a reference to the actual object.

I am writing my code in Python, but that's not really important, I just want to know what a good way to structure this might be.

So, in Python, some pseudocode might look something like this:

1. Read and create the drug objects

class Drug:
    def __init__(self, id, name, interactions):
        self.id = id
        self.name = name
        self.interactions = self.interactions  # list[str]

so, I might construct my example drugs A, B, and C like this

drug_a = Drug("A", ["B", "C"])
drug_b = Drug("B", [])
drug_c = Drug("C", [])

and have them stored in some global dictionary e.g.

DRUGS = {"A": drug_a, "B": drug_b, "C": drug_c}

2. Replace the drug ID strings in each Drug object with references to the actual drug objects

for drug in DRUGS.values():
    drug.interactions = [DRUGS[d_id] for d_id in drug.interactions]

This works well enough, but I'm wondering whether there is a better way, or an established design pattern for something like this. This two-step approach seems suboptimal and very much ad-hoc. But I can't really see a better way of doing things, so any insight would be interesting.

Answer 1

I don't really follow why you would want to model this kind of data in this way. The most straight forward way to do with would be to create a set of interactions like this:

i0 = ('A', 'B')
i1 = ('A', 'C')

And then index them:

{
  'A': (i0, i1),
  'B': (i0),
  'C': (i1),
}

The variable declarations are unnecessary and just for demonstrative purposes.

In the real-world drug interactions are more than just a list of drugs that interact, there would be other data associated with an interaction such as what it does and/or contraindicated diagnoses. Interaction should therefore be its own type and which you would then index based on how you need to look up the interactions.

In short, I would not model interactions as a property of a Drug but flip it around and model drugs as one of the properties of an Interaction.

Answer 2

When I see this:

drug_b = Drug("B", [])

I see two problems. B is unaware that it has a drug interaction with A and the idea that A and B interact needs to be recorded twice.

This boils down to the use of the wrong data structure. You've essentially built a directed graph. But if drug A interacts with B then B interacts with A. So long as that's true you don't need this much control over a directed graph. What you really need is a undirected graph.

Consider:

edge("A", "B")

This captures the idea that they interact with each other in one line. Doesn't mater which comes first. It also doesn't force you to back this with any particular implementation which is a bonus. As one example you could back it with a dictionary that takes each edge as two key value pairs. "A", ["B"] and "B", ["A"]. The trick here is that the values are a list that you append to. This way any drug can be used to look up all of it's interacting drugs.

That means if you later say:

edge("A", "C")

No previous edge code needs to be updated. We’re exploiting the fact that while nodes connect to many nodes an edge always has exactly two nodes. Back this with a dictionary and it’ll look like this:

Key, Value
"A", ["B", "C"]
"B", ["A"]
"C", ["A"]

But you don't have to implement edge that way. There are others.

And you don't have to just stick to strings. You could have your drug objects. But you'd ensure they looked more like this:

drug_a = Drug("A", ["B", "C"])
drug_b = Drug("B", ["A"])
drug_c = Drug("C", ["A"])

If some one later added

edge("D", "C")

Then you could do something like:

drug_d = Drug("D", ["C"])
drug_c.interactions.append("D")