algorithm - 图变换——顶点到边，边到顶点

Question

是否有任何算法或有任何名称可以将图转换为可以将边转换为顶点并将顶点转换为边的图？就为了我们可以从中得到一个新的图表或任何与这个问题类似的东西？我不确定这是否真的有意义，但如果你能给我任何关于此类问题的提示，我会很高兴。

Answer 1

LineGraph 是 Wolfram 语言中的一个内置函数：

http://reference.wolfram.com/language/ref/LineGraph.html

这就是它的作用：

• LineGraph[g] 中的每个顶点对应于 g 中的一条边。
• 对于无向图 g，如果 LineGraph[g] 中的两个顶点的对应边共享一个公共顶点，则它们是相邻的。
• 对于有向图g，如果LineGraph[g] 中的两个顶点对应的边是相连的，则它们是相邻的，即一条边的目标是另一条边的源。
• LineGraph 适用于无向图、有向图和多重图。

Answer 2

您要的是折线图。您可以使用networkx line_graph 函数来创建给定图形的折线图或对偶图。但是，请注意，此函数不会传播原始图形中的数据，因此如果需要，您将不得不破解它。

Answer 3

您是否考虑过基于模式的图形转换？就像你会

• 搜索图形模式，例如您想变成节点的边类型，以及
• 定义将该边转换为节点/顶点的操作，例如将所有边属性转换为新节点/顶点的属性。

在图变换文献中，这两个步骤被称为图变换规则的左侧和右侧。

该领域有很多可用的科学文献，例如：http ://www.springer.com/de/book/9783319211442

还有专门的图形转换开发解决方案，例如Soley Studio。

希望有帮助。

Answer 4

我相信您可以使用以下 Python 库轻松地将边缘转换为顶点：http: //networkx.lanl.gov/

您可以获取边列表、节点列表并交换两者以构建新图。你只需要一些 Python 的（基本）知识。