I have a tree and for its each edge, I want to know the numbers paths passing through this edge.
For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (4,6)] Number of paths for each edge:
(1,2)-> 5
(2,3)-> 5
(2,4)-> 9
(4,5)-> 5
(4,6)-> 5
I am not able to think of any algorithm other than brute force (enumerating all paths of tree).
Please provide any linear/quadratic method.
The answer mentioned above is $\mathcal{O}(N)$ for ONE edge but doing it for each one will make it $O(N^2)$.
Although we can compute the answer in O(N) total for all the edges.
I've added pseudocode for the algorithm at the end.
Steps:
1) As we have a tree, we can root it at some node, say node 1.
2) Run a dfs and compute an array subtreeSize[], where subtreeSize[i] gives the size of the subtree rooted at node i,(Subtree of a node x contains node x as well as all those nodes which passes through x to reach the root in shortest path).
[I've added the pseudocode for computing subtreeSize array at the end]
3) Now that we have this array computed, for each edge {u,v} we know for sure either of these is a parent and other is the child. Lets say u is parent and v is its child. Now let A = subtreeSize[v], then answer for this edge will be (N - A) * (A).
Why? Because we have these two sets of nodes, lets say we remove the {u,v} edge then the we'll get 2 trees, say all nodes in u side are in set X and all nodes in v side are in set Y. Then we can see that for each node in set X we can make a path to each node in set Y that crosses the {u,v} edge. So total number of paths will be = |X| * |Y|, (|setS| = size of setS). You can achieve this whole step in the same dfs if you notice closely whie computing subtreeSize
pseudocode for the complete O(N) algorithm:
dfs(node, parent):
subtreeSize[node] = 1
for each child c of node do:
dfs(c, node)
subtreeSize[node] = subtreeSize[node] + subtreeSize[c]
answerForEdge[node and parent] = (N - subtreeSize[node])*(subtreeSize[node]) // N is the total number of nodes
return
If the edge is, say, {u,v}, it seems to me that you should be able to do a BFS from u (not including v) and a BFS from v (not including u).
From the BFS from u (omitting v), count the number of vertices you visit and add one to it (for u). This should be the number of paths leading to the u end of the edge (including the trivial path of just starting at u). Call this n(u).
Do the same thing from v (omitting u): count the number of vertices you visit and add one to it (for v). This will be the number of paths leading to the v end of the edge (including the trivial path of starting at v). Call this n(v).
Then you can simply multiply these together to get all the paths passing through edge {u,v}: the product is basically picking a path to u (of which there are n(u) such paths) and then picking a path to v (of which there are n(v) such paths).
BFS, on a tree, runs in O(V), where V is the number of nodes in the tree, so two BFS algorithms also run in time O(V) as well: thus, the algorithm is linear in the number of vertices. Indeed, since the double BFS visits every vertex exactly once, it can be done in V steps precisely.
You'll note that this works with your example: for instance, if we take {2,4}, starting a BFS at 2 gives us 2 vertices, namely 1 and 3, so:
n(2) = 2 + 1 = 3.
(Remember we add 1 for vertex 2 itself.)
Then, starting a BFS at 4 also gives us 2 vertices, namely 5 and 6, so:
n(4) = 2 + 1 = 3
(Remember that we add 1 for vertex 4 itself.)
Thus, the total number of paths through edge {2,4} is:
n(2) * n(4) = 3 * 3 = 9.
