5
\$\begingroup\$

I have written some code to practise graphs. Graph is represented as vector<list<int>> . Would you share some feedback with me? Are algorithms correct and perform well?

I implemented graph using vector<list<>> because of the name "adjacency lists". However now I think using unordered_map would be cleaner and would perform better, right? I plan to modify it later with a tamplate.

graph.h

#include <vector>
#include <list>
#include <iostream>
#include <iterator>
#include <queue>
#include <stack>

class Graph {
public:
    Graph(): numOfVert {}, adjacencyLists {} {}
    Graph(int n): numOfVert {n}{
        adjacencyLists.resize(n);
    }
    void addEdge(std::pair<int,int> p);
    void topoSort();
    void DFS(int start);
    void BFS(int start);
    void print();
private:
    int numOfVert;
    std::vector<std::list<int>> adjacencyLists;
};

void Graph::addEdge(std::pair<int,int> p){
    if(p.first >= numOfVert || p.second >= numOfVert){
        numOfVert = p.second > p.first ? p.second + 1 : p.first + 1;
        adjacencyLists.resize(numOfVert);
    }
    adjacencyLists[p.first].push_back(p.second);
}

void Graph::print(){
    for(unsigned i = 0; i != adjacencyLists.size(); ++i){
        std::cout << i << " | ";
        std::copy(adjacencyLists[i].cbegin(), 
                adjacencyLists[i].cend(), 
                std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }
}

void Graph::DFS(int start){
    std::cout << "DFS: ";
    std::vector<int> visited(numOfVert, 0);
    std::stack<int> s; s.push(start);
    while(!s.empty()){
        int curr = s.top(); s.pop();
        std::cout << curr << " ";
        for(const auto x: adjacencyLists.at(curr)){
            if(visited.at(x) == 0){
                s.push(x);
                visited.at(x) = 1;
            }
        }
    }
    std::cout << "\n";
}

void Graph::BFS(int start){
    std::cout << "BFS: ";
    std::vector<int> visited(numOfVert, 0);
    std::queue<int> q; q.push(start);
    while(!q.empty()){
        int curr = q.front(); q.pop();
        std::cout << curr << " ";
        visited.at(curr) = 1;
        for(const auto x: adjacencyLists.at(curr)){
            if(visited.at(x) == 0){
                q.push(x);
                visited.at(x) = 1;
            }
        }
    }
    std::cout << "\n";
}

void Graph::topoSort(){
    std::vector<int> incom_rank (numOfVert, 0);
    std::queue<int> next;
    std::queue<int> sorted;
    // create array of incoming edge rank
    for(unsigned i = 0; i != adjacencyLists.size(); ++i){
        for(const auto x: adjacencyLists.at(i)) ++incom_rank.at(x); 
    }
    // populating queue next 
    for(unsigned i = 0; i != incom_rank.size(); ++i){
        if(incom_rank.at(i) == 0) next.push(i); 
    }
    while(!next.empty()){
        int curr = next.front(); next.pop();
        sorted.push(curr);
        for(const auto x: adjacencyLists.at(curr)){
            --incom_rank.at(x);
            if(incom_rank.at(x) == 0) next.push(x); 
        } 
    }
    // print out toposorted graph
    std::cout << "TSort: ";
    while(!sorted.empty()){
        std::cout << sorted.front() << " ";
        sorted.pop();
    }
}

main.cpp

#include "Graph.h"
#include <set>

int main(){
    Graph g(10);
    std::set<std::pair<int,int>> E {{0,2},{1,3},{2,3},{2,4},{4,5},{3,5},{5,6},
                                    {6,7},{5,10},{7,12},{11,12},{8,9},{9,10},
                                    {10,11},{12,13}};
    for(auto& x: E) g.addEdge(x);
    g.print();
    g.topoSort();
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.