All paths between two nodes

Dev Shed Forums Sponsor:

November 22nd, 2012, 07:35 PM

paths000

Registered User

Join Date: Nov 2012

Posts: 1

Time spent in forums: 20 m 36 sec
Reputation Power: 0

All paths between two nodes

Hi everyone, I’m trying to solve problem in which I have to calculate the number of paths from one node to all of other nodes in the directed graph and I have a predetermined length of paths. The problem can be solved by simple recursive function, but the size of the input data precludes this option. Connections between two nodes which appear at the input, can appear more then once and we treat them as a different connections.

Code:

N, M, K (1<=N<=40, 1<=M<=100000, 1<K=10^1000), where n is number of nodes, m is number of connections and k is length of paths.

Example:

Code:

Input:
4 6 2
1 2
2 1
1 1
1 2
2 4
1 3
Output:
3
2
1
2

Explanation:
All possible paths with 2 hops are: (1,1,1), (1,2,1), (1,2,1), (1,1,2), (1,1,2), (1,1,3), (1,2,4), (1,2,4).

The fact is that the number of vertices is very small relative to the number of connections, so in the graph will be many hundreds of cycles. I wonder if somehow can use this fact.
Please, help me.

November 23rd, 2012, 04:44 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,347

Time spent in forums: 1 Month 2 Weeks 3 Days 6 h 53 m 17 sec
Reputation Power: 383

4 6 2 are your m n k
The pairs are directed paths.

All possible paths with 2 hops starting from node 1 are:
(1,1,1), (1,2,1), (1,2,1), (1,1,2), (1,1,2), (1,1,3), (1,2,4), (1,2,4)

Let G be the matrix connectivity matrix, where the connections are the count of like paths. (I've named my "G" noun as "GRAPH.)

Code:

   ('G';'  TO'),:(,.'FROM');GRAPH
┌─┬───────┐
│G│  TO   │
├─┼───────┤
│F│1 2 1 0│
│R│1 0 0 1│
│O│0 0 0 0│
│M│0 0 0 0│
└─┴───────┘

I assert that the number routes from one node to another given a path length N is G to the power of N. It works for path length 1 and 2!

Code:

   +/ .*~GRAPH     NB. Path length 2, G dot G
3 2 1 2
1 2 1 0
0 0 0 0
0 0 0 0

The first row gives the number of paths from node 1 to nodes 1 2 3 and 4. You see that 3 2 1 2 is the expected result. Also you can't get anywhere starting from nodes 3 and 4, that checks, and the paths length 2 from node 2 to the other nodes is verified.

You don't need to explicitly find each path. You'll need to add and multiply numbers that have more base 10 digits than there are atoms in the universe (assuming your caret in 10^1000 meant power instead of exclusive or).

__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : November 23rd, 2012 at 04:47 PM.

All paths between two nodes

Developer Shed Advertisers and Affiliates