A simple way to find the feasible region of a system with simple constraints 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?

Thanks!
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.