Get the position of points on a line segment with constraints

I am designing a layout engine for ZenUML. One requirement (after simplification) is this:

1. There a line segment;
2. There are n (n < 100, it can be reduced to n < 30 if that makes difference in performance) points on this line segment, the order is fixed; (e.g. P1 ~ Pn)
3. There are known minimum distances between some points; (e.g. m_d(P2,P4)=500)
4. The length of the line segment should be as small as possible;
5. (nice to have) The gaps between neighbour points should be as even as possible (measured by standard deviation, and must not violate 1~4).
6. (newly added) it must give result in no longer than 1s for 30 points in worst case (more or less constraints).

A sister questions is asked at https://math.stackexchange.com/q/4377433. It is the same problem described with math language (matrix).

For example, for a line segment that has 4 points on it (P1 ~ P4).

m_d(P1, P3) = 200, m_d(P1, P4) = 900.

• a. One solution would be P1 = 0, P2 = 0, P3 = 200, P4 = 900.
• b. A better solution would be P1 = 0, P2 = 100, P3 = 200, P4 = 900. (put P3 at the middle)
• c. A even better solution would be P1 = 0, P2 = 300, P3 = 600, P4 = 900. (evenly distribute P2 and P3).

Some background of this problem. Have a look at the following diagram.

• We need to create a layout for all the lifelines (vertical lines). #1, #2
• The gap between those line are decided by the length of messages. #3
• We need to make sure the total width of the diagram is small (to save space when there are many participants). #4
• In this diagram, B should be moved to closer to C. #5

I have implemented the following which satisfies constraints #1~#4. Can some please help with constraint #5? It can be partially met (like b in the example) or fully met (like c in the example). We can use standard deviation to measure the quality of the solution. Updated: thanks to Roman Svistunov, the base implementation to get non-optimal position is dramatically simplified.

// Known minimum distance is stored in a matrix
// e.g.
//    m = [
//      [0, 100, 0, 900],
//      [0, 0,   0, 0],
//      [0, 0,   0, 0],
//      [0, 0,   0, 0],
//    ]

let f = function (n: number, m: Array<Array<number>>): number {
  let array = Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    array[i] = f(i, m) + m[i][n];
  }
  return Math.max(0, ...array);
}

from Recent Questions - Stack Overflow https://ift.tt/6NcxzwS
https://ift.tt/L1JGulR