CODEWITHSUNDEEP
c++sortinggraphdirected-acyclic-graphstopological-sort
ChristopherC
ChristopherC

Reputation: 1665

Iterative/Dynamic Topological Sorting for Dummies

I'm currently implementing a dynamic DAG graph in C++—it will be displayed through an UI to the user and insertion/removal of nodes/edges will be common operations.

The size of the graphs might potentially range from the really small scale to the large one—I'm aiming to support millions of nodes.

As such, I'm looking for an optimal data structure that won't take up too much space in memory but also for a way to have fast insertions/removals with a fast multi-threaded iteration over the topologically sorted nodes (so multiple nodes can be executed in parallel).

I haven't done any profiling to see if a naive approach of recomputing a topological sort of the full graph each time a modification is being done would cut it, but for the sake of learning, I thought I'd rather find a “smarter” way.

I've got no idea how to approach the multi-threaded iteration of the graph but for a start I've stumbled upon some papers related to the iterative/dynamic topological sorting step, and the problem is that they're a bit too smart for me to understand. It gets way into the theoretical/mathematical side and lacks concrete implementation examples that could help me to understand what's going on.

Here's an example of a such paper: A Labeling Approach to Incremental Cycle Detection.

Since there's a lack of papers such as “Iterative/Dynamic Topological Sorting for Dummies”, does anyone have any hint on subject?

Upvotes: 5

Views: 2369

Answers (2)

Jason Eisner
Jason Eisner

Reputation: 31

There is indeed work on dynamic toposort.

Pearce & Kelly http://homepages.ecs.vuw.ac.nz/~djp/dts.html have an algorithm that they claim is both simple and practically efficient. They also provide a C++ implementation. By way of introduction, they discuss even simpler variants.

Here is some of the later work on this problem, in chronological order. Later methods tend to be more complicated than earlier ones. Even if not, the later papers may assume that you have already read the earlier ones. You apparently started with the last paper on this list, which might have been jumping into the deep end.

Upvotes: 2

n. m. could be an AI
n. m. could be an AI

Reputation: 120079

The dynamic toposort algorithm (untested).

Start with a topologically sorted sequence of vertices.

  1. If a vertex with no edges is added, insert it anywhere in the sequence.
  2. If an edge or a vertex is removed, do nothing.
  3. If a forward edge (from lower-sorted to higher-sorted vertex) is added, do nothing.
  4. If a new backward edge A→B is added, move B directly after A. Mark outgoing edges of B as new. Repeat points 3 and 4 as necessary. (If several vertices can be moved, start with the lowest-sorted one; if a vertex to be moved has several new incoming edges, choose one from the highest-sorted vertex). If you encounter the same vertex twice in this process, report a cycle.

The algorithm by itself doesn't detect cycles, but you may limit cycle search to the subset of vertices that were moved.

Upvotes: 2

Related Questions