Topological sort using STL

Question

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]<<" ";
} 

• Toby Speight: Seems to require an input stream on stdin - can you provide a sample input?

Answer 1

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 << " ";
}

Answer 2

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).

Answer 3

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?

• kraskevich: Not any type. Vertex ids are used as indices now, so they should be int-like.