Calculate the accumulated flow in a directed graph

user_16224640 0
Viewed 246

Directed Graph

I have a directed graph that ends at point "L". When I sum all the incoming degrees at point "L", I got the value: 13. But I want to modify the graph based on the given plot (see the figure). In the graph, the incoming degree will be distributed in the following nodes. For instance, the incoming degree of point "F" is 2 therefore the value for "F" is 2. But in the case of point "K" and "G", the value will be 0.5 and 0.5, because the value of "H" is distributed into two parts. The value of point "J" will be the sum of the incoming values from the upper nodes (i.e., G, E, F).

A solution in R or python is desired.

This is the sample code that I used...

library(igraph)
library(dplyr)
g1<- graph (edges = c("A","E", "E","I", "I","L", "E","J", "J","L", 
"B","F", "C","F", "F","J", "D","H", "H","K", "H","G", "G","J", "K","L"), 
directed = T)
cum_deg <- data.frame(name=names(V(g1))) %>%
        mutate(deg_1=degree(g1, mode="in")) %>%
        mutate(cum_degree = rowSums 
        ((!is.infinite(distances(g1,mode="in"))) %*% diag (deg_1)))

        > cum_deg
         name deg_1 cum_degree
         A     0          0
         B     0          0
         C     0          0
         D     0          0
         E     1          1
         F     2          2
         G     1          2
         H     1          1
         I     1          2
         J     3          8
         K     1          2
         L     3         13
networkx igraph graph r python
2 Answers

A possible solution is using all_simple_paths to "split" the graph and then aggregate the paths with cumulative weights, e.g.,

# all source vertices
vs <- V(g1)[degree(g1, mode = "in") == 0]
# all sink vertices
vt <- V(g1)[degree(g1, mode = "out") == 0]
# cumulative weights along each simple path
df <- do.call(
    rbind,
    lapply(
        unlist(sapply(
            vs,
            function(x) all_simple_paths(g1, x, vt)
        ),
        recursive = FALSE
        ),
        function(s) {
            stack(
                replace(
                    cumprod(
                        replace(
                            1 / degree(g1, s, mode = "out"),
                            length(s),
                            1
                        )
                    ),
                    1,
                    0
                )
            )
        }
    )
)
# aggregate weights
out <- rev(stack(xtabs(df)[order(names(V(g1)))]))

gives

> out
   ind values
1    A    0.0
2    B    0.0
3    C    0.0
4    D    0.0
5    E    1.0
6    F    2.0
7    G    0.5
8    H    1.0
9    I    0.5
10   J    3.0
11   K    0.5
12   L    4.0
user_121587570

Another possible solution in Python is based on the preliminary calculation of sink and tank nodes, namely nodes with no incoming/outgoing edges, respectively.

Using igraph, you can do it on your graph g:

sink=g.vs.select(_indegree=0)["name"]
tank=g.vs.select(_outdegree=0)["name"]

Then initializing a variable, ready_nodes, which will contain the nodes with the flow computed in each iteration and initializing it to flow=1 for each sink nodes:

ready_nodes = {sink[i]: 1 for i in range(0, len(sink))}

you can call, recursively the following function:

def get_score(node_name:str, ready_nodes:list):
    if node_name in ready_nodes:
        return ready_nodes[node_name]
    else:
        curr_node = g.vs.find(node_name)
                
        # get neighbor nodes
        neighbors_idx = g.neighbors(curr_node, mode="in")
        neighbors_names = g.vs[neighbors_idx]["name"]
        display(f"The neighbors of {node_name} are {neighbors_names}")

        this_node_score = 0
        for j in range(0, len(neighbors_names)):
            this_node_score += get_score(neighbors_names[j], ready_nodes)

        # divide the score by the number of outgoing edges if this node is not a tank node
        if curr_node.outdegree() > 0:
            this_node_score /= curr_node.outdegree()

        display(f'The outgoing flow from node {curr_node["name"]} is: {this_node_score}')
        ready_nodes[node_name] = this_node_score
        return this_node_score

from this for loop:

for i in range(0, len(tank)):
    t_name = tank[i]
    
    display(f"The flow to {t_name} is {get_score(t_name, ready_nodes)}")

to get things done.

The neighbors of L are ['I', 'J', 'K']
The neighbors of I are ['E']
The neighbors of E are ['A']
The outgoing flow from node E is: 0.5
The outgoing flow from node I is: 0.5
The neighbors of J are ['E', 'F', 'G']
The neighbors of F are ['B', 'C']
The outgoing flow from node F is: 2.0
The neighbors of G are ['H']
The neighbors of H are ['D']
The outgoing flow from node H is: 0.5
The outgoing flow from node G is: 0.5
The outgoing flow from node J is: 3.0
The neighbors of K are ['H']
The outgoing flow from node K is: 0.5
The outgoing flow from node L is: 4.0
The flow to L is 4.0

You can browse the solution in this colab sheet

user_94094250
Related