将图转换为规范字符串

我正在寻找一种将图存储为字符串的方式。这些字符串将用作地图中的键，以便两张拓扑相同的图将映射到地图中的相同值。有人知道这样的算法吗？树的节点被标记为允许重复标签。将图转换为规范字符串

该程序是在java中的一个实现将是整洁，但任何可能的算法指针表示赞赏。

2010-02-25 Thomas

您可能会发现相关的以下问题......

Using finite automata as keys to a container

基本上，可以自动使用众所周知的算法从自动机理论的教科书最小化。 Hopcrofts就是一个例子。恰好有一个最小自动机等于任何给定的自动机。但是，最小的自动机可能以不同的方式表示。构建一个安全的规范形式基本上是重新编号节点并使用对定义自动机有重要意义的信息排序邻接表的问题，而不是通过特定于该表示的信息排序。

基本原理应该扩展到一般图。您是否可以最小化图表取决于其语义，但重新编号节点和排序邻接表的基本思想仍然适用。

此处的其他答案假定您的图形有关的事情 - 例如节点具有唯一的标签，可以对其进行排序，这些标签对图形的语义有重要意义，可用于识别邻接矩阵或列表中的节点。例如，如果您对未标记图的形态感兴趣，这种方法根本行不通。对节点进行编号的不同方法（以及因此排序邻接列表）将导致对于恰好以不同方式表示的等同图形的不同规范形式。

至于重新编号等，一种方法是从自动机最小化算法借用和适应原则。基本上...

创建一个块（节点集）的向量。最初，为每类节点填充一个块（即每个不同的节点注释）。这里的修改是我们通过注释详细信息（而不是表示特定的节点ID）对这些信息进行排序。
对于按顺序排列的每个类（注释），评估每个块。如果块中的每个节点都可以沿着当前边缘类型到达同一组下一个块，则不要改变它。否则，根据需要分割它以获得达到此目标的最大块。将这些拆分块聚集在向量中（保留现有的排序，稍微改进一点），然后根据下一个块集合的适当顺序对拆分块进行排序。例如，只要当前块的向量使用位向量，每个块的设置位就可以通过跟随当前边的类型来访问。要订购位向量，请将它们视为大整数。

编辑 - 我忘了提及 - 在第二子弹，只要你分割块，重新启动在载体和第一边缘标注的第一个块。显然，一个朴素的实现会很慢，所以要遵循原则并使用它来适应Hopcrofts最小化算法。

如果最终得到的块中有多个节点，则这些节点是等效的。这是否意味着它们可以合并取决于你的语义，但是每个这样的块内节点的相对顺序显然并不重要。

如果处理可以最小化的图表（例如自动机图），我怀疑最好先将其最小化，尽管我仍然没有掌握实现这一点。

的关键是，当然，以确保您重新编号是敏感只到图形的显著细节 - 其结构和注释 - 而不是只在那里的东西，这样就可以构建一个表示这样的作为节点ID /地址等。

一旦你有了块的排序，派生一个规范形式应该很容易。

来源

2010-02-25 20:33:53 Steve314

啊，是的，我没有想过使用自动机方法。你是对的，那里可能有些东西。然后，我必须挖掘我的旧书。 – Thomas 2010-02-25 20:40:38

一种常见的方式做到这一点是使用Adjacency lists

来源

2010-02-25 19:47:00 stacker

问题是节点上的标签不是唯一的。一个图形可能有一个标有“A”和几个标记为“B”，在这种情况下，邻接表会是这样的 A->若干节点B，B; a-> c; b-> a; b-> c; – Thomas 2010-02-25 19:51:25

如何添加unqiue ID（通过递增int a1-> b1，a2-> c2等串行）？否则，你不能有反funtion http://en.wikipedia.org/wiki/Bijection – stacker 2010-02-25 19:58:42

-1

除了邻接表，有adjacency matrices。你选择哪一个应该取决于你用什么来实现你的Graph类（邻接表通常是更好的选择，但它们都有优点和缺点）。如果你有一个完全不同的Graph实现，可以考虑使用其中的一个，因为它使得很多图算法很容易实现。

另一种选择是，如果可能，在Graph类上覆盖hashCode()和equals()，并将实际的图形对象用作键，而不是转换为字符串。 E：覆盖hashCode()和equals()是我将采用的路线，如果某些顶点没有唯一标记。正如评论中指出的那样，这可能很昂贵，但我认为这取决于Graph类的实现。

如果equals()过于昂贵，那么您应该使用邻接列表或矩阵，但不要只使用节点名称。你必须仔细指定它是什么来标识各个图形和顶点（并且因此它们使它们相等），然后使邻接表的字符串表示使用这些属性而不是节点名称。我建议你的图表write this specification等于操作下来。

来源

2010-02-25 19:53:58 Sean

equals（）方法将执行非常昂贵的，因为我将不得不运行每次调用时的拓扑匹配算法。我宁愿付钱在前面，并允许非常快地插入到地图中。 – Thomas 2010-02-25 19:56:06

如果您有一种将常规图形映射到字符串的算法，并且两个图形映射到相同的字符串（当且仅当它们在拓扑上等效时），那么您的算法为GRAPH AUTOMORPHISM。 图自同构没有已知的多项式时间算法。所以你不可能有（容易）一个多项式时间算法来计算字符串，因为否则你会构造一个先前未知并且非常有效的算法来绘制自同构。

这并不意味着它不可能解决您的类图的问题;这只是意味着对于所有图表来说这是一种困难。

来源

2010-02-25 23:20:21

gSpan引入了'最小DFS代码'，它对图进行编码，使得如果两个图具有相同的代码，则它们必须是同构的。 gSpan在C++和Java中有实现。

来源

2011-09-13 21:25:09 Entong

将图转换为规范字符串

回答

相关问题