• Articles
• Topological Sort of Strings- part I
Jul 27, 2014 (last update: Nov 7, 2014)

# Topological Sort of Strings- part I

Well, I wonder how a compiler finds out dependencies in a header file( one headers needs another and another needs the other and blah blah blah). So let's say -

``` We have 4 headers named "A", "B", "C" and "D"
--> "A" depends on "B" and "C"
--> "B" depends on "D"
--> "C" doesn't depend on anyone
--> "D" depends on "C"
```

Here's our problem- How all these headers will be sorted so that before including a header all it's dependencies will be met. And here comes topological sorting. We should sort them like this -

```C -- D -- B -- A
```

So now all dependencies will be met !

Here's how I did that -

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687`` ``````#include #include #include #include using namespace std; class StringTopoSort { public : StringTopoSort(vector [],int); ~StringTopoSort(); vector string_topo_sort(); private : void visit(int index); int len; vector * str_lists; vector unsorted; vector sorted; vector * digit_eq; vector digit_sorted; vector is_visited; }; StringTopoSort :: StringTopoSort(vector * _str_lists,int _len) { str_lists = _str_lists; len = _len; digit_eq = new vector[len]; for(int i =0; i::iterator it = str_lists[i].begin(); it :: iterator index = find(unsorted.begin(),unsorted.end(),*it); if(index != unsorted.end() ) digit_eq[i].push_back(index-unsorted.begin()); } } } StringTopoSort :: ~StringTopoSort() {} vector StringTopoSort :: string_topo_sort() { for(int i =0;i::iterator i = digit_eq[index].begin(); i headers[] = {{"A","B","C"},{"B","D"},{"C"},{"D","C"}}; StringTopoSort sorter(headers,4); vector sorted = sorter.string_topo_sort(); for(int i =0; i

And here we go -

 ``` C -- D -- B -- A -- ```

The StringTopoSort doesn't need c++11, but the declaration of headers here needs
this. So you have to compile it by -

```g++ main.cpp -std=c++11
```