获取带有约束条件的线段上点的位置

14
我正在为ZenUML设计一个布局引擎。其中一个要求(经过简化)如下:
  1. 有一条线段;
  2. 在这条线段上有n个点(n < 100,如果能提高性能则可以缩小为n < 30),其顺序固定;(例如P1~Pn)
  3. 某些点之间的最小距离是已知的;(例如m_d(P2,P4)=500)
  4. 线段的长度应尽可能小;
  5. (可选)相邻点之间的间隔应尽可能均匀(用标准差衡量,并且不能违反1~4)。
  6. (新增)最坏情况下必须在1秒内给出30个点的结果(或多或少存在其他限制)。

^ 标准差被用作我在有限的数学知识下可以精确描述的最佳替代方法。然而,正如Roman和David指出的,在某些情况下,没有满足最低标准差的更吸引人的结果。请参见此评论

https://math.stackexchange.com/q/4377433上提出了一个姐妹问题。使用数学语言(矩阵)描述的是相同的问题。

例如,对于一条线段上有4个点(P1 ~ P4)的情况。

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

  • a.一种解决方案是P1=0,P2=0,P3=200,P4=900。
  • b.更好的解决方案是P1=0,P2=100,P3=200,P4=900。(将P3放在中间)
  • c.更好的解决方案是P1=0,P2=300,P3=600,P4=900。(均匀分布P2和P3)

这个问题的一些背景信息。请看以下图表。

  • 我们需要为所有的生命线(竖直线)创建一个布局。#1,#2
  • 这些线之间的间隔由消息的长度决定。#3
  • 我们需要确保图表的总宽度尽可能小(当参与者很多时可以节省空间)。#4
  • 在这个图表中,B应该移动到C更近。#5enter image description here

我已经实现了以下满足约束#1~#4的内容。有人能帮忙解决约束#5吗?它可以部分满足(例如示例中的b)或完全满足(例如示例中的c)。我们可以使用标准差来衡量解决方案的质量。已更新:感谢Roman Svistunov,获取不理想位置的基本实现得到了极大简化。

// 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);
}

你能指定你试图最小化的间隙度量吗?或者换句话说,(好要有)相邻点之间的间隙在5中是什么意思?你想最小化最大间隙大小、平方间隙尺寸的总和还是其他函数? - kcsquared
1
“标准差”是一个不错的选择。为了提供一些背景,这是为了创造视觉上舒适的效果。比如说,均匀分布的点看起来比一端拥挤、另一端稀疏要好。我想指出,如果有n个点,就会有(n-1)个间隙。 - Devs love ZenUML
第一个和最后一个之间的距离没有预定义。例如,P1~P4的给定信息可能是m_d(P1, P2)m_d(P3, P4)。在这种情况下,d(P1, P4)将是m_d(P1, P2) + m_d(P3, P4)。这里没有给出m_d(P1, P4)。如果给出了,它不一定是最终结果,因为其他间隙可能会进一步推动P4向右移动。我在问题中提出的算法可以为P1和P4之间的距离产生正确的结果。它不满足#5。 - Devs love ZenUML
1
因此,对于第4点比第5点和算法更重要,范围是固定的。对于每个点,可以根据这个总体范围计算出最小和最大位置。 - Sebastian
1
不要优化间隙的标准差(适用于所有点的全局标准,对离群值更有权重),也不要优化到最佳位置的平方差和(适用于所有点的全局标准,对离群值更有权重),或者间隙的最小长度(仅适用于最极端点的全局标准),您还可以通过最小化该位置的平方差之和(适用于所有具有更多本地离群值权重的点的本地标准)来要求点位于两个相邻点的中间。我真的认为这在视觉上有所不同。 - Sebastian
显示剩余8条评论
3个回答

8

我将介绍一些理论知识,然后提供一些符合1-4和6的JavaScript代码,以及经过修改的版本5和以下两点:

  1. 能够应对数值问题
  2. 没有外部依赖

我们可以将1-4表示为线性规划。例如,您的样例实例将被转换为:

minimize x4 - x1
subject to

