标签: subgraph

我将开始一个关于自动机和图论的科学项目,我正在寻找一个支持以下功能的图库:

• 有向/无向图
• 图同构测试(即图g1同构wrt g2？)
• 子图同构测试(即图形g1与g2的子图同构？)
• 图搜索,访问等
• 可能,非常快,因为我需要做一些严肃的计算

我知道Boost Graph Library,但据我从文档中理解,它缺少子图测试.

所以,我的问题是:哪个是最好的c ++图形库,好吗？他们不需要为我需要的每个功能提供支持,我知道现有的库当然没有完全满足我的需求.

我正在尝试使用创建图表dot.我到现在为止给出的图表如下,并给出了代码.

码

digraph top {
  node [shape=record ,penwidth = 2,fontsize=25];
  graph [labeljust=l]
  ratio="fill";

  subgraph cluster_1 {
    label = "Box 1";
    fontsize=40;
    subgraph cluster_2 {
      label = "Box 2";
      fontsize=38

      subgraph cluster_3 {
        label = "Box 3";
        fontsize=36;

        subgraph cluster_4 {
            label = "Box 4";
            fontsize=34;



            subgraph cluster_7 {
                    label = "Box 5";
                    fontsize=30;
                    color=blue;
                    style="dashed";
                    subgraph cluster8 {
                        color=red;
                        label = "Box 6";
                        subgraph cluster9 {
                            label = "Box 7";
                            subgraph cluster10 {
                                label = "Box 8";
                                l4 …

我有一个mygraph有10,000个节点和~145,000个边的igraph对象,我需要从这个图中创建一些子图,但是它们的大小不同.我需要的是从确定的大小(从5个节点到500个节点)创建子图,其中所有节点都连接在每个子图中.我需要为每个大小创建~1,000个子图(即,大小为5的1000个子图,大小为6的1000个,依此类推),然后根据不同的节点属性为每个图计算一些值.我有一些代码,但需要很长时间才能进行所有计算.我想在使用该graphlets功能以获得不同的大小,但每次我在计算机上运行它都会因内存问题而崩溃.

这是我正在使用的代码:

第一步是创建一个函数来创建不同大小的子图并进行所需的计算.

random_network<-function(size,G){
     score_fun<-function(g){                                                        
          subsum <- sum(V(g)$weight*V(g)$RWRNodeweight)/sqrt(sum(V(g)$RWRNodeweight^2))
           subsum
           } 

      genes.idx <- V(G)$name
      perm <- c()
      while(length(perm)<1000){
           seed<-sample(genes.idx,1) 
           while( length(seed)<size ){
                tmp.neigh <- V(G)[unlist(neighborhood(G,1,seed))]$name
                tmp.neigh <- setdiff(tmp.neigh, seed)
                if( length(tmp.neigh)>0 )  
                seed<-c(seed,sample(tmp.neigh,1)) else break 
            }
      if( length(seed)==size )
      perm <- c(perm,score_fun(induced.subgraph(G,seed)))
      } 
      perm
     } 

第二步是将函数应用于实际图形

 ### generate some example data
 library(igraph)
 my_graph <- erdos.renyi.game(10000, 0.0003)
 V(my_graph)$name <- 1:vcount(my_graph)
 V(my_graph)$weight <- rnorm(10000)
 V(my_graph)$RWRNodeweight <- runif(10000, min=0, max=0.05)

 ### Run the code to get the subgraphs from different …

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

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

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

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

我创建了一个轻量级图形库,它有3个对象(Vertex,Edge,Graph)和1个函数(topo_sort),它们看起来像:

class DAGError(Exception): pass

def topo_sort(graph):
    sorted_list = []
    def visit(vertex):
        nonlocal sorted_list
        if vertex.idle:
            raise DAGError('Graph has at least one cycle.')
        if not vertex.done:
            vertex.idle = True
            for neighbor in vertex.vertices():
                visit(neighbor)
            vertex.done = True
            vertex.idle = False
            sorted_list.insert(0, vertex)
    queue = [vertex for vertex in graph.vertices() if not vertex.done]
    while queue:
        visit(queue.pop(0))
    return iter(sorted_list)

如果我有一个平坦的DAG,这工作正常.但我想要实现的是将子图(或嵌套图)添加到我的主图中,正如您在此图中所示我绘制的:

嵌套/子图插图http://f.cl.ly/items/2o0s1c2W1o2C0i0g0l0r/subgraph_illustration3.png

这仍然是一个DAG,所以如果我对此运行我的函数,正常 topo_sort输出将是这样的:

V0, V3, V1, V5, V4, V8, V7, V12, V11, V13, V14, V2, V6, V10, V9, V15, …

我正在寻找一种算法来检查给定的图是否是另一个给定图的子图.

我没有什么条件让这个NP完全问题更可行.

• 图表有大约<20个顶点.
• 图是DAG.
• 所有顶点都是非唯一标注的,主图和子图中的相应顶点应具有相同的标签.我不知道我是否使用了正确的术语(因为我没有采用图论理论课程......).它将是这样的:

线图A-B是A-B-A的子图,但A-A不是A-B-A的子图.

任何建议都没问题.这不是一个功课问题顺便说一下.:d

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

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

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

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

我想知道我是否可以使用networkx从输入大图中提取子图中具有特定节点数的所有可能的诱导子图(graphlet),或者是否有其他包可以完成这项工作？例如,如果我有一个大图,以networkx邻接列表格式说明,

图G:

1 2 3 7
2 1 4
3 1 4 6 5
4 2 3 5
5 3 4 6
6 3 5 7
7 1 6

这看起来像

如果我想用3个节点提取graphlet,算法应该返回给我

subgraph1:

1 2 3
2 1
3 1

[(1,2),(1,3)] subgraph2:

1 3 7
3 1
7 1

[(1,3),(1,7)] subgraph3:

3 4 5
4 3 5
5 3 4

[(3,4),(3,5),(4,5)]

subgraph4,subgraph5,subgraph6 ...

以下是@Hooked建议的问题代码.假设n = 3

import itertools
target = nx.complete_graph(3)
for sub_nodes in itertools.combinations(g.nodes(),len(target.nodes())):
    subg = g.subgraph(sub_nodes)
    if nx.is_connected(subg):
        print …

我已将我的问题简化为以下简单示例：

digraph {
subgraph {rank=same; 0 -> 1 -> 2;}
0 -> 2 [label="A"];
2 -> 0 [label="B"];
}

产生

在将 0、1 和 2 保持在同一等级（原始示例是在更大图的上下文中）的同时，我需要可辨别 A 和 B 边。即边缘与标签清晰匹配，标签可读。

我想象的一种解决方案是在指定的边缘连接上使用端口

0:ne -> 2:nw [label="A"];
2:sw -> 0:se [label="B"];

然而这会产生

其他想法？我正在生成具有相同问题的更大图形，因此最佳解决方案不是完全临时手动放置边/标签。

编辑：较大生成图的（仍然简化）示例如下。

digraph {
size = "6,8.5";
ratio = "fill";
node [shape = circle];
node [fontsize = 24];
edge [fontsize = 24];
{graph [rank=same]; edge[color=invis];1;}
{graph [rank=same]; edge[color=invis];2 -> 0 -> 3 -> 4;}
0 -> 0 [label="6: 0.1764"];
0 …

我想知道是否可以在 Graphviz 中做这样的事情：

如您所见，节点“two”位于两个集群内，而集群不是递归的。

注意：图像由 Dia 制作。