How to determine if a path exists between 2 vertices in BGL

Question

I want to use the Boost Graph Library to decide if there is a path between 2 nodes on an directed unweighted graph.

Therefore I try to use either Breath-First-Search or Dijkstra but I got confused by all these parameter lists.

What is the simplest way to create a function like this:

bool isPath(src,dest);

with BGL?

I think BFS is the simplest way to do it. Have a look at this [question](http://stackoverflow.com/questions/14470566/how-to-traverse-graph-in-boost-use-bfs). You need only implement `discover_vertex`. — pbible, Mar 09 '15 at 20:17

score 2 · Answer 1 · answered Mar 09 '15 at 23:33

BFS/DFS is the simplest way. I'll sketch up DFS solution because it's less memory hungry.

Presuming you have adjacency matrix adj of size N x N (N being number of vertices in a graph) with:

1 in adj[i][j] if you have edge going from i vertex to j vertex,
0 otherwise.

In that case you could have something like this:

// doing DFS...
bool isPath(int src, int dest) {
  bool visited[N] = {false};
  visited[src] = true;
  std::stack<int> next;
  next.push(src);

  while(!next.empty()) {
    int cv = next.top();
    next.pop();

    for (int nv = 0; nv < N; ++nv) {
      if (!visited[nv] && adj[cv][nv] == 1) {
        visited[nv] = true;
        next.push(nv);
      }
    }
  }
  // dest was reached from src?
  return visited[dest];
}

How to determine if a path exists between 2 vertices in BGL

1 Answers1