Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Simplifying a business example, I have the following situation:

Some objects should be distributed in a graph in most "linear" way possible for a given "thermometer".

Say, a voyager visits some cities. Several cities are visited multiple times.

So, we have list of cities in ordinate axis (that may be duplicated), and Time in abscissas one.

Now, for a given path, say (A => X => A => B => C) we should display a line, in the "most linear way possible".

enter image description here

By eg. in the image above, the green line is optimal one
(1 > 2 > 3 > 4 > 5)

but there could be multiple possible outputs

(1 > 2 > 1 > 4 > 5)
(1 > 2 > 3 > 4 > 5)
(1 > 2 > 6 > 4 > 5)

(3 > 2 > 1 > 4 > 5)
(3 > 2 > 3 > 4 > 5)
(3 > 2 > 6 > 4 > 5)

(6 > 2 > 1 > 4 > 5)
(6 > 2 > 3 > 4 > 5)
(6 > 2 > 6 > 4 > 5)

Is there some algorithms helping in such situations?

share|improve this question
    
Is it not more linear to move the first point up to (1)? Maybe I do not understand the requirements. With repeats you can always construct your graph so that any given sequence or path is displayed linearly. –  Joshua Shane Liberman Jan 25 '11 at 15:11
    
@Joshua Shane Liberman: Have reason. I fixed the post. –  serhio Jan 25 '11 at 17:28
    
Your edits have made my statement even more valid and left unanswered. The algorithm is to have the ordinate axis be your list of visited cities. Are you asking if one graph can make all possible outputs appear linear? –  Joshua Shane Liberman Jan 25 '11 at 17:47
    
@Joshua Shane Liberman: The problem is that the Thermometer is modified by the user, and not generated by the graph nodes. –  serhio Jan 25 '11 at 18:13
2  
I don't understand the question, and the lack of responses suggests I'm not the only one. Voting to close in the hope of spurring OP on to edit some comprehensibility into the question. –  Gerry Myerson Jul 24 '11 at 5:02
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.