All Paths

Given a txt file that consists of graph data, output all the possible paths that begin and end with the first two characters in the first line of the file.

Consider the following Graph:

12
A : C, G
G : I, H
I : G
H : I, K
D : H, E
C : F, E, D
B : C
F : E
L : M

-------------------

A->C;
A->G;

G->I;
G->H;

I->G;

H->I;
H->K;

D->H;
D->E;

C->F;
C->E;
C->D;

B->C;

F->E;

L->M;

Implementation

void all_paths_rec(Node src, const Node &dest,
                   vector<Node> &temp, vector<vector<Node>> &main,
                   unordered_set<Node> &cur_path, Graph &g)
{
    cur_path.insert(src);
    temp.push_back(src);

    if (src == dest) {
        main.push_back(temp);
        temp.pop_back();
        cur_path.erase(src);
        return;
    }

    for (auto &element : g.graph.at(src)) {
        if (cur_path.find(element) == cur_path.end()) {
            // current path does not contain next element
            all_paths_rec(element, dest, temp, main, cur_path, g);
        }
    }

    temp.pop_back();
    cur_path.erase(src);
}

vector<vector<Node>> all_paths(const Node &src, const Node &dest, Graph &g)
{
    if (!g.exists(src) || !g.exists(dest)) {
        cout << "Either src or dest does not exist" << endl;
        return vector<vector<Node>>();
    }
    if (src.id == dest.id) {
        cout << "src is the same as dest" << endl;
        return vector<vector<Node>>();
    }

    vector<Node> temp;
    vector<vector<Node>> all_paths;
    unordered_set<Node> visited;
    all_paths_rec(src, dest, temp, all_paths, visited, g);

    return all_paths;
}

void test(Graph &g)
{
    g.traverse_all();
    cout << "\n\n";
}


int main()
{
    const string filepath = "../old_input_files/graph.txt";
    Graph g(filepath);
    test(g);

    Node src("L"), dest("B");
    vector<vector<Node>> paths = all_paths(src, dest, g);
    print2d(paths);

}

Analysis

• See problem 'All Root to Leaf Paths' as a prerequisite.

• The general idea is to to a depth first traversal through the tree, except this time, it is not the kind of traversal one would normally expect. Typically, we visited each node a single time. To find all paths, each 'thread' of the DFS tree is unique, and should be treated as such. E.g. A->B->C and A->B->E are unique, but carry the same thread A->B.

• To elumate the idea of unique threads, I decided to go with an unordered_map that will keep track of what of the current path I have in my graph. (Just as an FYI, this map would not be needed if the graph did not contain cycles, because the algorithm would be able to exit the for loop on the instance there is no adjacent element, or the destination was found.)

• As I iterate through the paths, I maintain an ordered vector and push back elements. I also keep the unordered_map, and insert elements into it the same instances of the vector. The advantage is that I am able to maintain both order of the path, as well as a constant time lookup to detect if I need to insert the next element in. Its a trade off of space for time.

• Once the destination is found, I remove the latest element in the vector, as well as the the element in the map. I then return to go back to an earlier state in the traversal.

• Because of how the stack is structured, on return the for loop exits and the path isn't repeated again.

• It is not necessary to iterate outside the scope of src (e.g. Nodes L and M), because they are guaranteed to be disconnected anyway, and in no way src can connect to dest if dest is within a disconnected subgraph from src.