子图同构是一个NP完全问题.最广泛使用的算法是Ullman提出的算法.

有人可以用外行的语言向我解释算法吗？我读了他的上述文章,但不太了解.

该问题还有哪些其他算法？

我正在做一个图像处理项目.

我有一个包含以下属性的图表:

• 无向
• 不加权
• 每个顶点至少有2个,最多连接6个边.
• 顶点数将<100
• 图形是静态的,不能添加/删除或编辑顶点/边.

我正在寻找顶点的随机子集(至少2)之间的路径.路径应该是只经过任何顶点一次的简单路径.

我的最终目标是拥有一组路线,以便您可以从其中一个子集顶点开始并到达任何其他子集顶点.在跟踪路由时,不必通过所有子集节点.

我发现的所有算法(Dijkstra,Depth first search等)似乎都在处理两个顶点和最短路径之间的路径.

是否有一个已知的算法可以为我提供连接这些顶点子集的所有路径(我想这些是子图)？

编辑:

我创建了一个(警告!程序员艺术)动画gif来说明我想要实现的目标:http://imgur.com/mGVlX.gif

预处理和运行时分为两个阶段.

前处理

1. 我有一个图形和一个顶点的子集(蓝色节点)
2. 我生成连接所有蓝色节点的所有可能路由

运行

1. 我可以从任何蓝色节点开始选择任何生成的路线并沿着它行进以到达我的目的地蓝色节点.

所以我的任务更多的是创建连接所有蓝色节点的所有子图(路由),而不是创建A-> B的路径.

