#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    1
    Rep 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.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    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).
    Last edited by b49P23TIvg; November 23rd, 2012 at 05:47 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo