MousE0910 MousE0910 - 1 month ago 15
C++ Question

Reachable vertices in directed graph made from vector of vectors

I'm working on a simple programming assignment for my studies and I've encountered a problem. The assignment has a predefined header which cannot be modified, so I have to use the structures that are set, making the problem more complicated than it should be.

I need to implement a function that returns a vector of all vertices reachable from the start vertex. That would be a simple task if I could use a more complex structure for it, but the whole graph is represented as a vector of vectors, leaving me stumped with how to do it. Any help would be greatly appreciated.

The graph structure means that for example graph that's

{{1,2,3}, {3}, {3}, {}}
means that vertex 0 leads to vertices 1,2,3; vertex 1 leads to 3, vertex 2 leads to 3, vertex 3 leads nowhere.

graph.hpp

#include <vector>
#include <algorithm>

/*
* Struct representing graph, that is, vertices and edges between the vertices.
* Vertices are identified with indices, where 0 stands for 1st added vertex,
* 1 stands for 2nd added vertex, 2 stands for 3rd added vertex, etc...
*
* The edges between vertices are directed.
*/
struct graph {
std::vector<std::vector<int>> connections;
};

// Other functions manipulating the graph here

/*
* Return vertices that are reachable from given vertex.
* That is, the vertex itself,
all vertices connected to the given vertex,
all vertices connected to these vertices,
etc...
*
* Can only be called with existing vertex.
*/
std::vector<int> reachable_vertices(const graph& g, int vertex);


I've tried a kind of naive brute force approach but it doesn't work.

graph.cpp

#include "graph.hpp"

// Other functions manipulating the graph here

std::vector<int> reachable_vertices(const graph& g, int vertex) {
if (g.connections.size() < vertex) {
return{};
}
std::vector<int> reachables;
for (auto vert : g.connections[vertex]) {
if (vert > vertex) {
reachables = reachable_vertices(g, vert);
}
}
reachables.push_back(vertex);
std::sort(reachables.begin(), reachables.end());
reachables.erase(std::unique(reachables.begin(), reachables.end()), reachables.end());
return reachables;
}

Answer

The frontier starts out with a single node. You take a node from the frontier (if you need cycle detection: and add it to a set of visited nodes). Perform a function on the node. Then take all the nodes that are directly reachable from that node, and add them to the frontier (if you need cycle detection: unless the node has been visited before). Continue until no more nodes left.

Depending on how you "add" nodes to the frontier and how you "take a node" from the frontier this is a description of a whole class of search strategies.

A queue (adding at the end, take from front) will give you a BFS, a stack (adding on top, take from top) will give you a DFS.

"Perform a function" would in your case be "add it to the set of reachable nodes".