Sorting with only a partial order definition

[Lasse Vågsæther Karlsen]

Lasse Vågsæther Karlsen wrote:
> Paul Rubin wrote:
> 
>> Lasse Vågsæther Karlsen <lasse at vkarlsen.no> writes:
>>
>>> I have a list of items and a "rule" for ordering them.
<snip>

Ok, managed to implement the algorithm. Might not be the optimal 
solution (memory and speed-wise) but it worked and doesn't take too long 
to run either so I'm going to stick with it.

I have a different question though, along the same lines, but one that 
doesn't need a solution, just want to know if something like it exists.

A while back I had an application that had a lot of items that it needed 
to order. The problem, however, was that the rules was not defined at 
all. Instead it was opted for a visual solution where the user would be 
presented with images and had to rearrange them in the order that was 
necessary. The application was one I helped build for a friend which 
combined images from several cameras and allowed him to sort them 
according to the contents so that he could get a timeline formed.

The date/time stamps on the cameras was not directly usable for various 
reasons so the visual ordering was what we ended up on. For instance, 
two of the cameras was not digital ones so they had no timestamp except 
for the one provided by the scanning software.

In that application we talked about presenting the user with two and two 
images and he just had to click on the image that came first. The 
problem with this was to try to present the "right" images to the user 
so that he had to minimize the number of clicks.

In other words, try to pick nodes in the graph and ask the user to 
provide the direction of the edge, and the "picking algorithm" would 
work in such a way that the number of edges would be minimized.

Not sure if I'm explaining it correctly.

The solution we ended up with was to present the user with all the 
images in one big timeline and just let him drag them around. This worked.

What I was wondering about is if there is an algorithm that would do 
what I want? Ie. help me pick the nodes so as to minimize the number of 
edges. Obviously the answer to the first pair of nodes will influence 
which nodes will be subsequently picked, so each answer would stear the 
algorithm in a way, not just go into the final problem.

If anyone got the name of such an algorithm or something I would like to 
look at it at least. Application is built and deployed so I'm not 
looking for a solution to implement.

-- 
Lasse Vågsæther Karlsen
http://usinglvkblog.blogspot.com/
mailto:lasse at vkarlsen.no
PGP KeyID: 0x2A42A1C2