I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem:
I start out with this directed acyclic graph:
The values describe the range that the edge lengths are allowed to be. So the edge B->E can't be shorter than 9, but can be any size larger, while the edge B->C has to be between 0 and 1 (inclusive).
Also, it's constrained as if they were flattened onto a number line: for example, the distance from A->B->C is equal to the distance from A->C. And BE=BC+CD+DE, DF=DE+EF, AF=AB+BE+EF=AC+CD+CF, and so on. It's important to note that the ordering matters: D must come before E and F. Here's a visualization of that. Think of the gray lines as extendable/retractable bars:
My goal is to create an algorithm that narrows down the values to the most constrained possible range that is legal. For example, D->F has range (2,∞), but it can't be shorter than 3, since the smallest D->E->F can be is 3. So I would want to raise the minimum value of D->F's range to (3,∞). Note that real numbers are allowed. The end result would look like this:
The challenge is that I need performant method that runs ideally in roughly linear time. In practice, the graphs will be enormous and I will need to run this algorithm hundreds of thousands of times.
Originally, I was just dealing with minimum values, and had a version that was simple and worked well. It just added the previous min values up, did the same in reverse, and found the difference:
- put the root A in queue Q - while Q is not empty: - node N = Q.dequeue - if N has no previous edges: - N.prev_range = (0,0) - else: - N.prev_range = (0,∞) - for each edge PN in N.previous_edges: - N.prev_range.min = max(N.prev_range.min, P.prev_range.min + PN.min) - N.prev_range.max = min(N.prev_range.max, P.prev_range.max + PN.max) - now do the exact same thing in reverse: - start at F and move down, storing values in N.next_range instead - total_length = 15 (AF, in this example. We can treat AF as a special edge in my case, as I think my data will always have such an edge, although ideally the best solution would not need to designate a particular edge for this) - then, for each edge XY: - XY.min = max(XY.min, total_length - X.prev_range.max - Y.next_range.max) - XY.max = min(XY.max, total_length - X.prev_range.min - Y.next_range.min)
This algorithm just traversed the graph twice, and only looked at neighbors, so it ran fine on increasingly large graphs. However, once I started adding constraints with maximum values, like the B->C and D->E in this example having a max value of 1, I started getting a problem where edge B->E is essentially locking C->D into having a min size of 7 (through BC and DE), and that locking relationship isn't captured by the process I implemented, so it's not constraining it to 6.
Is it even theoretically possible to find the real sizes without having to search local edges for these kinds of relationships? I've been thinking about some physical analogs (ropes and knots, or sliding tubes) but they haven't helped. Does anyone have any ideas, or what kinds of things I should researching? Or if such a solution isn't possible, if there's a simple and relatively performant non-linear solution?