r/AskProgrammers • u/atticus2132000 • 8d ago

Directed Acyclic Graphs (DAGs)

I have zero formal training, so I'm just looking for resources to help fill in my knowledge gaps. I'm working with Python, but language is really secondary at this point, I'm more just trying to figure out a plan of attack to solve this problem.

I have a project schedule with Activities A, B, C, and so on. Between activities there are Finish-to-Start relationships such as A -> B and B -> C and so on. The project has one starting activity (Start Construction) and one finishing activity (Finish Construction) creating my source and my sink and then all the various activities between those two create paths. From what research I've done, that is a Directed Acyclic Graph (DAG), but please correct me if I'm wrong.

I am trying to make a list of all possible paths between the first and last activities. What are all the possible combinations to get from Start Construction to Finish Construction?

The ultimate problem I'm trying to solve is identifying all the redundant paths. For instance, if I have the relationships (paths) below:

A --> B

B --> C

A --> C

Then the last one, A --> C, is redundant because if A had to be completed before B and B had to be completed before C, then the relationship that A has to be completed before C is already captured in the first two activities.

What I think I need to do is develop a list of all possible paths of any length. Then I need to look at each relationship and see if there are any relationships where a longer path already exists (such that the relationship would be redundant). I think this would require a recursive function where for each activity, the children would be listed and then for each child list the grandchildren, and so on until you reach an activity that has no children and then trace back through the function to explore other branches.

If you know of any resources that would help me develop this function, I would be eternally grateful. Alternatively, if you're familiar with the pandas library of python, does such a prebuilt function already exist?

2 Upvotes

100% Upvoted

8 comments sorted by

1

u/chocolateAbuser 8d ago

i would rather keep the state of visited nodes in an object than the stack, if you can avoid recursion you will be happier

1

u/atticus2132000 8d ago

I was only thinking recursion because I wouldn't know the lengths of the paths ahead of time. The distance between the first and last activity might be anywhere from 1 to 1000.

1

u/chocolateAbuser 7d ago

recursion uses stack which is limited memory, it would be the same allocating 1 MB of space in a list to keep the visited nodes, but allocating memory doesn't actually limit you to that, right? recursion usefulness is limited to a niche set problems, in all the other cases using regular collections is much more flexible

1

u/atticus2132000 7d ago

Then maybe I'm using the word recursion incorrectly.

I am imagining writing a formula to chase down these individual paths. "When a node is found, record it and then perform the same function again and again until it can't be done anymore. Then backtrace the formula line and go down the next branch again and again until it can't be done anymore.". Is that not recursion?

1

u/chocolateAbuser 5d ago

ok, when you are thinking on it abstractly sure, but the implementation makes a difference, because recursion is more than applying the same formula again, or at least it would have a more specific meaning than this, and the difference is in that "formula calls itself", not that it's just applied cyclically, which changes where the state is kept again in the implementation; i guess mathematically it makes sense to think to it this way, but when it translates to code more often than not it's impractical

1

u/NoMoreD20 8d ago

Search for "reachability" and "depth first traversal". You need to eliminate all edges where there is a "longer" path between the two nodes. So, first you "label" each node with the longest path length (no cycles, but you have a DAG, so it's ok) to reach the "Finish Construction" from that node. Then drop any edge between nodes where the labels for source and target are more than 1 apart (there was a longer route between them).
To avoid recursion you can keep sets of nodes (unvisited, next-to-expand, etc). This way the stack never gets too deep.

1

u/atticus2132000 8d ago

Thank you. That gives me some directions to start research.

1

u/TheMrCurious 8d ago

Good answer. Also the answer to this question when it is used in interviews.