<p>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.</p>

<p>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:</p>

<p>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).</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/b7PbH.jpg" alt="enter image description here"></p>

<p><img src="https://i.sstatic.net/uDiKp.jpg" alt="enter image description here"></p>

<p>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.$$</p>

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

CC BY-SA 3.0
2012-11-16T00:09:48.400Z
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
CC BY-SA 3.0
2012-11-16T00:24:00.047Z
@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
CC BY-SA 3.0
2012-11-16T03:27:07.360Z
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**!
Jeffε
CC BY-SA 3.0
2012-11-16T05:44:53.817Z
@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
<graph-theory><co.combinatorics><network-modeling><ni.networking-internet>
Decomposing Graph Flow (Solution exists?)
Mustafa
# Decomposing Graph Flow (Solution exists?)

(Asked by: username_0 on 2012-11-15)

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](https://i.sstatic.net/b7PbH.jpg)

![enter image description here](https://i.sstatic.net/uDiKp.jpg)

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 ?

**Tags:** graph-theory, co.combinatorics, network-modeling, ni.networking-internet

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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...  
> **username_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**!  
> **username_0**: @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?  

---

## 0 answers

