Is the complexity of this topological sort algorithm O(P+D) where P is projects and D is dependencies?

Question

I have written a topological sorting algorithm in c++ but i am not sure if the complexity is as good as it should be. I know theres a topological sort algorithm that works in O(P+D) time where p is projects and D is number of dependencies, but I am unsure if i wrote it correctly. Can you take a look? Code is below. Any other suggestions on improvement is welcome too, I feel like having 2 lists for adjacency is inefficient and I think there should be a better way to do it.

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

class Graph
{
public:
    Graph(vector<string> projects, vector<pair<string,string>> dependencies)
    {   
        int counter=0;
        for(int i=0;i< projects.size();i++)
        {
            strToInt[projects[i]]=counter++;    
        }
        adjList.resize(projects.size());
        for(int i=0;i<dependencies.size();i++)
        {
            adjList[strToInt[dependencies[i].second]].first.insert(strToInt[dependencies[i].first]);
            adjList[strToInt[dependencies[i].first]].second.push_back(strToInt[dependencies[i].second]);
        }
    }

    vector<pair<unordered_set<int>,vector<int>>> adjList;
    unordered_map<string,int> strToInt;

    bool BuildOrder(){
        vector<int> visited(adjList.size(),0);
        queue<int> q;
        int count =0;
        for(int i=0;i<adjList.size();i++)
        {
            if(adjList[i].first.size()==0)
            {
                count++;
                q.push(i);
            }
        }
        while(!q.empty())
        {
            count++;
            int temp=q.front();
            q.pop();
            visited[temp]=1;
            for(int i=0;i<adjList[temp].second.size();i++)
            {
                adjList[i].first.erase(temp);
                if(adjList[i].first.size()==0&&visited[i]==0)
                {
                    q.push(i);
                }
            }
        }
        if(count==visited.size())
        {
            return true;
        }
        return false;
    }

};

int main()
{
    vector<string> projects {"a", "b", "c", "d", "e", "f"};
    vector<pair<string,string>> dependencies{
        {"a","d"},
        {"f","b"},
        {"b","d"},
        {"f","a"},
        {"d","c"}
    };
    Graph g(projects,dependencies);
    bool temp=g.BuildOrder();
    return 0;
}

Answer 1

I dont totally understand what your code is doing but I think it is implementing Kahn's algorithm. The thing with Kahn's algorithm is that it requires a graph representation in which you can get the in-neighbors and the out-neighbors of a given vertex in the digraph efficiently. To me this makes it too cumbersome to bother with given that a topological sort kind of naturally falls out of a depth-first search of out-neighbors only.

Below is an implementation of the DFS way. I do it with two visited sets like they explain in the Wikipedia article, because that way you do not even need to keep track of the source vertices of the graph, the vertices with in-degree zero, when building the graph -- although if you know the sources the DFS based algorithm is even simpler.

#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using Edges = std::vector<std::pair<std::string, std::string>>;
using Vertices = std::vector<std::string>;
using Graph = std::unordered_map<std::string, std::vector<std::string>>;

Graph BuildAjacencyList(const Edges& edges)
{
    Graph graph;
    for (const auto& edge : edges)
        graph[edge.first].push_back(edge.second);
    return graph;
}

Vertices FindTopologicalOrder(const Vertices& vertices, const Edges& edges)
{
    auto graph = BuildAjacencyList(edges);

    std::unordered_set<std::string> unexplored, visited;
    std::copy(vertices.begin(), vertices.end(), std::inserter(unexplored, unexplored.end()));

    std::deque<std::string> topo_order;
    std::function<bool(std::string)> visit = [&](std::string vert) {
        if (unexplored.find(vert) == unexplored.end())
            return true;
        if (visited.find(vert) != visited.end())
            return false;
        visited.insert(vert);
        for (const auto& neighbor : graph[vert])
            if (!visit(neighbor))
                return false;
        visited.erase(vert);
        unexplored.erase(vert);
        topo_order.push_front(vert);
        return true;
    };

    while (!unexplored.empty())
        if (!visit(*unexplored.begin()))
            return Vertices(); // the dependency graph has a cycle.

    return Vertices(topo_order.begin(), topo_order.end());
}

int main()
{
    std::vector<std::string> projects{ "a", "b", "c", "d", "e", "f" };
    Edges dependencies{
        {"a","d"},
        {"f","b"},
        {"b","d"},
        {"f","a"},
        {"d","c"},
        {"b","e"}
    };

    auto order = FindTopologicalOrder(projects, dependencies);
    if (order.empty()) {
        std::cout << "there is a cycle in these dependencies\n";
    } else {
        for (const auto& vert : order)
            std::cout << vert << std::endl;
    }
    return 0;
}