如何在图网络中找到闭环 [英] 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.

输入图通常可以简化.有些节点可能只有一条边；它们不能对分区做出贡献，并且可以与边缘一起移除.其他节点具有连接不同节点的两条边.在这里，节点和两条边可以用连接邻居的直接边代替.IE.图 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.

确定哪个区域编号对应于无穷大有一个小问题.要看到这一点，请看一个简单的 () 图:两条边、两个节点和两个区域(内部和外部).由于边和顶点的随机编号，outside 可能最终为 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屋！