1

I have a representation of a process trough something that is very much like a DAG (Directed Acyclic Graph). This graph is represented with an adjacency table, but not like a "regular" adjacency table, there are few differences:

  • Each entry in the table is a list of lists,
  • Each "inner" list states the predecessor nodes required.

The idea for this data structure is to hold requirements of steps within a process. So, for example: enter image description here

P = {1:[[]], 2:[[1]], 3:[[2]], 4:[[3]], 5:[[2]], 6:[[]], 7: [[4,6],[8,5]], 8:[[]]}

For process P, step 1 doesn't require any predecessor, step requires step 1,..., step 6 also doesn't require any predecessor, step 7 requires steps (4 and 6) OR (8 and 5).

Each step has a state (some ID reference) that determines if the next step can be executed or not, or if the process can be terminated or not.

In the example above, I would not be able to execute step 2 if step 1 didn't fulfill some specific condition regarding the state the same for step 5, which requires step 2 with state=something specific. And for step 7, the only way to execute it, would be if step 4&6 OR 5&8 have their corresponding state=something specific.

What I need is a way to get all the unique paths that lead to a certain step, so later I can check against this paths if the conditions are met. For step 7 it would be : paths = [[1,2,3,4,6],[1,2,5,8]]

I've checked:

Most of the information around points to some sort of modified DFS or some kind of enhanced Dijkstra. For what I've checked and tested none of the above gives me what I need which is a list of all "unique paths" that lead to a node that may be reached from "different paths".

The question is not language specific, so any example in any language would be appreciated :)

EDIT: 04/01/22 Further clarifications:

  • The steps are one way, meaning that node 1 is connected to step 2 by a distance of 1, to step 3 a distance of 2, and so on. But step/node 1 is not conntected with 6 or 8.
  • All graphs have a unique starting point and ending point. In the example 1 and 7.
  • Yes, node 5 should be connected to node 7. Img updated.
  • The number of nodes will always be <100.
FireHuillin
  • 31
  • 2
  • 5
  • Is there a path from node 1 to every other node in the graph? Can we assume that every path you want starts at node 1? – ravenspoint Jan 01 '22 at 15:11
  • I'm not sure I understand the actual problem here: if your datastructure is already what you show, then this is just a direct composition by barely doing any work: for each node, check each parent, and save those paths in a tracking datastructure while you're walking the graph. E.g. start at 7: we _know_ its parents, so for each one you loop up _their_ parents, and keep doing that. Every time there's more than 1, you duplicate your known-paths-so-far and pass down a distinct copy as part of the lookup so you end up with a full set of distinct paths once you've walked the entire graph involved. – Mike 'Pomax' Kamermans Jan 01 '22 at 16:24
  • but note that 7 is definitely not `[[1,2,3,4,6],[1,2,5,8]]`, even if you forgot to draw the arrow from 5 to 8, and forgot to write 8 as `8:[[5]]`. Right now, from what you're showing, 7 is `[[1,2,3,4],[6],[8]]`. Three ways to get there, one long path, two single node paths. – Mike 'Pomax' Kamermans Jan 01 '22 at 16:28
  • "7: [[4,6],[8,5]]," This does not match your picture. There is no link between 5 and 7 in the picture. Which is correct, the picture or the text? – ravenspoint Jan 01 '22 at 19:47
  • @Mike'Pomax'Kamermans I've updated the question and corrected the image. I think this should be resolved using recursion but I can't seem to figure it out. How do I keep track of each distinct path within the stack? Or how do I break or split the two distinct paths within the recursion? – FireHuillin Jan 05 '22 at 13:48
  • Your updated graphics still does not reflect the paths you're claiming there are. With the added edge, there are now four paths to 7: [1,2,3,4], [1,2,5], [6], and [8]. Look at your graph, _manually_ run through it first for each node to make sure you have the correct paths-to-that-node information in your post, and even just by doing that you should already start getting an idea on how to properly implement this. But if not, once your graph and code are aligned we can write up an answer. Until then, not much to say other than "which of the two is right, the graph, or the code claim?" – Mike 'Pomax' Kamermans Jan 05 '22 at 17:30
  • Now I understand what you mean, yes there are 4 individual paths to 7. I wasn't clear enough regarding the meaning of the "step requirements", as for step 7 the requirements are steps (4 and 6) or (5 and 8), so I can "merge" this paths together. They represent the same requirement I need to check, [1,2,3,4]+[6] or [1,2,5]+[8], but yes, each array represents a different path. – FireHuillin Jan 05 '22 at 22:23
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Jan 09 '22 at 02:26

2 Answers2

0

How big is your graph? What is your performance requirement?

For a small graph like your example, Dijsktra is almost instant. So you do not need to store all the paths.

  • Set cost of all links to 1
  • Set cost of links that lead to nodes that are NOT in the required state to 10^10
  • Run Dijkstra to find shortest path from source to destination through nodes in required state.
ravenspoint
  • 19,093
  • 6
  • 57
  • 103
0

I think I've managed to get what I needed, nevertheless I think the answer is overly complex.

Function to populate a tracker object with all the possible paths.

const tracker = {};
function getPaths (step, branchRef) {
    const currentStepRequires = getStepRequires(step); // func that gets the array of arrays of current step
    const oldBranchRef = branchRef;
    const hasBranches = currentStepRequires.length > 1;
    for (const branch of currentStepRequires) {
        if (branch.length === 0) {
            return;
        }
        if (!hasBranches && !branchRef) {
            tracker[branch] = [];
        }
        if (!branchRef) branchRef = branch;
        if (hasBranches) {
            if (oldBranchRef && oldBranchRef !== branchRef) {
                tracker[branch] = [...tracker[oldBranchRef]];
            }
            else if (tracker[branchRef]) {
                tracker[branch] = [...tracker[branchRef]];
                branchRef = branch;
            }
            else {
                tracker[branch] = [];
            }
        }

        for (const step of branch) {
            tracker[branchRef].push(step);
            getPaths(step, branchRef);
        }
        if (hasBranches) branchRef = '';
    }
}

After the tracker object has been populated I need to remove the paths that are contained within the other paths. I'm using lodash here to simplify the filtering, checking and adding the paths

const paths = [];
_.forEach(_.sortBy(tracker, path => path.length * -1), branch => {
    const isSubpath = _.some(paths, path => _.isEqual(branch, _.intersection(path, branch)));
    if (!isSubpath) {
        paths.push(branch);
    }
});

For the example above, this returns the following: [[4,3,2,1,6], [8,5,2,1]]

I've also tested with more "branching", like example: P = {1:[[]], 2:[[1]], 3:[[2]], 4:[[3]], 5:[[2]], 6:[[]], 7: [[4,6],[8],[5]], 8:[[6],[3]]} Which returns: [[4,3,2,1,6],[8,6],[8,3,2,1],[5,2,1]]

For now its working, but....as I said, I think its more complicated than it needs to be. So, any improvements are welcome.

FireHuillin
  • 31
  • 2
  • 5