标签: subgraph

在DOT语言中GraphViz,我试图表示一个依赖关系图.我需要能够在容器内部拥有节点,并且能够使节点和/或容器依赖于其他节点和/或容器.

我subgraph用来代表我的容器.节点链接工作正常,但我无法弄清楚如何连接子图.

鉴于下面的程序,我需要能够连接cluster_1并cluster_2使用箭头,但我尝试过的任何东西都会创建新节点而不是连接集群:

digraph G {

    graph [fontsize=10 fontname="Verdana"];
    node [shape=record fontsize=10 fontname="Verdana"];

    subgraph cluster_0 {
        node [style=filled];
        "Item 1" "Item 2";
        label = "Container A";
        color=blue;
    }

    subgraph cluster_1 {
        node [style=filled];
        "Item 3" "Item 4";
        label = "Container B";
        color=blue;
    }

    subgraph cluster_2 {
        node [style=filled];
        "Item 5" "Item 6";
        label = "Container C";
        color=blue;
    }

    // Renders fine
    "Item 1" -> "Item 2";
    "Item 2" -> "Item …

我有一个图表,其中包含未知数量的断开连接的子图.什么是一个好的算法(或Java库)来找到它们？

我想让我的图表看起来像这样:

但我只能得到这个:

问题是,rankdir 不工作在subgraph.那么,如何模仿呢？

代码:

digraph G {
    node [shape = circle]
    0 [style = invis]

    0 -> "0A"

    subgraph clusterA {
        label=A
        "0A"
        "1A"
        "2A" -> "0A" [label=•]
    }

    subgraph clusterB {
        label=B
        "0B"
        "1B"
        "2B" -> "0B" [label=•]
    }

        subgraph clusterC {
        label=C
        "0C"
        "1C"
        "2C" -> "0C" [label=•]
    }

    subgraph clusterD {
        label=D
        "0D"
        "1D"
        "2D" -> "0D" [label=•]
    }

    subgraph clusterE {
        label=E
        "0E"
        "1E"
        "2E" -> "0E" [label=•]
    }

    subgraph clusterF …

我想用以下代码对一些节点进行分组

digraph dataflow {
    subgraph pipeline {
        relations;
        synonyms;
        articles;
    }
    subgraph lucene {
        index;
        search;
    }
    training_data - > index;
    relations - > search;
    synonyms - > index;
    articles - > index;
    training_data - > evaluation;
}

但dot并不关心子图:

我有一个未加权的连接图.我想找到一个连接的子图,它肯定包含一组特定的节点,并且尽可能少的附加内容.怎么可以实现呢？

为了以防万一,我将使用更精确的语言重述问题.设G(V,E)为未加权,无向连通图.设N是V的某个子集.找到G(V,E)的最小连通子G'(V',E')的最佳方法是什么,N是V'的子集？

近似没问题.

我一直在通过python的Bulbflow处理Neo4j,现在需要一种方法来保存/导出子图.我已经看过Java甚至Ruby的方法,但是一个简单的Python方法似乎隐藏了我...

到目前为止,我找到了两条潜在的途径:

1. 通过py2neo访问Geoff,但是从大型本地neo4j数据库或neo4jserver中提取子图的文档很少令人惊讶.

2. 使用Networkx:我发现networkx可以加载来自多种不同格式的图形(我不确定neo4j存储它们的dbs的格式),但是我还没有找到一种方法只将一个子图提取到Networkx中.我认为这应该从gremlin查询完成,但我不知道如何去做.

我偏爱Networkx路径,因为它还附带了我希望应用于子图的网络分析算法.我觉得它也可以避免Bulbflow和py2neo之间的潜在冲突,虽然我不确定是否会存在这样的冲突.

任何建议将不胜感激!

提前致谢

是否有已知的算法或方法来查找图中的所有完整子图？我有一个无向的,未加权的图形,我需要找到其中的所有子图,其中子图中的每个节点都连接到子图中的每个其他节点.

是否有现有的算法？

这是图表的消费税.

给定具有n个顶点和m个边的无向图G和整数k,给出O(m + n)算法,该算法找到G的最大诱导子图H,使得H中的每个顶点具有度≥k,或证明不这样的图存在.图G =(V,E)的诱导子图F =(U,R)是G的顶点V的U的子集,以及G的所有边R,使得每个边的两个顶点都是U.

我最初的想法是这样的:

首先,这个消息实际上要求我们拥有度数大于或等于k的所有顶点S,然后我们删除S中没有任何边连接到其他边的顶点.然后精化的S是H,其中所有顶点都具有度> = k并且它们之间的边是R.

另外,它问O(m + n),所以我认为我需要一个BFS或DFS.然后我卡住了.

在BFS中,我可以知道顶点的程度.但是一旦我得到v(一个顶点)的程度,我不知道除了它的父之外的其他连接顶点.但如果父母没有度> = k,我就无法消除v,因为它可能仍然与其他人联系.

任何提示？

编辑:

根据@Michael J. Barber的回答,我实现了它并在这里更新代码:

任何人都可以看看代码的关键方法public Graph kCore(Graph g, int k)吗？我做得对吗？是O(m + n)？

class EdgeNode {
   EdgeNode next;
   int y;
}

public class Graph {
   public EdgeNode[] edges;
   public int numVertices;

   public boolean directed;

   public Graph(int _numVertices, boolean _directed) {
      numVertices = _numVertices;
      directed = _directed;
      edges = new EdgeNode[numVertices];
   }

   public void insertEdge(int x, int y) {
      insertEdge(x, y, directed);
   } …

我正在尝试找到工具/算法来搜索与面向图中指定模式相对应的部分,例如:

A-> B-> C或或A- - B-> C.

请建议我搜索的方向.

我的意思是模式匹配.我需要找到匹配指定模式的所有节点和边的组

我有一个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 …