使用iGraph的哈密顿路径 [英] Hamiltonian path using iGraph

问题描述

我开始评估igraph库及其功能. 我需要计算由igraph_de_bruijn()函数生成的图的哈密顿路径. igraph库中是否有为此提供的现成函数?我不想从头开始实施它. 用C语言编写的示例将是完美的.

I started evaluating igraph library and its functionality. I need to calculate hamiltonian path of a graph generated by igraph_de_bruijn() function. Is there any ready made function in igraph library for that? I don't want to implement it from scratch. An example in C would be perfect.

推荐答案

哈密顿路径问题可以转换为子图同构问题，对此igraph具有多个功能.构造一维晶格图(一条线")，其顶点数与图形的顶点数相同，然后使用亚同构函数搜索该模式.

The Hamiltonian path problem can be cast as a subgraph isomorphism problem, for which igraph has several functions. Construct a 1D lattice graph (a "line") with the same number of vertices as your graph, then search for this pattern using subisomorphism functions.

以下是使用 Mathematica界面的示例.

hamiltonianPath[g_] := 
 Values@First@IGLADGetSubisomorphism[
    GridGraph[{VertexCount[g]}],  (* <- this is just a 1D lattice, like O-O-O-O *)
    g                             (* <- this is the graph we want to match *)
 ]

让我们尝试十二面体图:

Let's try a dodecahedral graph:

g = PolyhedronData["Dodecahedron", "SkeletonGraph"]

以下是顶点需要访问的顺序:

Here's the order the vertices need to be visited in:

path = hamiltonianPath[g]

(* {1, 16, 7, 3, 14, 9, 17, 19, 5, 11, 12, 8, 4, 20, 6, 2, 13, 18, 10, 15} *)

让我们形象化:

HighlightGraph[g, PathGraph[path], GraphHighlightStyle -> "Thick"]

我仅将Mathematica用于说明.使用C接口时，过程相同.

I use Mathematica only for illustration. The procedure is identical when using the C interface.

从C 进行>时，可以使用igraph_subisomorphic_lad查找单个亚同构(请参见map参数).使用igraph_ring创建模式(对于汉密尔顿路径，使用circular=false，对于汉密尔顿循环，使用circular=true).如果要使用十二面体作为测试用例，则可以使用igraph_famous来获得.

When you do this from C, you can use igraph_subisomorphic_lad to find a single subisomorphism (see the map argument). Use igraph_ring to create the pattern (circular=false for Hamiltonian path, circular=true for Hamiltonian cycle). If you want the dodecahedron for a test case, you can get it with igraph_famous.

这篇关于使用iGraph的哈密顿路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！