Algorithm Based Sorting / Re-Ordering of objects based on allowed following objects

Question

I have a need to develop an algorithm that will take a set of unordered objects and re-order them intelligently based on the objects they are allowed to proceed to.

My initial design/thought is to use Core Data to store an entity (for instance "Objects") with a to-many relationship ("canGoTo") back on itself with a set of objects that can follow the selected Objects *object.

Consider the following example where each object has a set of objects in which it can proceed to (the actual set of objects is much larger).

Object A - can go to -> Objects B,C,D
Object B - can go to -> Objects E,F,G,Y,H
Object C - can go to -> Objects P,S,Z
Object D - can go to -> Objects H,J,X
...
Object G - can go to -> Objects R,Y,Z
Object H - can go to -> Objects G,Z
...
Object Y - can go to -> Objects Z
Object Z - can go to -> Objects NULL (no objects follow this object)

If the program is given a set of Objects (R,B,H,G,A,Z) the program needs to find how to re-order the objects to find an acceptable structure. Thus the correct outcome for this set would be A->B->H->G->Y->Z

What strategy is the best, or most efficient, to flow through this issue? Should I be looping through re-orders and quitting when I successfully touch all objects in a pass? Using a genetic algorithm to generate output and analyzing generations (i.e. http://ijoshsmith.com/2012/04/08/simple-genetic-algorithm-in-objective-c/)? Or do I use an Insertion Sort to analyze all objects and re-order the object to where it can fit in the sequence? Keep in mind the real list of objects will be more like 30+ objects long instead of 6, and in a perfect world the program would pick the BEST way to order the list (maybe based on "canGoTo" priority).

Any advice/best practices would be greatly appreciated. Sorry for no sample code, this is in the thought phase at the moment.

As of my first glance at that link I would have to agree. Never heard of a Topological Sort until now, thanks for the heads up! — Andrew Robinson
– Andrew Robinson, Commented Nov 6, 2012 at 17:26

alestanis · Accepted Answer · 2012-11-06 14:09:15Z

1

You can model your problem as a Directed Acyclic Graph and then do Topological Sorting on it. This will give the exact output you are looking for.

answered Nov 6, 2012 at 14:09

alestanis

22k4 gold badges50 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andrew Robinson Over a year ago

Thanks for the answer! I love the Topological sorting idea. I will investigate this model further but definitely a correct answer.

Andrew Robinson Over a year ago

So, to follow up on some research I have done, it seems topological sorting selects ALL objects and places them in an order that makes sense (based on the design and always following the nodes forward). Since the program needs to evaluate a series of say 100 objects and extract 25-35 of them in order (based on rules specifying which objects can follow a given object), does it make sense for me to program the extract of the 25-35 objects FIRST and worry about sorting later?

alestanis Over a year ago

Are you certain that there will be a path through all these objects? In that case, you can try building a DAG with only the 25-35 objects that matter to you, sort it, and then extract the given path. In your example, Object B - can go to -> Objects E,F,G,Y,H but you only need objects (R,B,H,G,A,Z) so you would build a graph with the information Object B - can go to -> Objects G,H

Collectives™ on Stack Overflow

Algorithm Based Sorting / Re-Ordering of objects based on allowed following objects

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related