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(); g->to_some_arc_rework(A,B); int *t2 = g->t_sort(); if (compare(t1,t2)) printf("cool\n"); else 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.