标签: isomorphism

在我参与过的一个项目中,出现了同构与单态的主题.

一点背景:我不是图论的专家,也没有正式的培训.但是这个主题在化学中非常重要,化学家期望在他们使用的结构搜索系统中进行特定类型的子图匹配.

如果目标图A具有n个节点和m个边,则化学家将接受子图匹配,其中查询图B具有n个节点和m-1个边.唯一的要求是B中的每个边都应该存在于A中.例如,6个节点的线性链应匹配6个节点的循环.

这种匹配是同构还是单态？也许还有别的东西？

假设我有2个图A和B,我想知道A是否是B的子图.节点包含属性,比如'size'和'material'.

当我跑:

GM = networkx.algorithms.isomorphism.GraphMatcher(B,A)
print networkx.algorithms.isomorphism.subgraph_is_isomorphic()

这仅仅按边缘匹配图形,而不是边缘和属性.

关于如何检查属性的任何线索？

另外,假设B包含2个连通图A.

当我跑:

GM.mapping

这将仅输出A的子图中的一个.有关如何输出每个子图的任何想法吗？

我正在尝试理解 Nauty 算法。遵循这篇文章：http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf
在该算法中，根据顶点的度数以及一个组与其他组相对应的相对度数（组动作）来区分顶点。通过这种方式，我们得到的组为：

1379|2468|5
完成此步骤后，将按照本文第 7 页中所述完成拆分。本文中的一张图片是：

我无法理解分裂是如何进行的， 1379|2468|5为什么会分到不同的组，然后又1|9|37|68|24|5 分到另一个组。1937

假设我有一个大的(几千个节点)有向图G和一个小得多(3-5节点)的有向图g.我想计算G中有多少g的同构.换句话说,我想知道G中有多少个唯一的节点集匹配g.我意识到这是子图同构问题的一个实例,因此是NP完全的.但是,考虑到你可能认为g很小,有没有合理有效的算法呢？

我想将NetworkX Graph对象用作Python中的键dict.但是,我不希望比较的默认行为(即,通过对象的地址).相反,我希望同构图指代是相同元素的关键dict.

这种行为是否已在某处实施？我找不到这个方向的任何信息.

如果我必须自己实施,以下评估是否现实？

• 换networkx.Graph上课.
• 定义__eq__它调用is_isomorphic.
• __hash__以某种方式定义(欢迎建议).

我认为我必须使这个包装的Graph不可变,因为:

如果一个类定义了可变对象并实现了一个__eq__()方法,那么它就不应该实现__hash__(),因为hashable集合的实现要求一个键的哈希值是不可变的(如果对象的哈希值改变,它将在错误的哈希桶中).

给定两个图，如何在这两个图中找到同构的子图。目前，我只是发现 igraph 已经实现了 igraph_subisomorphic_vf2，它有两个图 G 和 H 作为输入，并确定 G 是否包含与 H 同构的子图。

由于我没有在 igraph 中找到任何其他可以直接解决我的问题的函数，我目前认为一种方法是从给定的图中枚举所有可能的子图，然后使用函数 igraph_subisomorphic_vf2 来确定该子图是否与另一个同构给定的图形。

对于我数据集中的图，平均节点数是40个，不知道是不是一个可行的方法来解决这个问题？

有没有更好的方法可以在给定的两个或更多图中找到最大子图？

谢谢！

现在我正在发现Este.js并且我对同构应用程序有一个小问题。我不明白如何在使用 renderToString() 渲染服务器端之前进行 api 调用。

一种解决方案是使用 React Router 在路由器级别进行所有数据获取。根据顶级路由，我可以预测需要哪些数据，进行 api 调用，然后调用 React.renderToString。

很好，但我仍然必须在组件级别和路由器级别声明数据依赖项。我最终编写了两次相同的代码，而且我认为这不是最好的方法。

编辑：好的，现在我可以做一些我想做的事情。使用 React-Router 和这个链接我已经能够做到以下几点：

给这个全局应用状态，我想在指向 /todos 时预取 todos

初始状态.js

{
  auth: {
    data: null,
    form: null
  },
  examples: {
    editable: {
      state: null,
      text: 'Some inline-editable text.'
    }
  },
  i18n: {
    formats: {},
    locales: initialLocale,
    messages: messages[initialLocale]
  },
  pendingActions: {},
  todos: {
    editables: {},
    newTodo: {
      title: ''
    },
    list: [{
      id: 1,
      title: 'first todo yipiyo'
    }]
  },
  users: {
    viewer: null
  } …

我正在尝试使用Boost vf2_subgraph_iso()来检测子图同构.

我可以在简单的图形上成功完成此操作,但不能在多图形(允许有多个边缘的图形)上执行此操作.

考虑检测以下G1和G2之间的子图同构:

G1是G2的子图,我想使用以下代码检测:

#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>

int main()
{
  // Define edge property
  typedef boost::property<
    boost::edge_name_t,
    char
  > edge_property;

  // Define graph type
  typedef boost::adjacency_list<
    boost::vecS,           // OutEdgeListS
    boost::vecS,           // VertexListS
    boost::bidirectionalS, // DirectedS
    boost::no_property,    // VertexProperties
    edge_property,         // EdgeProperties
    boost::no_property,    // GraphProperties
    boost::listS           // EdgeListS
  > MyGraphType;

  // Build graph G1
  MyGraphType g1;
  std::vector<MyGraphType::vertex_descriptor> v1(3);
  for (auto itr = v1.begin(); itr != v1.end(); ++itr) {
    *itr = boost::add_vertex(g1);
  }
  boost::add_edge(v1[0], v1[1], …

我正在阅读“Scala 编程”一书（红皮书）。

在关于 Monoids 的章节中，我理解了 Monoid 同态是什么，例如：M具有串联和length函数的 String Monoidf保留了Monoid结构，因此是同态的。

M.op(f(x), f(y)) == M.op(f(x) + f(y))
// "Lorem".length + "ipsum".length == ("Lorem" + "ipsum").length

引用这本书（根据记忆，如果我错了，请纠正我：

当这在两个方向上发生时，它被命名为 Monoid isomorphisim，这意味着对于 monoidsM, N和函数f, g，f andThen g和g andThen f是identity函数。例如StringMonoid 和List[Char]Monoid with concatenation 是同构的。

但我不能看到看到这一个实际的例子，我只能想到f的length功能，但会发生什么g？

注意：我看过这个问题：What are isomorphism and homomorphisms。

是否有 Haskell 库提供（或协助编写）总和类型与关联的异构总和类型之间的通用同构？

采用以下总和类型，

data TR = TR_Index | TR_Inner R

现在我们将它与异质总和相关联NS I xs（其中“xs”由类型类定义；见MotleyRouteSubRoutes下文）。然后定义一个同构来来回转换：

instance MotleyRoute TR where
  -- `SingletonRoute s` is isomorphic to `()`
  -- `PrefixedRoute s r` is isomorphic to `Const r s`
  type MotleyRouteSubRoutes TR = 
    '[ SingletonRoute "index.html"
     , PrefixedRoute "inner" R
     ]
  motleyRouteIso =
    iso
      ( \case
          TR_Index -> Z $ I SingletonRoute
          TR_Inner r -> S $ Z $ I $ PrefixedRoute r
      )
      ( \case
          Z (I SingletonRoute) -> …