aajjbb's blog

Path with pre-determined size in a graph
By aajjbb, 12 years ago, In English

Hi, is it possible to check if there's a path with size from a node 'a' to a node 'b' with size 'N' ? I've tried an BFS approach, using the 'visited' array with integer with a limit in the number 'N', but this strategy didn't worked.

Do you have any idea, or there's a well known algorithm for this ? (I seached, but didn't found anything)

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

O(m) solution for unweighted (__UPD:__ and undirected) graph:
Idea: if three its path of length t, there is path of length t+2(go somewhere and return). Let's find shortest path of length of parity of n. Create vertices (v,0), (v,1) for vertex v, edges (x,0)-(y,1) and (x,1)-(y,0) for edge x-y. Now go bfs from (a,0) to (b, n%1)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't got it, if I want to travel from vertex 1 to vertex N in a path of M steps, how would I create this vertexes (v, 0), (v, 1) and this edges.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can we visit same vertex twice?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Then you need to find shortest path with BFS (let it be d). If d <= m && d % 2 == m % 2, then answer YES, else NO. Why is it so? Shortest path a -> b at the end has some edge (v, a) and if d < m you can go by edge (a, v) and then again by edge (v, a), what results in d = d + 2. So you need to do it while d < m and if parity of d and m are the same, you have answer, otherwise — no.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 4   Vote: I like it 0 Vote: I do not like it

            I've already tried it and didn't worked.. but I'm almost sure this strategy is right. EDIT: My strategy it this one:


            #include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string.h>
#include <stdio.h>

using namespace std;

const int INF = 100000000;
int c, l, a, b, s, e, d, maze[110][110], dist[110], vis[110];

int main(void) {
    while(cin >> c >> l && !(c == 0 && l == 0)) {
        memset(maze, 0, sizeof(maze));
        for(int i = 0; i <= c; i++) {
            dist[i] = INF;
            vis[i] = 0;
        }
        for(int i = 0; i < l; i++) {
            cin >> a >> b;
            maze[a][b] = maze[b][a] = 1;
        }
        cin >> s >> e >> d;
        if(d == 0 && s == e || (s == e && d == 1)) {
            cout << "Yes, Teobaldo can travel." << endl;
            continue;
        }
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        dist[s] = 0;
        while(!q.empty()) {
            int tmp = q.front(); q.pop();
            for(int i = 1; i <= c; i++) {
                if(maze[tmp][i] == 1 && !vis[i]) {
                    dist[i] = dist[tmp] + 1;
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
        if(dist[e] <= d && dist[e] % 2 == d % 2 && !(c == 1 && l == 0 && s == 1 && e == 1 && d != 0) && d != 0) {
            cout << "Yes, Teobaldo can travel." << endl;
        } else {
            cout << "No, Teobaldo can not travel." << endl;
        }
    }
    return 0;
}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Lets look.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                yes, it's unoriented and unweighted, by the way here's the link, the statement is in portuguese but google translate make a good job Link

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Problem in your BFS, you should mark vertex as visited when you look at that not when you get there by bfs. So it must look like something that:

                  while(!q.empty()) {
  int tmp = q.front(); q.pop();
  for(int i = 1; i <= c; i++) {
    if(maze[tmp][i] == 1 && !vis[i]) {
      dist[i] = dist[tmp] + 1;
      vis[i] = 1
      q.push(i);
    }
  }
}
                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I've already tried this strategy, and didn't worked again.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Did you process case when c = 1, l = 0, s = 1, e = 1, d <> 0?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, and it's yet a WA.I can't see one error in this approach. The update code is in the previous comment.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Oh, sorry, man, i've just got, that my solution was wrong. And riadwaw was right: you need to make graph with vertices (v, p) where v is number and p is parity. In this graph you need to find shortes path (s, 0) -> (e, d % 2) . And if it exist you have answer YES otherwise — NO. Don't forget about case where s == e d != 1 and you haven't got any edge from s.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Oh, It was another corner case I was forgetting, but it's yet WA. I've also got another corner, when 'd == 0' there's no possible path since for only being in the starter vertex, it's already count as one node in the path. The new code is in the previous comment.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I didn't got it yet, I should BFS through pairs ? with a starter vertex (s, 0) ? how would I relax it's distance ?

                  → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a undirected and unweighted graph. Build an adjacency matrix for this graph. Raise this square matrix up to the power 'N' and check if the adj[a][b] > 0 because doing so gives you the number of different paths of length N in adj[a][b]. Obviously if adj[a][b] > 0 holds true, there is a path between these two nodes. For multiplication of matrix N times, you could use fast matrix multiplication technique.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It should work with directed graphs to.

    You may use "and" instead of multiplication and "or" instead of sum to avoid overflow

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To make the multiplication for N I should do adj[i][j] ^ N isn't it ? using and and or to avoid overflow, it would be adj[i][j] & N ?

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm looking for matrix multiplication techniques now. s

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With trivial multiplication of matrices you get solution for O(c^3*logd), which is good. So you need just to write function binPow for matrices with trivial multiplication.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I'm yet a newbie in matrix operations, just googling for 'binPow' I've found it, is the definition of the function right ? Link

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, its right. If you want and if it helps you, you can check my code for this problem.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you, I finally got 'AC', I'm still curious how this matrix multiplication find this paths, I'll study more on matrix operations, search more for this problem on the net, I've found this solution which get 'AC' too, LINK. it looks like a weird BFS, but the code is too messy, so it made me more sure that there's also a 'graph' solution(which doesn't use matrix multiplication) to solve this problem.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There is a theorem in Graph theory which states: Consider a graph G with n vertices, consider its adjacency matrix, call it A. Now consider a natural number, like x. Raise A to the power of x to obtain A^x. Then, for each i and j, entry A^x(i, j) contains number of walks from vertex i to vertex j. It can be proved using induction on x. Note that we're calculating it using Dynamic Programming. Base case is trivial, for induction step, consider all walks of length x+1 from i to j. Now consider vertex before j in our walk. Call it u. Obviously, for each u, number of walks of length x+1 from i to j equals to number of walks of length x from i to u, multiplied by number of walks of length 1 from u to j (That is, if they're adjacent in G). By multiplying A^x * A, we're calculating all such walks. Hence we're done. Note : Refer to definition of matrix multiplication for understanding induction step efficiently.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thank you so much, now I've got this approach, but I'll keep studying on matrix multiplication.. but did you saw the code I've paste in the last comment, it looks like a bfs, but the author make so weird stuff inside it, but it made me thought that there's also a solution using BFS. do you know these solution too ?

                → Reply