1

Given a series of statements such as:

a<c
a<b
b<c
(Read as "a is before b", "a is before c", etc.)  

What is the order of the elements? In this example, the answer is a<b<c.

A less trivial question would be:

a<c<d
b<d
c<e
a<b

This one has four answers: a<b<c<d<e, a<c<b<d<e, a<b<c<e<d, a<c<b<e<d.


Edit: To be clear, an algorithm need only return 1 of the possible answers for the logical statements. There will also never be a case where the statements have a contradiction. E.g. below is an impossible input:

a<b
b<a
  • 2
    Are you asking people to describe such an algorithm, write one, or are you trying to make a discussion? This doesn't seem like a real "question" – Daenyth Mar 17 '15 at 17:58
  • Write or describe, either would be of great assistance. This is a real-world problem where a system I'm working with outputs up to 26 elements in a defined order. However, it does not tell me the order and only outputs non-null entries. – user1361991 Mar 17 '15 at 18:03
  • 5
    You might be looking for "topological sort". Note that depending on which statements you're working from, you may only have a partial order (so there are multiple possible orderings and topological sort just chooses an arbitrary one) or there might be a contradiction (so there's no possible ordering). – Steve314 Mar 17 '15 at 18:03
  • 3
    Another possibility is a "transitive closure". A closure takes some seed set and grows it until all reachable members are included in that set. If you have a < b and b < c in your seed set, by transitivity, you also have a < c, so a transitive closure would add that to the set, and then use that as if it were a seed element as well to try to find more, until no further ordering statements can be proven from those already found. – Steve314 Mar 17 '15 at 18:09
9

A topological sort algorithm can sort a collection of data according to some set of rules as you have specified, where not all pairs have a pre-defined ordering.

Typically the rules only define a partial ordering, so there are multiple possible orderings and topological sorting chooses an arbitrary one. If there's a contradiction in the rules you have specified, there will be no possible ordering.

If you can give a true/false/don't-know answer for any pair of elements in constant time, IIRC there are sequential algorithms that topologically sort in linear time - O(Vertices + Edges), as mentioned in comments below.

A contradiction in the constraints arises if, and only if, there is a cycle in the constraints. It may therefore by useful to identify the "greatest strongly connected components" in the digraph of constraints.

It may also be useful to grow your initial seed set of constraints to include all possible constraints that can be proven directly or indirectly from that seed set. In general, the resulting set is considered "closed" with respect to the function used to find new members, so algorithms that grow sets like this are "closure algorithms" - not to be confused with a lexical-scope closure. Particular set closures often mentioned WRT abstract algebra include symmetric closures (if a?b is in your set, also add b?a), reflexive closures (if a?b is in your set, also add a?a and b?b) and transitive closures (if a?b and b?c are in your set, also add a?c).

Ordering relations are transitive - if a<b and b<c then a<c - so the transitive closure of your set of constraints may be useful.

You might also want to identify clusters of elements that are ordered with respect to each other (assuming no contradiction) without caring initially about the order. This defines a partitioning of the elements into equivalence classes, given an in-the-same-cluster sense of equivalence. For that, you could use a disjoint set / union-find data structure - the equivalence classes are disjoint from each other, so each equivalence class is a set that's disjoint from the others. The union operation from union find basically says "whatever classes these two elements are in, combine those classes into a single class if necessary". The "find" determines which class a particular element is in, usually by choosing one element to represent that class.

A common theme in all this is the theory of graphs, although aspects come from abstract algebra and elsewhere. Basically, the relation a<b can be modelled as an edge on a graph between vertices representing the elements a and b. If you care about the ordering, that's a directed graph.

For example a relation x<y will appear in the transitive closure of your initial set of constraints if both x and y are in the same strongly connected component of the digraph.

Sorry, I got confused above - the relation x<y will appear in the transitive closure if there's any path between x and y in the digraph, but that doesn't imply a strongly connected component. A strongly connected component requires a cycle, not just a path.

  • 1
    "IIRC there are sequential algorithms that topologically sort in linear time" The Wikipedia article claims that "Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time." According to this Stack Overflow question there's algorithms that are O(Vertices + Edges), because at each vertex it checks the outgoing edges and the sum of all outgoing edges is the total number of edges. – Doval Mar 17 '15 at 19:13
  • 1
    @Doval - it could be the "+ Edges" part of that big-O that resolves my confusion. What I said about true/false/don't-know obviously applies to full-order sorting (it's just that the don't-know case never happens) and that obviously has O(n log n) complexity, but n in that case is only the number of vertices. The number of possible edges in a digraph with n vertices (and at most one edge in each direction between any pair of vertices) is n^2, so the number of edges is significant. A full order sort based on an O(n) topological sort would presumably be O(n^2) because all possible edges exist. – Steve314 Mar 17 '15 at 19:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.