网络流量算法的适当图形表示 [英] Appropriate graph representation for network flow algorithms

问题描述

在实施 Ford-Fulkerson 或

When implementing Ford-Fulkerson or Dinitz algorithms for maximum network flow there are two operations that need to be performed on the graph:

• 遍历给定顶点的所有邻居
• 找到给定边的反边(当沿着增加路径添加流时，图形修改需要使用此边).

理想情况下，第一个操作相对于邻居数是线性的，第二个操作应该是恒定的.此外，图形表示所需的内存应相对于边数呈线性关系(请注意，对于最大网络流算法的大多数实际应用，我已经看到边数约为线性数乘以顶点数).仅在满足上述约束的情况下，这两种算法的复杂性的所有估计才成立.

Ideally the first operation will be linear with respect to the number of neighbours and the second one should be constant. In addition the memory required for the graph representation should be linear with respect to the number of edges(note that for most practical applications of max network flow algorithms I have seen the number of edges is about linear times the number of vertices). All the estimations for the complexity for the two algorithms will only hold if the constraints above are met.

问题是经典图形表示法都不能满足上述要求:

The problem is that none of the classical graph representations is able to meet the above requirements:

使用邻接矩阵，可以在恒定的时间内找到给定边的反向边.但是，相对于所有顶点的数量，对所有邻居进行迭代都是线性的，并且相对于顶点的数量，所需的内存是二次的.

Using adjacency matrix, finding the reverse edge of a given edge can be done in constant time. However iterating over all neighbours is linear with respect to the number of all vertices and also the required memory is quadratic with respect to the number of vertices.

使用该表示形式，在所有邻居上进行迭代相对于邻居数量而言不是线性的，并且找到给定边的反向边也不是恒定的.

Using this representation, iterating over all neighbours will not be linear with respect to the number of neighbours and also finding the reverse edge for a given edge is not constant.

使用这种表示形式，我们可以在线性时间内对所有邻居进行迭代，并且所需的内存相对于边数也是线性的.尽管如此，找到给定边的反向边将相对于目标顶点的邻居数是线性的.

Using this representation we can iterate over all neighbours in linear time and also the needed memory is linear with respect to the number of edges. Still, finding the reverse edge for a given edge will be linear with respect to the number of neighbours of the destination vertex.

稍加修改，我们可以改善这一点-如果代替邻居列表，我们保留一些邻居的二进制搜索树，我们可以找到具有对数复杂度的反向边.甚至更好-如果我们使用哈希映射而不是二进制搜索树，我们将具有恒定的摊销复杂性.仍然这种表示方式感觉不对-尽管哈希表仍然是线性的，但它仍有一些内存开销.而且，它仅具有摊销后的恒定复杂度，因此某些操作实际上可能会更慢.

With a slight modification of this representation we could improve that - if instead of neighbours list we keep some binary search tree of the neighbours we could find the reverse edge with logarithmic complexity. And even better - if we use hash map instead of binary search tree we will have constant amortized complexity. Still this representation does not feel right - although still linear, a hash map has some memory overhead. Also it only has amortized constant complexity thus some operations may in fact be slower.

所以我的问题是:哪种图形表示形式适合实现最大的网络流量算法?

So my question is: what graph representation is appropriate to implement maximum network flow algorithms?

推荐答案

我将Ivaylo的表示形式描述为边缘相邻".还有一个端点连续"的表示形式，我认为从一个极其不科学的示例中可以广泛使用它.我在不同的时间都实现了.

I would describe Ivaylo's representation as "edge-contiguous". There's also an "endpoint-contiguous" representation, which I believe from an extremely unscientific sample to be in wider use. I have implemented both at various times.

在没有硬数据的情况下，我的假设是，对于通常的可疑网络流算法，端点连续表示比边缘连续表示更好，因为每次扫描弧时，边缘连续都会产生随机访问，并且端点-连续的，每次将气流推入一个圆弧(大概是在扫描圆弧之前).这种表示的明显优势是它支持非对称图(与网络流无关).这种表示的明显缺点是，更改图的拓扑要慢得多.

Absent hard data, my hypothesis would be that the endpoint-contiguous representation is better for the usual suspects network flow algorithms than the edge-contiguous representation, since edge-contiguous incurs a random access each time an arc is scanned, and endpoint-contiguous, each time flow is pushed on an arc (which presumably was preceded by scanning the arc). The clear upside of this representation is that it supports unsymmetric graphs (not so relevant for network flow). The clear downside of this representation is that changing the topology of the graph is much slower.

表示形式由两个数组组成.具有n + 1个元素的 first 存储具有指定尾部的第一条弧的索引.多余的项是m，即弧的总数，因此，尾号为v的弧的索引为 first [v] (包括)到 first [v + 1] (不包括).在Ivaylo的图中，

The representation consists of two arrays. first, with n+1 elements, stores the index of the first arc with the specified tail. The extra entry is m, the total number of arcs, so that the indexes of arcs with tail v are first[v] inclusive through first[v+1] exclusive. On Ivaylo's graph,

[0] = 0->1, [1] = 0->2,
[2] = 1->0, [3] = 1->2, [4] = 1->3,
[5] = 2->0, [6] = 2->1, [7] = 2->3, [8] = 2->4,
[9] = 3->1, [10] = 3->2, [11] = 3->5,
[12] = 4->2, [13] = 4->5,
[14] = 5->3, [15] = 5->4,

数组 first 是

0, 2, 5, 9, 12, 14, 16.

弧本身存储在以下结构类型的m元素数组中.

The arcs themselves are stored in an m-element array of the following structure type.

struct Arc {
    int head;
    int capacity;
    int symmetric;
};

symmetric 是对称弧的索引.

这篇关于网络流量算法的适当图形表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！