gistfile1.cpp

#include <iostream>
#include <fstream>
#include <vector>

#include "utilities/Graph.h"

using namespace std;

vector<pair<int,int>> maxRevenuePath(Graph<int>* g);

int main() {
    
    Graph<int>* g = new Graph<int>("Q3_2.txt");
    
    cout << "Adjacency List: "<< endl;
    g->display();
    
    auto path = maxRevenuePath(g);

    int totalRevenue = 0;
    cout << "The path is as follows:" << endl;
    for (int i = path.size()-1; i >= 0; --i) {
        cout << path[i].first << "\t";
        totalRevenue += path[i].second;
    }
    cout << g->numVertices-1 << endl;   // Last vertex (n-th toll plaza)
    cout << "The total revenue for this path is: " << totalRevenue << endl;
    
    return 0;
}

/*
*   The algorithm works on a reverse adjacency list
*   which contains incoming edges instead of outgoing ones
*   This is constructed in O(V+E) time. 
*   
*   This list is traverses in O(V+E) time maintaining
*   a record of the most valuable path to a particular vertex
*   in an array 'maxInto'. 
*   
*   After the traversal, this array is backtracked in such a 
*   way that we jump from a vertex to the one before it with the highest 
*   value path until we reach toll-booth 0.
*   This backtracking results in the final path.
*
*   This entire algorithm takes O(V+E) time
*   and O(V+E) space for reverse adjacency list and O(V) for 'maxInto'
*   for a total of O(2V+E) space complexity.
*/
vector<pair<int,int> > maxRevenuePath(Graph<int>* g) {
    
    vector< pair<int,int> > reverseList[g->numVertices];

    for(int i = 0; i < g->numVertices; ++i) 
        for (auto& e : g->adjacencyList[i]) 
            reverseList[e.first].push_back(make_pair(i, e.second));

    // cout << "Reverse List: "<< endl;
    // for(int i = 0; i < g->numVertices; ++i) {
    //     cout << i << ": ";
    //     for (auto& e : reverseList[i])
    //         cout << e.first << ";" << e.second << ", ";
    //     cout << "\b\b " << endl;
    // }

    pair<int,int> maxInto[g->numVertices];
    for (auto& e : maxInto)
        e = make_pair(-1, -1);  // dummy value to signify node not on path
    maxInto[0].second = 0;

    for(int i = 0; i < g->numVertices; ++i) {
        if (reverseList[i].size() == 0 && maxInto[i].second == -1) 
            // No incoming edges to this vertex
            continue;
        // Find max path into this vertex
        for (auto& e : reverseList[i]) {
            if (e.second > maxInto[i].second && maxInto[e.first].second != -1) {
                maxInto[i] = e;
            }
        }
    }

    // for (auto& e : maxInto)
    //     cout << e.first << ";" << e.second << ", ";
    // cout << "\b\b " << endl;

    vector<pair<int,int> > outPath { maxInto[g->numVertices-1] };

    auto current = outPath.back();
    do {
        current = outPath.back();
        auto prev = maxInto[current.first];
        outPath.push_back(prev);
        current = prev;
    } while (current.first != 0);

    return outPath;
}