1
$\begingroup$

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?

  • 0
    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.2011-01-25
  • 0
    @Joshua Shane Liberman: Have reason. I fixed the post.2011-01-25
  • 0
    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?2011-01-25
  • 0
    @Joshua Shane Liberman: The problem is that the Thermometer is modified by the user, and not generated by the graph nodes.2011-01-25
  • 0
    By thermometer (a device for measuring temperature) do you mean the y-axis?2011-01-25
  • 0
    Okay, I finally understand the question you are asking. Now you just need to explain the phrase "most linear way possible". DXAD in the first graph provides a situation where there is no perfect solution and two reasonable alternatives.2011-01-25
  • 0
    For Thermometer you understood correctly. this is why I wrote it in uppercase. I don't know what is "DXAD", but the second graph has no perfect linear solution. So, then "most linear way" means exactly what it says "most linear way possible". I am afraid I will be forced to finally calculate angles between lines in order to deal with some arc weights for optimization.2011-01-25
  • 0
    With DXAD I meant a path that traveled through those cities in that order.2011-01-25
  • 0
    Is it not easier to calculate just the slope? A naive algorithm would be greedy and just grab the subsequent city with slope nearest to the previous slope, possibly with look-ahead.2011-01-25
  • 0
    As a measure of "linearity" you could fit a straight line and compute a measure based on the residuals.2011-04-15
  • 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.2011-07-24
  • 0
    @Gerry: the OP has not returned since April, so I wouldn't hold out hope. Another way to demand clarification is through up/down votes: one of the reasonable reasons for voting down a question is that the question is "unclear or not useful".2011-07-25
  • 0
    @Willie, you fooled me, by editing the question, into thinking it was current. Of course, I should have looked at the other dates on the question and comments.2011-07-25
  • 0
    @Gerry: it was one of those cases of Community User thinking this question deserves an answer. I merely retagged after seeing that the tags were incorrect.2011-07-26
  • 0
    is anybody aware of an algorithm to "exponentialize" data points of a linear graph?!2017-12-10

0 Answers 0