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:
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
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.
The implementation is here:
At a cursory glance, it appears to follow the same steps as in Kahn’s algorithm, as described in Wikipedia.
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…
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).
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.)
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.