如何在图形网络中找到闭环 [英] How to find closed loops in graph networks

问题描述

我有一个由街道和交叉口组成的无向图网络，我想知道是否有任何算法可以帮助我找到闭环，即我可以放置建筑物的地方。

I have an undirected graph network made of streets and crossings, and I would like to know if there is any algorithm to help me finding closed loops, ie places where I can put buildings. Any help appreciated, thanks !

推荐答案

根据对我之前的回答的评论：

Based on comments to my earlier answer:

看起来图形都是无向和平面的，即可以嵌入在没有交叉边缘的2D平面中，和给出了这样的嵌入。这种嵌入将划分平面。例如。图8将平面划分为三个：两个内部区域和无限外部区域。另一种观点是节点的所有边缘是循环排序的。 （这是允许我们应用图论的重要部分）

It seems the graphs are all undirected and planar, i.e. can be embedded in a 2D plane without crossing edges, and one such embedding is given. This embedding will partition the plane. E.g. a figure 8 partitions the plane in three: two "inner" areas and an infinite outer area. An alternative view is that all edges of a node are cyclically ordered. (This is the essential part that allows us to apply graph theory)

分区必须由一个循环包围，但不是所有的循环都可以分割单个区域。然而，在图8的简单情况下，所有三个区域与不同的周期直接相关。

A partition is necessarily enclosed by a cycle, but not all cycles may partition a single area. In the trivial case of a figure 8, though, all three areas are directly associated with a distinct cycle.

输入图通常可以被简化。一些节点可以仅具有单个边;它们不能有助于分割并且可以与边缘一起被去除。其他节点具有连接不同节点的两个边。这里，节点和两个边可以由连接邻居的直接边替换。也就是说图8的图可以简化为两个节点和它们之间的三个边。 （这不是一个必要的步骤，但有助于计算）。

The input graph can generally be simplified. Some nodes may have only a single edge; they can't contribute to the partitioning and can be removed along with the edge. Other nodes have two edges connecting distinct nodes. Here, the node and the two edges can be replaced by a direct edge connecting the neighbors. I.e. a figure 8 graph can be simplified to two nodes and three edges between them. (This is not a necessary step but helps computation).

现在，每个顶点将有两个区域的任一边（因为它们是无向的，左右不是明显的区别）。因此，对于 | V | 顶点，我们需要考虑 2 * | V | 他们一般不明显。如果它们也以该节点的边缘的循环次序相邻，则两个相邻的边（连接到同一节点）可以邻接相同的区域。显然，对于只有两个边的节点，两个边共享两个区域（这就是为什么我们在前面的步骤中消除它们）。对于具有三个边的节点，任何两个边至少共享一个区域。

Now, each vertex will have two areas to either side (since they're undirected, "left and right" aren't obvious distinctions). So, for |V| vertices, we need to consider 2 * |V| sides. They're in general not distinct. Two adjacent edges (connected to the same node) may border the same area, if they're also adjacent in the cyclic order of edges of that node. Obviously, for nodes with only two edges, the two edges share both areas (which is why we'd eliminated them in the previous step). For nodes with three edges, any two edges share at least one area.

因此，下面是如何枚举这些区域：到所有边和顶点。为每个边缘分配一个方向，使其从较低编号边沿到较高边沿。从顶点1开始，右侧，并编号此区域1.跟踪此区域的边界边缘，将相同的数字1分配给其边界边缘的适当边。你这样做是通过在每个节点以逆周期顺序取下一个相邻的边。当你回到你的起点，你知道所有边界的区域1。

So, here's how to enumerate those areas: Assign a sequential number to all edges and vertices. Assign a direction to each edge so it runs from the lower-numbered edge to the higher. Start with vertex 1, right side, and number this area 1. Trace the boundary edges of this area, assigning the same number 1 to the appropriate sides of its boundary edges. You do this by taking at each node the next adjacent edge in counter-cyclical order. When you get back to your starting point, you know all edges bounding area 1.

然后检查第一个顶点的左边缘。如果它不是区域1的一部分，则它是区域2，并且应用相同的算法。接下来，检查顶点2，右侧和左侧等。每次找到一个未编号的边和边时，分配下一个区域号并跟踪新创建区域的边。

You then check the left edge of the first vertex. If it's not part of area 1, then it's area 2, and you apply the same algorithm. Next, check vertex 2, right side and left side, etc. Each time you find an edge and a side that's unnumbered yet, assign the next area number and trace the edges of the newly founded area.

确定哪个区域编号对应于无穷大有一个小问题。为了看到这一点，采取一个简单的（）图：两个边，两个节点和两个区域（内部和外部）。由于边和顶点的随机编号，外部可能结束为1或2。这是不可避免的;在图论中，内部和外部没有区别。

There's a slight problem with determining which area number corresponds to infinity. To see this, take a simple () graph: two edges, two nodes, and two areas (inside and outside). Due to the random numbering of edges and vertices, outside may end up as either 1 or 2. That's unavoidable; in graph theory there's no distinction between inside and outside.

这篇关于如何在图形网络中找到闭环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！