9
$\begingroup$

Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, due to the possibles cycles.

This question is slightly different, or at least I think.

INPUT: Be G a directed graph. G can have cycles and also selfconnected nodes. Let A(G) be the adjacency matrix of G (with a 1 in Gi,j if there's a link going from i to j and a 0 otherwise). Define T and B two subset of nodes of G, possibly with void intersection.

OUTCOME: A list of all paths of length at most k going from one node in T to one node in B. Paths can contain multiple time the same edges, as long as they go from the source node to the target node in strictly less than k+1 steps.

QUESTION: I would like to know which algorithm perform best in this task. I'm trying to develop a possible answer based on the fact that the n-th power of the adjacency matrix, if computed symbolically (with a different variable for each entry instead of a 1), keep traks of all this paths (and it reduces to the counting of paths if computed numerically with 1 in the entries). But I really don't know if this is the fastest way of doing the task (probably not).

CAVEAT: I'm not asking for the counting problem, nor for the shortest paths, the length of a path is defined as the number of edges used (counting the repetition). I'm using R, but if you prefer think about it in any other language! I'm really sorry if the question was already posed and solved. Thank you for the kind help!

additional info: I tried a matrix power series approach (A^3 gives all the 3 long path, ...) and dfs / bfs. I think the latter two are far from optimality as they don' take into account that I'm working on sets of sources and targets, and hence do a lot of redundant work...

Improve this question
$\endgroup$
3
  • $\begingroup$ Hi there! Are you still interested in multiplying the matrices symbolically in R? $\endgroup$
    – Ferdinand.kraft
    Commented Apr 1, 2013 at 0:31
  • $\begingroup$ Yep, although it is more stringlike that symbolically (see the question in stackoverflow). Thanks. $\endgroup$
    – gvdr
    Commented Apr 1, 2013 at 0:59
  • $\begingroup$ Then see my answer at Stackoverflow. $\endgroup$
    – Ferdinand.kraft
    Commented Apr 1, 2013 at 18:41

1 Answer 1

Reset to default
7
$\begingroup$

If I am not missing something about your question, you can apply the standard trick for reducing the question about multiple sources and destinations to the case of single source and single destination:

  1. Add two new nodes $s$ and $t$,
  2. Connect $s$ to all sources,
  3. Connect all destinations to $t$.

After this reduction we are in the standard question setting with two extra vertices $s$ and $t$ and we want to find walks from $s$ to $t$ of length at most $k+2$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ How couldn't I see the trick? That's just make the work, after it it all seems pretty much straightforward. $\endgroup$
    – gvdr
    Commented Apr 1, 2013 at 0:17
  • 1
    $\begingroup$ You can also use the matrix powering approach directly on the original adjacency matrix: $(A^k)_{ij}$ is the number of paths of length $k$ from $i$ to $j$. $\endgroup$
    – Yuval Filmus
    Commented Apr 1, 2013 at 4:58
  • $\begingroup$ @YuvalFilmus, as said I'm not counting the paths, but actually finding them. Hence I can't simply use the matrix powering, but a "string" version of that. $\endgroup$
    – gvdr
    Commented Apr 1, 2013 at 5:20
  • 2
    $\begingroup$ @Yuval Filmus: Yuval is right! When he refers to the "number of paths" this should not be understood as for solving the problem of counting them but just to know what index to look at in the preceding adjacency matrix $A^{k-1}$. If $\left(A^k\right)_{ij}=1$ then search backwards in dfs or bfs examining all nodes $\left(A^{k-1}\right)_{i\omega}=1$ if and only if $\left(A^{k-1}\right)_{\omega j}$ also equals 1 $\endgroup$
    – Carlos Linares López
    Commented Apr 3, 2013 at 7:54
  • $\begingroup$ Sorry Carlos, I missed your answer. $\endgroup$
    – gvdr
    Commented Jun 18, 2013 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.