(known minimum distances)
a: x3 - x1 >= 200
b: x4 - x1 >= 900

(fixed order)
c: x2 - x1 >= 0
d: x3 - x2 >= 0
e: x4 - x3 >= 0

x1, x2, x3, x4 unbounded

每个线性规划问题都有一个对偶问题,其最优目标值相同(在这里满足一定条件)。上述问题的对偶问题如下:

maximize 200 a + 900 b
subject to

x1: -a - b - c = -1
x2: c - d = 0
x3: a + d - e = 0
x4: b + e = 1

a, b, c, d, e >= 0

这是一个没有容量限制的最大费用流问题。因此,某些路径是最优流,所以我们可以将标准1-4理解为最长路径问题。

一旦我们有了最优目标,这里是900,我们可以将标准4转换为约束条件。

x4 - x1 <= 900

思考如何制作最令人愉悦的布局。按照所写,我们可以通过解决二次规划问题来实现标准5:

minimize (x2 - x1)**2 + (x3 - x2)**2 + (x4 - x3)**2
subject to

(most efficient layout)
x4 - x1 <= 900

(known minimum distances)
x3 - x1 >= 200
x4 - x1 >= 900

(fixed order)
x2 - x1 >= 0
x3 - x2 >= 0
x4 - x3 >= 0

x1, x2, x3, x4 unbounded

我写的目标不是标准差,但这并不重要。最小化标准差等价于最小化方差。反过来,随机变量 X 的方差是 E[X**2] - E[X]**2,而 E[X]**2 在此处是一个常数 (例如,在本例中 E[X]=900/4=150)。最后,最大化 E[X**2] 等价于最大化等可能结果的平方和。
然而,我提出了一个不同的标准。
5′. 按照字典顺序最大化(从小到大排序)间隙长度列表。
这意味着我们尽可能地避免小间隙。在 Roman Svistunov 给出的示例中,假设我们有如下约束条件:
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8

标准差最小的解决方案集

x1 = 0
x2 = 0.75
x3 = 2
x4 = 6.25
x5 = 10

与优化替换目标的解决方案相比

x1 = 0
x2 = 1
x3 = 2
x4 = 6.5
x5 = 10

我们已经将 x2 更加居中,代价是让 x4 不太居中。由于 x2x4 更靠近其邻居,因此我认为这是一个合理的权衡,但最终还是由您决定。
要优化5',我们按如下步骤进行。首先制定一个线性规划问题,如下所示:
maximize z
subject to

(most efficient layout)
x5 - x1 <= 10

(known minimum distances)
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8

(fixed order)
x2 - x1 >= z
x3 - x2 >= z
x4 - x3 >= z
x5 - x4 >= z

x1, x2, x3, x4, x5 unbounded

在这里,我们解决最优情况,即 z = 1,并记录哪些差距阻止了它变得更大。我们替换那些 z 变量,并再次解决,重复此过程直到没有 z 的出现。

maximize z
subject to

(most efficient layout)
x5 - x1 <= 10

(known minimum distances)
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8

(fixed order)
x2 - x1 = 1
x3 - x2 = 1
x4 - x3 >= z
x5 - x4 >= z

x1, x2, x3, x4, x5 unbounded

最优解为 z = 3.5

maximize z
subject to

(most efficient layout)
x5 - x1 <= 10

(known minimum distances)
x3 - x1 >= 2
x4 - x2 >= 5.5
x5 - x3 >= 8

(fixed order)
x2 - x1 = 1
x3 - x2 = 1
x4 - x3 >= z
x5 - x4 = 3.5

x1, x2, x3, x4, x5 unbounded

最优解为z = 4.5,并且这是最后一次迭代。

正如前面所观察到的,我们可以使用扩展的最长路径算法来解决这些线性规划问题。在JavaScript中:

// Dual numbers represent linear functions of time.
function Dual(p, v) {
  return { position: p, velocity: v };
}

// Adds dual numbers x and y.
function dualPlus(x, y) {
  return Dual(x.position + y.position, x.velocity + y.velocity);
}

