Implementation 1

Implementation

void erase(Node &n, Graph &g)
{
    if (g.graph.find(n) == g.graph.end()) { 
        cout << "Node does not exist" << endl; return; 
    }
    g.graph.erase(n);

    for (auto &i : g.graph) {
        if (i.second.find(n) != i.second.end()) {
            i.second.erase(n);
        }
    }
}

vector<string> top_ordering(Graph g)
{
    vector<string> t_order;
    t_order.reserve(g.graph.size());
    bool stop = false;
    while (!stop) {
        stop = true;
        for (auto i : g.graph) {
            if (i.second.empty()) {
                stop = false;
                t_order.push_back(i.first.id);
                erase(const_cast<Node&>(i.first), g);
                break;
            }
        }
    }

    if (!g.graph.empty()) {
        cout << "No topological ordering exists" << endl;
        return vector<string>();
    }
    else return t_order;
}

A Few Remarks/Thoughts

• I initially passed not my reference because I didn't want to mess with graph internally.

• Can be used to validate if a graph as a cycle, although this will be slow. Time complexity for this is:$(O(|V|) + O(|V|))^2$