I got a DAG (directed acyclic graph) on which I can apply a Tsort algorithm (actually its a modified one which also makes sure to visit each node using an ascending node property) in order to calculate its topological sort.

Due to my application, I have to constantly do changes on the graph (that is changing some incoming and outgoing arcs of some particular verticies) but I want to make sure that doing that I maintain the same topological sort.

The pseudocode of the approach that I got in mind is:

Graph *g = init_graph();
int *t1 = g->t_sort();
int *t2 = g->t_sort();
if (compare(t1,t2))
    printf("not cool\n");

I wanted to ask if there is an existing algorithm, Graph property or a procedure to identify beforehand if a modification on the graph will lead to different topological sortings. If this is not possible any way to at least estimate the subset of the tsort that will be modified, would save quite some time rather than recalculating the whole topological sort from scratch.

  • $\begingroup$ Afaik, a topological sort is such that for every directed arc $u\rightarrow v$, vertex $u$ comes before vertex $v$ in the sort/ordering. If you reverse any arc, you will always change the sort/ordering. Another problem with your question, is that if you revert an arbitrary arc, your DAG may not be acyclic anymore (unless the non-directed graph is itself acyclic). Looking at methods to quickly obtain the new topological sort instead of doing it from scratch seems interesting. $\endgroup$ – N.Bach Jan 30 '18 at 16:32
  • $\begingroup$ Yes you're absolutely right, my bad. I'm not actually reversing arcs, I'm actually changing one incoming and one outgoing edge of a vertex. $\endgroup$ – Greg K. Jan 30 '18 at 16:55

Your Answer

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

Browse other questions tagged or ask your own question.