const epsilon = Math.sqrt(Number.EPSILON);

// Compares dual numbers x and y by their position at a time infinitesimally
// after now.
function dualLessThan(x, y) {
  let d = x.position - y.position;
  return d < -epsilon || (Math.abs(d) <= epsilon && x.velocity < y.velocity);
}

// Tracks delta, the length of time for which every pair of arguments to
// .dualLessThan() maintains the present relation.
function DeltaTracker() {
  return {
    delta: Infinity,
    dualLessThan: function (x, y) {
      let lessThan = dualLessThan(x, y);
      if (lessThan) {
        [x, y] = [y, x];
      }
      if (x.velocity < y.velocity) {
        this.delta = Math.min(
          this.delta,
          (x.position - y.position) / (y.velocity - x.velocity)
        );
      }
      return lessThan;
    },
  };
}

// Converts the adjacency matrix to an adjacency list representation.
function graphFromMatrix(n, matrix) {
  let graph = [];
  for (let j = 0; j < n; j++) {
    graph.push([]);
    for (let i = 0; i < j; i++) {
      if (matrix[i][j] > 0) {
        graph[j].push({ i: i, length: Dual(matrix[i][j], 0) });
      }
    }
  }
  return graph;
}

// Essentially the usual algorithm for longest path, but tracks delta.
function longestPathTable(graph, gaps) {
  let tracker = DeltaTracker();
  let maximum = Dual(0, 0);
  let table = [];
  for (let j = 0; j < graph.length; j++) {
    let argument = null;
    if (j > 0) {
      maximum = dualPlus(maximum, gaps[j - 1]);
    }
    for (let edge of graph[j]) {
      let x = dualPlus(table[edge.i].maximum, edge.length);
      if (tracker.dualLessThan(maximum, x)) {
        argument = edge.i;
        maximum = x;
      }
    }
    table.push({ argument: argument, maximum: maximum });
  }
  return [tracker.delta, table];
}

// Essentially the usual algorithm for decoding the longest path from the
// dynamic program table.
function freezeCriticalGaps(table, graph, gaps) {
  let j = table.length - 1;
  while (j > 0) {
    let critical = true;
    let argument = table[j].argument;
    if (argument !== null) {
      j = argument;
    } else {
      j--;
      gaps[j].velocity = 0;
    }
  }
}

// Changes the time from now to now + delta.
function advanceGaps(gaps, delta) {
  for (let i = 0; i < gaps.length; i++) {
    gaps[i].position += gaps[i].velocity * delta;
  }
}

// Extracts the final result from the dynamic program table.
function positionsFromTable(table) {
  let positions = [];
  for (let entry of table) {
    positions.push(entry.maximum.position);
  }
  return positions;
}

// Entry point for the layout algorithm.
function layOut(n, matrix) {
  let graph = graphFromMatrix(n, matrix);
  let gaps = [];
  for (let j = 1; j < n; j++) {
    gaps.push(Dual(0, 1));
  }
  while (true) {
    let [delta, table] = longestPathTable(graph, gaps);
    if (delta == Infinity) {
      return positionsFromTable(table);
    }
    if (table[n - 1].maximum.velocity > 0) {
      freezeCriticalGaps(table, graph, gaps);
    } else {
      advanceGaps(gaps, delta);
    }
  }
}

