graph6格式如何工作? [英] How does graph6 format work?

问题描述

我一直到处都在寻找.g6或graph6格式的工作方式，我不知道它甚至如何工作，我发誓它就像魔术一样.

F?B~w

这是一个以ASCII形式表示的图形. Wolfram Mathematica，Sage和Maple可以解释它，仅举几例，并为我们提供视觉效果.但是，在花了数小时研究Sage的开源代码之后，我无法终生弄清楚他们如何将其理解为图表.

我想知道是否可以在上述图形中搜索汉密尔顿循环，而不必将其转换为邻接矩阵?还是如果不可能，我们如何将其转换为邻接矩阵?

任何帮助将不胜感激.

解决方案

航海来源中有一个实现)两种相关格式:sparse6(用于稀疏图)和digraph6(用于有向图).

digraph6格式似乎很新(在nauty 2.6中添加了)，并且与graph6相似，只是为了处理有向图，该格式对减去对角线的整个邻接矩阵进行编码，而不仅仅是上三角. >

I've been looking all over the place on how the .g6 or graph6 format works and I have no idea how it even works I swear it's like magic.

F?B~w

That is a graph represented in ASCII form. It can be interpreted by Wolfram Mathematica, Sage, and Maple to name a few and give us a visual. However, after hours of diving into the open source code of Sage, I cannot for the life of me figure out how they can read that as a graph.

I want to know if it is possible to search the above graph for Hamiltonian Cycles without having to convert them into Adjacency Matrices? Or if that is not possible how do we even convert it into an Adjacency Matrix?

Any help would be appreciated.

解决方案

The reference to the format description was already provided by Oliver Charlesworth, but in short the basic idea is to encode the graph size and the upper triangle of the adjacency matrix in ASCII-printable characters.

1. From your original undirected graph, compute the adjacency matrix. This is guaranteed to be symmetric so all we care about is the upper triangle of this matrix, excluding the diagonal which will be identically zero.

2. Next, build a bit vector of size n*(n-1)/2 by traversing the upper triangle of the matrix row by row. For example, for a 4x4 matrix the traversal would be (1,2),(1,3),(1,4),(2,3),(2,4),(3,4).

3. Prepend your bit vector with the graph size n (as a binary word) and break the resulting bit vector into chunks of 6 bits each.

4. Transform each 6-bit chunk into an integer in the range 63 to 126, then transform each of these to the corresponding ASCII character and concatenate them.

Note the graph6 format does not support directed or weighted graphs. I believe it was created by Brendan McKay (there's an implementation of it in the nauty source) and there are two related formats: sparse6 (for sparse graphs) and digraph6 (for directed graphs).

The digraph6 format appears to be fairly new (added in nauty 2.6) and is similar to graph6 except that in order to handle directed graphs, the format encodes the entire adjacency matrix minus the diagonal, not just the upper triangle.

这篇关于graph6格式如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！