Shevek (shevek) wrote,

I have a directed graph G = (V, E). For each edge (a, b) in E, I know either a < b or a <= b. If (a, b) not in E, then nothing is known, thus the graph defines a partial order on the elements of V, some of which is strict and some of which is not. I would like to know a reasonably minimal partition of G into equivalence classes such that the total ordering on sample elements from each class is consistent.

Note that a <= b, b <= a creates an equivalence class. Note also a < b, b <= a creates an inconsistency and no ordering of equivalence classes is possible. Consider a <= c, b <= c, a < d, b <= d as a good case with which to start designing an algorithm.

If it helps, visualise the system as a marble maze such that (a, b) means the marble can travel from a to b, and if a < b, then the traverse is downhill. Is the maze consistent (not an Escher), what is the total depth of the maze, and which nodes are at which levels?

This is an instruction scheduling problem for a compiler, the solution probably requires a topological sort on the transitive closures over <= of elements reachable from one end of a < relation. I have not yet had the clarity of thought required to solve it, but it seems almost immediate that a good solution should take at most O(n^2) time.
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.