# topo\_sort() algorithm **URL:** \ **Category:** Usage\ **Tags:** R\ **Created:** [2 August 2021 18:33 UTC](https://igraph.discourse.group/t/topo-sort-algorithm/806 "2021-08-02T18:33:39Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![raimy](https://avatars.discourse-cdn.com/v4/letter/r/71c47a/32.png) [@raimy](https://igraph.discourse.group/u/raimy)\ **Post date:** [2 August 2021 18:33 UTC](https://igraph.discourse.group/t/topo-sort-algorithm/806/1 "2021-08-02T18:33:39Z")
Hi All, Does anyone know what algorithm the topo\_sort() function in the igraph 1.2.6 R package uses to determine the one outputted sort? From the wikipedia page on topological sort: > **[Topological sorting](https://en.wikipedia.org/wiki/Topological_sorting)** > > In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is ... I’m guessing it is either Kahn’s algorithm or depth first. Can anyone confirm/deny what algorithm is used. Thanks in advance and maybe I got this posted in the right forum since I’m a new user. Eric ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [3 August 2021 20:22 UTC](https://igraph.discourse.group/t/topo-sort-algorithm/806/2 "2021-08-03T20:22:40Z")
Can you explain why you want to know this, and to what application you believe it makes a difference? Note that igraph does not guarantee that the underlying algorithms won’t change between versions. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [3 August 2021 20:32 UTC](https://igraph.discourse.group/t/topo-sort-algorithm/806/3 "2021-08-03T20:32:36Z")
The implementation is here: > At a cursory glance, it appears to follow the same steps as in Kahn’s algorithm, as described in Wikipedia. ---
**Author:** ![raimy](https://avatars.discourse-cdn.com/v4/letter/r/71c47a/32.png) [@raimy](https://igraph.discourse.group/u/raimy)\ **Post date:** [4 August 2021 00:19 UTC](https://igraph.discourse.group/t/topo-sort-algorithm/806/4 "2021-08-04T00:19:46Z")
Thank you very much for the follow up response to my question. Its truly appreciated. Now to answer your question… I am a phonologist (linguist who studies sound patterns in human language) with a particular research interest in the application of directed graphs as representations of words in human language. I am currently working on a project where there are words that have parallel paths of letters that need to be sequenced in a particular order. Topological sorting is a proxy for this process so I was curious as to how the topo\_sort() function in R would work. It turns out that it produced ‘the answers’ that were ‘correct’. This caused me to question what algorithm was being used to do the sort since I was aware that there could be multiple different sorts. Knowing what algorithm was used would allow me to better understand what was happening. I’ve attached/imbedded/somethinged… a fairly representative directed graph that I’m interested in. They are sparse, small, and very simple as compared to ones that are interesting to CS but that’s human language. The sort that is ‘correct’ for the graph is [katab]. This is what was produced. Testing other example graphs produced 'correct results too. In the end, topological sorting won’t work in the long run for my project because: (1) there are cyclic graphs that must be sequenced (2) some nodes in parallel graphs need to be merged into single nodes in the output sequence any suggestions on flow algorithms (I think that is what I’m looking for) would be very helpful. tl;dr I was interested because the output of the sort was what I was looking for and wanted to know which algorithm gave me the ‘right answer’ Let’s hope my newbie status got the image embedding correct… we’ll see… ![katab](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/915415480e5a1ad2dd42c9ed6f92f07d44666579.png) ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [4 August 2021 07:49 UTC](https://igraph.discourse.group/t/topo-sort-algorithm/806/5 "2021-08-04T07:49:33Z")
I just wanted to note that _which_ result you get out of the many possible ones depends not only on the algorithm, but also on the representation of the graph. The same graph can have several different representations on the computer (for example, different vertex and edge orders). Here’s a short example (using igraph’s Mathematica interface) that shows different outputs for different representations (`g1` and `g2`) with different algorithms (`toposort` is igraph, `TopologicalSort` is Mathematica’s built-in implementation). ```auto In[35]:= Needs["IGraphM`"]; In[36]:= toposort[g_] := VertexList[g][[IGTopologicalOrdering[g]]] In[37]:= g1 = IGShorthand["0->k->t->b->1,0->a1->a2->1"]; g1 // toposort Out[38]= {0, "k", "a1", "t", "a2", "b", 1} In[39]:= g1 // TopologicalSort Out[39]= {0, "a1", "a2", "k", "t", "b", 1} In[40]:= g2 = IGShorthand["0->a1->a2->1,0->k->t->b->1"]; g2 // toposort Out[41]= {0, "a1", "k", "a2", "t", "b", 1} In[42]:= g2 // TopologicalSort Out[42]= {0, "k", "t", "b", "a1", "a2", 1} ``` (Mathematica’s built-in must be using a different algorithm.) ---
**Author:** ![raimy](https://avatars.discourse-cdn.com/v4/letter/r/71c47a/32.png) [@raimy](https://igraph.discourse.group/u/raimy)\ **Post date:** [5 August 2021 01:54 UTC](https://igraph.discourse.group/t/topo-sort-algorithm/806/6 "2021-08-05T01:54:08Z")
Yes, this is absolutely correct and actually a feature rather than a bug. There is independent evidence from the morphosyntax about the order of adding different pieces of the graph that is sorted. Noticing this was one of the main reasons for my original inquiry. I wanted to make sure I understood what algorithm the R version was using so I could understand the ordering effect. If I could put in any order of pieces of the graph and got the same answer, I would not have been interested. Same goes if I got the wrong answers with the right order. Thank you for helping me with this question. Let me know if you have any other questions.