All orderings of boost::graph::topological_sort()
Hello, In implementing a dependency graph subsystem, one of the tasks is figuring out all the possible ways of traversing the graph with respect to the dependencies. boost::graph::topological_sort() looks like a reasonable place to start; however, topological_sort() only gives /one/ linear ordering, not all possible orderings. I digged into the code and found that the algorithm is in fact a call to depth_first_search with a custom visitor. The 0-in-degree vertices are not mentioned in the algorithm, and I suspect manipulating the order of these vertices would be a good start in generating different orderings. I also digged into the depth_first_search() code, but there too it doesn't seem to be straightforward to change the order in which those start-nodes are visited. I am also aware that even if I would find a way to change the order in which the 0-in-degree vertices are visited it will still not give me all the various orderings; I think that repeating the procedure with a bredth_first_search() will give me yet more different orderings, and with I'll have all the different orderings. I may have missed something obvious but I really don't know how to tackle the problem of generating various orderings. Any advice, please? Thank you! -- Matan
I may have missed something obvious but I really don't know how to tackle the problem of generating various orderings. Any advice, please?
For any significant-sized input the number of orderings will be too large to do anything useful with. For an input small enough that the set of feasible orderings will fit in memory I would simply generate all permutations and screen for feasibility rather than attempting to create an enumeration algorithm. Create a comparability matrix and use it to prune the permutation tree, perhaps? N^2 bits doesn't sound prohibitive. This has probably been studied but I'm at work so I'll speculate. For larger inputs with many constraints it may be worthwhile to create an enumeration algorithm. For purposes of empirical testing of build-ordering systems it might be sufficient to go into the algorithm and randomize the selection processes whenever it makes arbitrary choices. This may or may not be easily achieved by randomly pre-sorting the input, depending on the internals of the algorithm. If the sort is stable that will work. An efficient feasible ordering enumerator for arbitrary finite partial ordered sets would have to have a recursive structure because there can be arbitrarily complex subgraphs with mutually incomparable nodes, nested to arbitrary depth. Another point regarding applications: if you are interested in testing build orders (as I very much am, that's what I'm doing manually right now) you can't just convert the partial order to a total order arbitrarily because modern build systems exploit incomparables in the partial order to parallelize build steps. If you impose an arbitrary order on the incomparables you serialize the build artificially, which prevents testing for parallel-step interaction. If there is enough interest to justify adding an efficient deterministic enumerator for poset orders I'll write one. Graph-theoretical algorithms are a fun way to spend the weekend :-)
participants (2)
-
Matan Nassau -
Stephen Nuchia