2

I'm trying to list all the paths in an undirected graph, and my question is similar to this question. I've tried to run this code, but it loops indefinitely -- I ran it with 60 nodes. Any ideas on how to produce the correct solution?

I added such a random graph and the code is now like:

    #include<stdio.h>

static struct {
  int value1;
  int value2;
  int used;
} data[] = {
  { 1, 2 },
  { 1, 5 },
  { 2, 3 },
  { 2, 6 },
  { 3, 7 },
  { 4, 0 },
  { 0, 4 },
  { 7, 3 },
  { 2, 1 },

};

enum { DATA_SIZE = sizeof data / sizeof *data };

static int output[DATA_SIZE];

int traverse(int from, int to, int depth) {
  output[depth++] = from;

  int i;
  if (from == to) {
    for (i = 0; i < depth; i++) {
      if (i) {
        printf("-");
      }
      printf("%d", output[i]);
    }
    printf("\n");
  } else {
    for (i = 0; i < DATA_SIZE; i++) {
      if (!data[i].used) {
        data[i].used = 1;

        if (from == data[i].value1) {
          traverse(data[i].value2, to, depth);
        } else if (from == data[i].value2) {
          traverse(data[i].value1, to, depth);
        }

        data[i].used = 0;
      }
    }
  }
}

int main() {
  traverse(1, 7, 0);
}`

And the output is: 1-2-3-7 1-2-3-7 1-2-3-7 1-2-3-7

Why do I get that path 4 times? Is it possible to fix? thanks

Community
  • 1
  • 1
user2147241
  • 53
  • 1
  • 9
  • Are you trying to find all the paths between all the nodes in the graph or all the possible paths between two given nodes? For the later, check out the simple Python implementation presented in http://www.python.org/doc/essays/graphs/, which is trivial to translate to C++. – Escualo Jul 29 '13 at 20:45
  • 4
    Does it work on a smaller graph, say 4 nodes? Or 10 nodes? Depending on how the graph is connected, you could be looking at up to 1.1 **quintillion** paths. If you could some how calculate 1 billion paths per second, it would take 877 years to execute. Some more information on your problem's constraints would be nice. – Shaz Jul 29 '13 at 20:46
  • 1
    Hint: google for "Dynamic programming" – STT LCU Jul 29 '13 at 20:51
  • I am trying to get all the paths between two nodes. – user2147241 Jul 30 '13 at 00:22
  • You have edges (1,2) and (3,7) twice, this makes 4 paths that look the same. – n. m. could be an AI Jul 31 '13 at 05:20
  • But there are two edges between 1 and 2, and 3 and 7, which means there is an undirected arc. So, I have to include them. Is there any need for modification in the code? – user2147241 Jul 31 '13 at 05:32
  • Your graph is undirected. The code does not distinguish between (a,b) and (b,a) edges. If you want a directed graph, you need to modify the code. – n. m. could be an AI Jul 31 '13 at 05:58
  • I need some suggestion to modify it. I couldn't figure it out. any hints? – user2147241 Jul 31 '13 at 06:01

2 Answers2

3

You can not fix it. The number of paths in graph (not counting sparse graphs) is exponential by itself and only outputting will take forever. Clearly, it's impossible. Even if your graph is sparse (but connected) there will be at least O(N^2) paths.

sasha.sochka
  • 14,395
  • 10
  • 44
  • 68
0

As I understand the algorithm you link to, it will visit the same vertex multiple times (it will not visit the same edge multiple times, though). This means that the maximum length of one path is proportional to the number of edges in your graph, not the number of nodes. You say your graph has 60 nodes - how many edges? If that number is very large, then it may run for a very long time to produce even a single path.

You could modify the algorithm slightly to only visit each node once, but that may not be what you're looking for.

JoshG79
  • 1,685
  • 11
  • 14