1
$\begingroup$

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 starting 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:

The constraints.

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 target result

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?

Thanks!

$\endgroup$
  • $\begingroup$ Can you define "geometrically legal" in formal terms? Are you dealing with integers only, i.e., no fractions? $\endgroup$ – Apass.Jack Oct 12 '18 at 4:25
  • $\begingroup$ Sorry, my phrasing is misleading, I'll edit it. What I mean is that the edge lengths should be viewed like as if they were flattened onto a single number line. For example, the length of the path from A->B->C should be the same as the edge AC. BE should be equal to BCDE, and BEF = BF. $\endgroup$ – lifeformed Oct 12 '18 at 4:39
  • $\begingroup$ If they are flattened onto a single number line, is there any restriction on which vertex must be either end? $\endgroup$ – Apass.Jack Oct 12 '18 at 5:04
  • $\begingroup$ Yes, I just updated the question again with a new image. The ordering matters, B can't come after C, and D can't come after E. I just realized that a DAG isn't the best way to visualize it, since it doesn't indicate any such constraints at all, I just took it for granted since I have been thinking about this problem for too long. $\endgroup$ – lifeformed Oct 12 '18 at 5:18
  • $\begingroup$ Thanks for the update. Yes, it happens frequently that various constraints become integrated with your thinking once you have been thinking about them for too long. $\endgroup$ – Apass.Jack Oct 12 '18 at 5:25
1
$\begingroup$

This can be formulated as a linear programming (LP) problem. Arbitrarily state that $A$ is at coordinate 0, then for your example graph we get equations

$$ A = 0$$ $$ B-A \ge 1 $$ $$ C-A \ge 1 $$ $$ 1 \ge C-B \ge 0 $$ $$ \dots $$ $$ F - E \ge 3 $$ $$ F - A = 15 $$

In particular, with $V$ nodes and $E$ edges, we have $V-1$ variables and at most $2E$ linear constraints. Linear programs can be solved in polynomial time (via e.g. the ellipsoid method), but it's not necessarily linear -- more like quadratic or cubic. However! You have a very sparse system: each constraint has only two nonzero entries. This means it will likely perform very well in practice. If you use a free (and usually very well optimized) library, like Gurobi or GLPK, they can use the Simplex method and pretty efficiently use the sparsity.

I realize this might not be completely satisfactory, but: LP solvers are pretty intelligent, and I'm not convinced there's a whole lot more structure to your problem that you could take advantage of that they won't. They will probably do something sort of like your take-min-first strategy, and then "fix" appropriately, and efficiently.

Finally, quick note: You didn't really specify what your goal is, but the solver will want some function to minimize. I would have suggested just saying "minimize $F$", but in your example graph $F$ is actually fixed. So a reasonable objective function might be "minimize $B+C+D+E+F$" or something. Depends on your application. But this should get you basically linear runtime on nearly all cases.

$\endgroup$
  • $\begingroup$ Thanks for the response. Would doing this be overkill if I am not looking for a specific goal? I am not trying to maximize or minimize anything yet, just trying to find the possible ranges. Your post had me research the Simplex Method - it seems like I am looking for a way to calculate the feasible region. $\endgroup$ – lifeformed Oct 12 '18 at 21:00
  • $\begingroup$ I think in practice, my system will be less sparse than my example. It could have more than two entries per constraint. I wonder if there's a way to take advantage of the fact that, in my system, all the constraints' terms have a coefficient of 1? And also that the constraints only involve addition and subtraction. $\endgroup$ – lifeformed Oct 12 '18 at 21:15
  • $\begingroup$ These are difference constraints; there are various efficient algorithms for solving LP problems with difference constraints. But I agree; I would start with a generic LP solver first. $\endgroup$ – D.W. Apr 11 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.