Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an "in-flow" and an "out-flow" from and to its neighbor nodes respectively.

Each edge $e_{i,j}$ represents a traffic out-flow from $i$ to $j$. For example, an edge weight of $50$ might mean that 50 cars traveled on that road (in the specific direction represented by the edge). Suppose that I know the flow for each road (in other words, I know all the edge weights). I am interested in calculating the following quantity:

I want to know the number of cars that traveled from $i \rightarrow j \rightarrow k$. So of all the cars that traveled from $i \rightarrow j$, I want to know the number of cars that also traveled from $j \rightarrow k$. Can this problem be solved? Could we add certain assumptions to make the problem feasible? For example, if I assume that the net flow at each node is 0, in other words, $\sum_j e_{i,j} = \sum_j e_{j,i}$ (a circulation).

Here's an example graph that my problem might have. Can I calculate the number of cars that traveled from $1$ to $2$ and then to $4$? What modifications can I possibly make to be able to do this? This graph is simplified and the general case is a little more complicated to describe here.

enter image description here

enter image description here

If we consider only the path $1 \rightarrow 2 \rightarrow 4$ then of the 10 cars that travel from $1 \rightarrow 2$, let $x_1$ go back from $2 \rightarrow 1$ and the remaining $x_2$ go from $2 \rightarrow 4$. Similarly, of the 3 cars going from $4 \rightarrow 2$, let $y_1$ go back from $2 \rightarrow 4$ and the remaining $y_2$ go from $2 \rightarrow 1$. The total flow from $2 \rightarrow 1$ and $2 \rightarrow 4$ is the sum of the constituent flows as contributed from node $1$ and node $4$. We can then setup the following equations: $$ x_1 + x_2 = 10, \\ y_1 + y_2 = 3, \\ x_1 + y_2 = 5, \\ x_2 + y_1 = 8, \\ x_1, x_2, y_1, y_2 \geq 0.$$

This system of equations has many feasible points. Anybody see some constraints etc. that I can add to make the solution unique ?

share|improve this question
    
@Tyson: thanks for linking the images! –  Mustafa Nov 16 '12 at 0:07
    
Perhaps I don't understand well the problem and what type of conditions should be set, but why don't you simplify the problem? If the flow from $x_1 \rightarrow x_2$ is $v_1$ and the flow from $x_2 \rightarrow x_1$ is $v_2$ and $v_1 > v_2$, you can use a single directed edge from $x_1 \rightarrow x_2$ with flow $v_1 - v_2$; and if $v_2 > v_1$ you can use a single directed edge $x_1 \leftarrow x_2$ with flow $v_2 - v_1$ ? Perhaps the resulting graph is easier and the problem can be better formulated. –  Marzio De Biasi Nov 16 '12 at 0:09
    
@Marzio: I need to preserve individual in and out flows from each node because the final quantity that I want to evaluate is a maximum likelihood estimate of the probability of a car transitioning from node $i$ to node $j$. If I remove a link $j \rightarrow i$ and combine the net flow in one direction of $i \rightarrow j$, then it reflects that $\mathbf{P}\{j \rightarrow i\} = 0$... i'm not sure if that will help in my case... –  Mustafa Nov 16 '12 at 0:24
2  
I don't think the question is well posed. The stated problem has many solutions. (In particular, in your example, any number of cars between 5 and 8 travel along the path $1\to2\to4$.) Obviously you can add more constraints or an objective function to make the solution unique, but that would change the problem! –  JɛffE Nov 16 '12 at 3:27
    
@Jeff: I understand that it changes the problem. In general though, given all the flows in a network, is it impossible to decompose them into their constituent components from each contributing node? –  Mustafa Nov 16 '12 at 5:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.