这就是生成的图形当前的外观: 以下是此代码:

  digraph {
  rankdir=TB;
  subgraph cluster01 {
    label="1.fázis"

    aSTART;
    node [shape = doublecircle]; a001; 
    node [shape = ellipse];

    aSTART -> a0 [ penwidth = 3 label = "0" ];
    a0 -> a00 [ penwidth = 3 label = "0" ];  
    a00 -> a001 [ penwidth = 3 label = "1" ];


    a0 -> aSTART [ label = "1" ];  
    a00 -> a00 [ label = "0" ];  
    a001 -> a0 [ label = "0"];
    a001 -> aSTART [ label …

我有代码显示两个子图:

graph {
    rankdir=LR;
    subgraph cluster01 {
        label="t=0"
        a0 [label="A"];
        a1 [label="B"];
        a2 [label="C"];
        a5 [label="E"];
        a0 -- a1;
        a1 -- a2 ;
        a2 -- a0;
    };

    subgraph cluster02
    {
        label="t=10"
        b0 [label="A"];
        b5 [label="E"];
        b1 [label="B"];
        b2 [label="C"];

        b0 -- b1;
        b2 -- b5;
    };

    a0--b0 [style=dotted];
    a1--b1 [style=dotted];
    a2--b2 [style=dotted];
    a5--b5 [style=dotted];
}

此代码显示两个子图,如下所示:

但我希望这样:

我希望有人能帮助我修复"rankdir"来完成它.

假设我有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的子图中的一个.有关如何输出每个子图的任何想法吗？

我有专利发明人的合作数据.每个发明人都是一个节点,每个边缘代表两个发明者合作的专利.一些专利有> 2个发明人,因此一些专利用多个边缘表示.

我想要了解至少有一位发明家位于博伊西的专利,但并非所有发明家都位于博伊西.其他专利和发明人需要从选择中排除.

例如:

gg <- graph.atlas(711)
V(gg)$name <- 1:7
V(gg)$city <- c("BOISE","NEW YORK","NEW YORK","BOISE","BOISE","LA","LA")
V(gg)$color <- ifelse(V(gg)$city=="BOISE", "orange","yellow")
gg<-delete.edges(gg, E(gg, P=c(1,2,2,3,2,7,7,6,7,3,3,4,3,5,4,5,5,6,6,1))) 
gg <- add.edges(gg,c(1,4,4,5,5,1),attr=list(patent=1))
gg <- add.edges(gg,c(7,5,5,4,4,7),attr=list(patent=2))
gg <- add.edges(gg,c(7,3,3,5,5,7),attr=list(patent=3))
gg <- add.edges(gg,c(2,7,7,6,6,2),attr=list(patent=4))
gg <- add.edges(gg,c(6,4),attr=list(patent=5))
plot(gg, edge.label=E(gg)$patent)

生产:

网络示例http://i60.tinypic.com/34teolg.png

在这个网络中,我只想要将所有入射在专利2,3,5边缘的节点子图.

在此示例中,节点1不应该在子图中结束.此外,还应排除从专利#1的节点5到节点4的边缘.

我一直在努力解决这个问题.这可能吗？

我有下图，我需要从左到右 GHKMNOP 排列集群/子图。每个子图的内容都很好。我该如何实现？我曾尝试按照其他问题中的描述添加不可见的边缘，但它没有按预期工作。

G/H 盒子需要按正确的顺序排列，但玩权重并不奏效......

下面的代码在底部呈现图像。00/01 节点设置为可见以显示顺序混淆的位置。

digraph {
    {
        edge [ style=invis ];
        rank=same;
        00 [  ];
        01 [  ];
        02 [ style=invis ];
        03 [ style=invis ];
        04 [ style=invis ];
        05 [ style=invis ];
        06 [ style=invis ];
        00 -> 01 -> 02 -> 03 -> 04 -> 05 -> 06 [ weight=1000 ];
    }

    subgraph cluster_GG {
        label="Journal litra GG 1829";

        GG27 [ label="27" ];
        GG112 [ label="112" ];
        GG177 [ label="177" ];
        GG921 [ label="921" …

如何将子图簇的标签定位在左侧而不是居中？

digraph mygraph {
    test1;

    subgraph cluster_mysubgraph {
        label = "This text should be at the left of the subgraph - not centered!";

        test2;
        test3;
        test4;
        test5;
        test6;
        test7;
    }

    test1 -> {test2, test3, test4, test5, test6, test7};
}

我已经下载了一个实现VGG16 ConvNet的tensorflow GraphDef，我使用它来执行以下操作：

Pl['images'] = tf.placeholder(tf.float32, 
                          [None, 448, 448, 3],
                          name="images") #batch x width x height x channels
with open("tensorflow-vgg16/vgg16.tfmodel", mode='rb') as f: 
    fileContent = f.read()

graph_def = tf.GraphDef()
graph_def.ParseFromString(fileContent)
tf.import_graph_def(graph_def, input_map={"images": Pl['images']})

此外，我具有与的输出同质的图像特征"import/pool5/"。

我怎么能告诉我的图不想使用他的输入"images"，而只是张量"import/pool5/"作为输入？

谢谢 ！

编辑

好吧，我知道我还不太清楚。情况如下：

我正在尝试使用GraphDef格式的预训练VGG16来实现 ROI池的这种实现。所以这是我的工作：

首先，我加载模型：

tf.reset_default_graph()
with open("tensorflow-vgg16/vgg16.tfmodel",
          mode='rb') as f:
    fileContent = f.read()
graph_def = tf.GraphDef()
graph_def.ParseFromString(fileContent)
graph = tf.get_default_graph()

然后，我创建我的占位符

images = tf.placeholder(tf.float32, 
                              [None, 448, 448, 3],
                              name="images") #batch x width x …

输入
具有 n 个顶点和一个整数 k 的无向图 G，使得 k 整除 n。
所有顶点的集合将由 V 表示。

OUTPUT
一组 S 的顶点集，使得：

1. S 有 k 个元素
2. S 的每个元素都是 G 中的一个完全子图（每个元素中的所有顶点在 G 中彼此共享一条边）
3. S 的所有元素都是互斥的（元素之间没有共同的顶点）
4. S 的所有元素的并集等于 V
5. S 的所有元素都有基数 n / k

背景
我经营一个小型剧本阅读小组，我们有时喜欢阅读大型剧本。我想以这样的方式为一小群人演一场大型戏剧，这样一个人就不会扮演一组彼此共享场景的角色。我意识到这个问题可以用图论来表述，我很好奇一个好的解决方案是什么样的。