1
\$\begingroup\$

I am trying to implement topological sort using STL. I have used vector of lists to store adjacency list. Indegree is an array which stores indegree of vertices.

Indegree0 is a queue implemented using STL list to store vertices with indegree 0. Can someone please help me improve my code?

# include <iostream>  
# include <bits/stdc++.h>
using namespace std;

vector<int> topologicalsort(vector<list<int> > adjacencylist,int  indegree[],int v,int e) 
{

    vector<int>ans(v+1);
    int k=1;
    //list to store vertices with indegree 0
    list<int>indegree0;
    for(int i=1;i<=v;i++)
    {
        if(indegree[i]==0)
            indegree0.push_back(i);
    }
    while(!indegree0.empty())
    {
        int x=indegree0.front();
        indegree0.pop_front();
        ans[k]=x;
        k++;
        list<int>::iterator itr=adjacencylist[x].begin();
        while(itr!=adjacencylist[x].end())
        {
            indegree[*itr]--;
            if(indegree[*itr]==0)
                indegree0.push_back(*itr);
            itr++;
        }
    }
    return ans;
}

int main()
{
    int v,e;
    cin>>v>>e;
    vector<list<int> > adjacencylist(v+1);
    int indegree[v+1];
    for(int i=1;i<=v;i++)
        indegree[i]=0;
    for(int i=1;i<=e;i++)
    {
        int v1,v2;
        cin>>v1>>v2;
        adjacencylist[v1].push_back(v2);
        indegree[v2]++;
    }
    //cout<<adjacencylist.size()<<endl;
    for(int i=1;i<=v;i++)
    {
        printf("adjacencylist[%d] :",i);
        list<int>::iterator itr=adjacencylist[i].begin();
        while(itr!=adjacencylist[i].end())
        {
            cout<<*itr<<"  ";
            itr++;
        }
        cout<<endl;
    }
    vector<int> ans=topologicalsort(adjacencylist,indegree,v,e);
    for(int i=1;i<=v;i++)
        cout<<ans[i]<<"  ";

}  
\$\endgroup\$
  • 1
    \$\begingroup\$ Seems to require an input stream on stdin - can you provide a sample input? \$\endgroup\$ – Toby Speight Aug 31 '17 at 17:16
4
\$\begingroup\$

Headers and namespaces

#include "bits/stdc++.h"

That's not a standard C++ header; prefer to use standard headers so that others can use your code.

using namespace std;

Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Used but not included: <cstdio>, <vector>, <list>. I'd recommend you stick to one of <cstdio> and <iostream>.

Function signature

std::vector<int> topologicalsort(std::vector<std::list<int> > adjacencylist,
                                 int indegree[], int v,
                                 int e)

Why do you require e? It's never used.

Passing indegree as a pointer and length is very C-style; prefer a C++ range (e.g. a pair of iterators, or a standard container).

There's no need to pass adjacencylist by value: a const-ref is more appropriate.

Result vector

Instead of creating v+1 elements in the result vector and having to keep track of our insert position with k, we can create it empty and push_back each result as we find it. We can avoid reallocation by using reserve().

Looping over elements

Instead of the error prone iterator-based loop, prefer to use range-based for when applicable:

    for (int i: adjacencylist[x]) {
        if (--indegree[i] == 0)
            indegree0.push_back(i);
    }

Variable-length arrays

This is a non-standard extension:

int indegree[v+1];

It's not clear why you ignore the 0th element of these arrays; that probably warrants a comment.


Cleaned code

#include <iostream>
#include <list>
#include <vector>

std::vector<int> topologicalsort(const std::vector<std::list<int>>& adjacencylist,
                                 std::vector<int> indegree)
{
    std::vector<int> ans;
    ans.reserve(indegree.size()+1);
    //list to store vertices with indegree 0
    std::list<int> indegree0;
    for (size_t i = 1;  i < indegree.size();  i++) {
        if (indegree[i] == 0)
            indegree0.push_back(i);
    }
    while (!indegree0.empty()) {
        const int x = indegree0.front();
        indegree0.pop_front();
        ans.push_back(x);
        for (const int i: adjacencylist[x]) {
            if (--indegree[i] == 0)
                indegree0.push_back(i);
        }
    }
    return ans;
}

int main()
{
    int v, e;
    std::cin >> v >> e;
    std::vector<std::list<int>> adjacencylist(v+1);
    std::vector<int> indegree(v+1);
    for (int i = 1;  i <= e;  i++) {
        int v1, v2;
        std::cin >> v1 >> v2;
        adjacencylist[v1].push_back(v2);
        ++indegree[v2];
    }
    for (int i = 1;  i <= v;  i++) {
        std::cout << "adjacencylist[" << i << "%d] :";
        for (int j: adjacencylist[i]) {
            std::cout << j << "  ";
        }
        std::cout << std::endl;
    }
    auto const& ans = topologicalsort(adjacencylist, std::move(indegree));
    for (int i: ans)
        std::cout << i << "  ";
}
\$\endgroup\$
2
\$\begingroup\$

In addition to the other answer:

  1. To make your intent clearer, use std::queue when you need queue. Don't reinvent the wheel. Don't confuse those who read your code.

  2. Iteration over std::list is very inefficient because it lacks memory locality. Don't use it unless you have a very good reason to. Use std::vector as a default container.

  3. Separate the words in variable's names somehow (either using camelCase or underscores). topologicalsort looks sort of gibberish. topological_sort or topologicalSort looks better, doesn't it?

  4. Even if the input and output should have 1-based indexing, I'd still use 0-based indexing in computations. It's more conventional so it makes your code easier to understand (That's the main reason. Saving one element isn't a big deal).

\$\endgroup\$
1
\$\begingroup\$

In addition to the other answers:

Why does the function topological_sort take more than one parameter? It should be able to calculate indegree0 by itself.

Why is it restricted to int instead of allowing any type?

\$\endgroup\$
  • \$\begingroup\$ Not any type. Vertex ids are used as indices now, so they should be int-like. \$\endgroup\$ – kraskevich Sep 1 '17 at 12:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.