// Various test cases.
console.log(
  layOut(4, [
    [0, 200, 0, 900],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

console.log(
  layOut(5, [
    [0, 0, 2, 0, 0],
    [0, 0, 0, 5.5, 0],
    [0, 0, 0, 0, 8],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
  ])
);

console.log(
  layOut(4, [
    [0, 0, 200, 0],
    [0, 0, 0, 150],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

console.log(
  layOut(4, [
    [0, 0, 200, 0],
    [0, 0, 0, 200],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

console.log(
  layOut(4, [
    [0, 0, 200, 0],
    [0, 0, 0, 300],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

嗨,大卫,你能否详细解释一下“标准5的不同解释:我们最大化最小间隔(通过第二个最小值打破平局,通过第三个最小值打破平局等)”?我没有完全理解它的含义。 - Devs love ZenUML
@david-eisenstat 如果其中一个间隙被强制缩短而其他间隙是灵活的,那么有多个解决方案同样好,最小值最大化,只有其中一个对标准差有好处。例如,m_d(0,1) = 10, m_d(1,2)=10, m_d(1,3)=50,与 [0,10,20,60] 同样好,就像 [0,10,35,60] 一样,但第二个是必要的解决方案,第一个不是。 - Roman Svistunov
2
@david-eisenstat 抱歉,我没有看到编辑1之后。不管怎样,仍然不是同一个度量标准。假设我们有5个点,且 m_d(0,2)=2, m_d(1,3)=5.5, m_d(2,4)=8。现在最佳解(用于标准差)为 [0, 0.75, 2, 6.25, 10],而你的解将产生 [0,1,2,6.5,10]。但我会认为你的度量标准对我来说更有吸引力,但这是主观的,我们应该让 @devs-love-zenuml 解决这个问题。 - Roman Svistunov
1
@RomanSvistunov 我同意[0,1,2,6.5,10][0,0.75,2,6.25,10]更吸引人。我不知道用什么数学术语来描述或量化这个问题。 - Devs love ZenUML
@DevsloveZenUML 我已经删除了关于弹簧和杆物理模型的答案(顺便说一句,我认为我没有时间进行全面改进)。FYI,我手动计算了该物理模型的结果。结果是 [0,0.75,2,6.25,10] - Walter Tross
@WalterTross,谢谢。如果有一天你找到时间实现它,我会非常感兴趣去看看。这是一个有趣的模型。我已经和我的同事们(不在SO上)讨论过这个模型。我们想要自己构建它。再次感谢和感谢SO社区。 - Devs love ZenUML

5
首先,我们应该找到线段的最小长度。这可以通过贪心算法来实现:将第一个点放置在0处(没有损失通用性),并逐个添加以下点,其坐标尽可能小,而不违反对所有以前点的距离要求。我们会将最后一个点固定在其位置,并不再移动它。我认为正确性是显然的。
现在,最棘手的部分是优化相邻距离的标准偏差。我们将引入n-1个变量 - 距离,我将它们命名为Di。试图最小化它们的标准偏差等同于最小化方差。
因为E(D)是恒定的,所以我们可以在固定第一个和最后一个点的情况下最小化标准偏差,就是最小化差异总和。
距离约束都是线性的,每当你有m_d(Pi,Pj)时,你会添加约束(sum Dk for k=i to j) >= m_d(Pi,Pj)。为了保证距离总和符合要求,我们还会添加合同sum Dk,既小于或等于也大于或等于在步骤一中计算的最小距离。因此,这个问题是一个二次优化问题,可以用库来解决。
请注意,点的坐标可以很容易地从距离中恢复为前缀和。
即使对于30个点,可能任何二次编程算法都足够快,如果你打算增加点数,那么进一步优化是值得投资时间的,因为这个问题实际上可以在多项式时间内完全解决。
第一个最重要的优化。因为目标函数是平方和,目标二次形式的矩阵是正定的(因为它是单位矩阵),因此存在一个多项式算法,如这篇论文所示。
我想提及的最后一个优化可能不相关,但在大多数可能的m_d矩阵上非常好。为了减少二次规划问题的大小,我们可以在二次规划之前找到某些点的最佳位置。
首先,我们需要缩减矩阵,以确保对于任何j都满足m_d(Pi,Pj)+m_d(Pj,Pk)>=m_d(Pi,Pk),并更新右侧。请注意,在此计算中,m_d(P1,Pn)也是线段的最小可能长度。完成此操作后,我们可以说,对于任何,如果m_d(P1,Pi)+m_d(Pi,Pn)=m_d(P1,Pn)为真,则点Pi只有一个可能的位置,这使我们可以删除变量之一,因为现在可以使用从P(i-1)到P(i+1)的距离替换P(i-1)到Pi和Pi到P(i+1)的距离的第一个变量 - 这个新距离就是Pi的位置-P(i-1)的位置,这可以通过归纳来推导出来,而P(i+1)的位置是P(i-1)的位置加上这个新距离。
编辑2:
此伪代码有两个版本,都假定您使用某种二次编程库,第一个版本是直观的(用于少数库),第二个版本是针对使用矩阵作为其输入的库(但不太直观)。
function findOptimal(Matrix md, int n) {
  int minLength = findMinLength(md, n);
  Constraints constraints; //from library
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (j < i)
        //Here sum of variables is not their current sum
        //but some object for library
        constraints.AddConstranit(sum of variables i to j >= md[j][i])
      else
        constraints.AddContraint(sum of variables j to i >= md[j][i])
    }
  }
  constraints.AddConstraint(sum of variables 0 to n-1 <= minLength)
  variables = QuadraticOptimizationSolve(sum of squares of variables, contracts)
  positions = Array<number>(n);
  positions[0] = 0;
  for (int i = 0; i < n; ++i) {
    positions[i + 1] = positions[i] + variables[i];
  }
  return positions;
}

矩阵在库中更常用作输入,因此这里是与其一起使用的伪代码:

function findOptimal(Matrix md, int n) {
  int minLength = findMinLength(md, n);
  Matrix optimization = Matrix(n - 1, n - 1);
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < n - 1; ++j) {
      if (i == j)
        optimization[i][j] = 1
      else
        optimization[i][j] = 0
    }
  }
  Matrix constraints = Matrix(n * (n - 1) / 2 + 1, n)
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      constraintRow = i * (i - 1) / 2 + j;
      //constriant is sum of distances from j to i is 
      //at least md[j][i]
      for (int k = j; k < i; ++k) {
        //these are coefficients in linear combination
        //negative because we need >= while optimizers usually use <= contraints
        if (k >= k and k < i)
          constraints[constraintRow][k] = -1
        else
          constraints[constraintRow][k] = 0
      }
      constraints[constraintsRow][n - 1] = -md[i][j];
    }
  }
  variables = QuadraticOptimizationSolve(optimization, constraints);
  positions = Array<number>(n);
  positions[0] = 0;
  for (int i = 0; i < n; ++i) {
    positions[i + 1] = positions[i] + variables[i];
  }
  return positions;
}
Also this solution assumes in your library the constants vector in constraints is the last column, but sometimes it might be separate vector

编辑 3

以下是你问题的JavaScript解决方案。它可以轻松地在一秒钟内处理30个点(实际上在我的设备上,它可以处理高达100个点)。它使用了与你不同的findMinLength函数实现(你的没有保存递归调用的结果,因此呈指数增长)。另外,我找不到一个好的二次规划库,所以最终使用了这个解决方案(在编辑4中进行了修改)。这是为node js编写的,但将所有文件组合在一起(并删除需要在其文件中定义vsmall作为epsilon的requires和exports,对于vsmall:你需要在他们的文件中定义vsmall作为epsilon),这个库似乎可以工作。先前的库似乎只是这个库的浏览器版本,并且这个库有一个问题,几年后被修复了,但手动修复也很容易(因为它没有依赖项)。

let findMinLength = function (n, m) {
  let answer = [];
  answer[0] = 0;
  for (let i = 1; i < n; i++) {
    answer[i] = 0;
    for (let j = 0; j < i; j++) {
      answer[i] = Math.max(answer[i], answer[j] + m[i][j], answer[j] + m[j][i]);
    }
  }
  return answer[n - 1];
}
let findOptimal = function(n, m) {
  let minLength = findMinLength(n, m);
  let dmat = [];
  let dvec = [];
  for (let i = 0; i < n - 1; i++) {
    dmat[i + 1] = []
    dvec[i + 1] = 0
    for (let j = 0; j < n - 1; j++) {
      if (i == j)
        dmat[i + 1][j + 1] = 1;
      else
        dmat[i + 1][j + 1] = 0;
    }
  }
  let amat = [];
  for (let i = 0; i < n - 1; i++) {
    amat[i + 1] = [];
    amat[i + 1][1] = -1;
  }
  let bvec = [];
  bvec[1] = -1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      let constraintRow = i * (i - 1) / 2 + j;
      for (let k = 0; k < n - 1; k++) {
        amat[k + 1][constraintRow + 2] = (k >= j && k < i) ? 1 : 0;
      }
      bvec[constraintRow + 2]=Math.max(m[i][j], m[j][i]) / minLength;
    }
  }
  let variables = solveQP(dmat,dvec,amat,bvec).solution;
  let positions = [];
  positions[0] = 0;
  for (let i = 0; i < n - 1; i++) {
    positions[i + 1] = positions[i] + variables[i + 1] * minLength;
  }
  return positions;
}

例如,调用findOptimal(4, m),其中m与您的示例相同(有4个点),该函数返回[0,300,600,900]
编辑
如@david-eisenstat所指出,存在将第5个点解释为最大化最小差距的解释,但是还有一种更简单和渐进更快的解决方案,即二分查找答案。
我们知道最小差距至少为0,并且最多为段长度/n。我们可以通过二分查找来增加它,通过检查器确保每个间隙都至少是我们的值。如果findMinLength是一个解决1-4的函数,则以下是优化此度量标准的解决方案(伪代码)。
function findOptimal(Matrix md, int n) {
  minLength = findMinLength(md, n) //The answer to minimize segment length
  minGapL = 0 //Lower bound in maximized minimum gap length
  minGapR = ceiling(minLength / n) //Upper bound in maximized minimum gap
  while minGapL < minGapR {
    minGapTest = (minGapL + minGapR) / 2
    mdCopy = md.copy()
    //This loop ensures that every gap is at least minimum gap tested
    for (int i = 1; i < n; ++i) {
      mdCopy[i - 1][i] = max(mdCopy[i - 1][i], miGapTest)
    }
    int testLength = findMinLength(mdCopy, n)
    if (testLength == minLength) {
      //if it is possible to get tested minimum gap update lower bound
      minGapL = minGapTest
    } else {
      //otherwise update lower bound
      minGapR = minGapTest - 1;
    }
  }
  return (minLength, minGapL);
}

使用此函数返回长度和最大化的minGap,可以像循环中那样使用矩阵修改重构答案,然后仅解决1-4问题。该解决方案是多项式的(如上所示,1-4问题可以在线性时间内解决,并且二分搜索是答案的对数,由于答案是输入大小的指数,因此也是输入大小的线性)。

1
谢谢@roman-svistunov。为了确保我理解正确,在第2行,参数n不是必需的,对吗?第7行应该是“md”。 - Devs love ZenUML
是的,这两个函数都不需要参数n,它只是md的大小。在第7行中应该是md,我已经将其编辑到答案中了。 - Roman Svistunov
2
“将第五点解释为最大化最小间隙”并不一定正确。例如,m_d(0,1) = 10, m_d(1,2)=10, m_d(1,3)=50。P0和P1之间的距离将固定为10。但是P2仍然可以移动到P1和P3的中间。 - Devs love ZenUML
这是真的,但代码会更好看,而且通常会起作用。这里的标准差优化似乎和任何正定矩阵的二次优化一样困难(虽然从未证明过,只是主观意义),而且速度会慢得多(仍足以处理30个点,但我不会对每秒100个或更多的点感到热情)。无论如何,我正在完成标准差解决方案的伪代码编辑。 - Roman Svistunov
1
现在问题已经解决了,原因是在库中。现在设置库略微困难,但至少应该能够工作,请参阅帖子获取详情。 - Roman Svistunov
显示剩余9条评论

2

既然您表示近似值可以接受,那么这里有一个简单的代码,可以计算出与我的其他答案大致相同的结果。邻接表版本可能会更长,但在稀疏约束矩阵上很可能更快。

// Increase for faster but less accurate results.
const PIXEL = 1;

// Returns a layout where each gap is within PIXEL of optimal.
function layOut(n, m) {
  let positions = Array(n).fill(0);
  let gaps = Array(n).fill(0);
  while (true) {
    // Compute the leftmost layout.
    for (let j = 1; j < n; j++) {
      positions[j] = positions[j - 1] + gaps[j - 1];
      for (let i = 0; i < j; i++) {
        positions[j] = Math.max(positions[j], positions[i] + m[i][j]);
      }
    }
    // Compute the rightmost layout. As we do so, each gap that can grow, grows.
    let stillGrowing = false;
    for (let i = n - 2; i > -1; i--) {
      let proposedGap = gaps[i] + PIXEL;
      // i + 1 is rightmost; i is leftmost.
      let maxGap = positions[i + 1] - positions[i];
      if (proposedGap < maxGap) {
        gaps[i] = proposedGap;
        stillGrowing = true;
      } else {
        gaps[i] = maxGap;
      }
      positions[i] = positions[i + 1] - gaps[i];
      for (let j = n - 1; j > i; j--) {
        positions[i] = Math.min(positions[i], positions[j] - m[i][j]);
      }
    }
    if (!stillGrowing) {
      return positions;
    }
  }
}

// Adjacency list version.
function layOut(n, m) {
  let leftArcs = [];
  let rightArcs = [];
  for (let i = 0; i < n; i++) leftArcs.push([]);
  for (let j = 0; j < n; j++) rightArcs.push([]);
  for (let j = 1; j < n; j++) {
    for (let i = 0; i < j; i++) {
      let x = m[i][j];
      if (x > 0) {
        leftArcs[j].push([i, x]);
        rightArcs[i].push([j, x]);
      }
    }
  }
  let positions = Array(n).fill(0);
  let gaps = Array(n).fill(0);
  while (true) {
    // Compute the leftmost layout.
    for (let j = 1; j < n; j++) {
      positions[j] = positions[j - 1] + gaps[j - 1];
      for (let [i, x] of leftArcs[j]) {
        positions[j] = Math.max(positions[j], positions[i] + x);
      }
    }
    // Compute the rightmost layout. As we do so, each gap that can grow, grows.
    let stillGrowing = false;
    for (let i = n - 2; i > -1; i--) {
      let proposedGap = gaps[i] + PIXEL;
      // i + 1 is rightmost; i is leftmost.
      let maxGap = positions[i + 1] - positions[i];
      if (proposedGap < maxGap) {
        gaps[i] = proposedGap;
        stillGrowing = true;
      } else {
        gaps[i] = maxGap;
      }
      positions[i] = positions[i + 1] - gaps[i];
      for (let [j, x] of rightArcs[i]) {
        positions[i] = Math.min(positions[i], positions[j] - x);
      }
    }
    if (!stillGrowing) {
      return positions;
    }
  }
}

// Various test cases.
console.log(
  layOut(4, [
    [0, 200, 0, 900],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

console.log(
  layOut(5, [
    [0, 0, 200, 0, 0],
    [0, 0, 0, 550, 0],
    [0, 0, 0, 0, 800],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
  ])
);

console.log(
  layOut(4, [
    [0, 0, 200, 0],
    [0, 0, 0, 150],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

console.log(
  layOut(4, [
    [0, 0, 200, 0],
    [0, 0, 0, 200],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

console.log(
  layOut(4, [
    [0, 0, 200, 0],
    [0, 0, 0, 300],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ])
);

谢谢David。我刚刚测试了这个解决方案。正如你所说,所有测试(位置大于100)都通过了。平均而言,在没有进一步优化的情况下,它比您的原始解决方案慢10倍。我还没有使用“邻接列表表示”进行测试。 - Devs love ZenUML
@DevsloveZenUML 根据您的约束矩阵稀疏程度,我可以轻松地看到这个解决方案弥补差距。 - David Eisenstat
我没有关于矩阵稀疏程度的数据。想象一个典型的序列图。我需要创建这个矩阵来保存“参与者”之间“消息”的宽度以及“参与者”标签的宽度(在参与者名称很长的情况下)。 - Devs love ZenUML
此外,我们在一个序列图中不会有超过几个参与者。 - Devs love ZenUML
@DevsloveZenUML发布了邻接表版本以供比较。 - David Eisenstat

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接