标签: graph-theory

给出一些输入词,我希望有一个实用程序,它将返回一组不同的相关术语,短语或概念.需要注意的是,它需要有一个大的术语图表,否则该功能将不会非常有用.

例如,提交"棒球"将返回

["shortstop", "Babe Ruth", "foul ball", "steroids", ... ]

谷歌集是我能找到这种功能的最好的例子,但我不能使用它,因为他们没有公共API(我不会违反他们的TOS).此外,单字输入不会获得非常多样化的结果.我正在寻找切线上的解决方案.

我最接近实验的是使用WikiPedia的API来搜索类别和反向链接,但是无法通过"相关性"或"流行度"直接对这些结果进行排序.如果没有这个,建议清单是庞大而且遍布整个地方,这不是立即有用而且非常难以减少.

使用词库也可以最低限度地工作,但这会遗漏任何专有名词或切向相关的术语(如上面列出的任何结果).

我很乐意重用一个开放服务,如果存在,但我还没有找到足够的东西.

我正在寻找一个既方式来实现这一点无论在公司内部有体面填充的起始一套,或重复使用一个免费的服务,提供了这一点.

有解决方案吗？ 提前谢谢!

更新: 感谢您提供令人难以置信的密集和信息丰富的答案.我会在6到12个月内选择一个成功的答案,当我希望了解你所有建议=)

这是Vazirani的算法书中的一个问题

该问题的输入是树T,边缘上具有整数权重.权重可以是负数,零或正数.给出线性时间算法以找到T中最短的简单路径.路径的长度是路径中边缘权重的总和.如果没有重复顶点,则路径很简单.请注意,路径的端点不受约束.

提示:这与在树中查找最大独立集的问题非常相似.

如何在线性时间内解决这个问题？

这是我的算法,但我想知道它是否是线性时间,因为它与深度优先没什么不同:

1. 遍历树(深度优先)
2. 保留索引(节点)
3. 添加值
4. 做(1)直到树的尽头
5. 比较总和并打印路径和总和

这个问题与此主题类似,但没有确定的答案.

是否有一个C++(或任何其他语言)库,其中包含用于图着色问题的算法组合？

当然有天真贪婪的顶点着色算法,但我对更有趣的算法感兴趣,如:

1. 维基的"精确算法"部分中提到的算法
2. 利用特殊图形属性的近似算法,如平面图或单位磁盘图.
3. 找到图的分数着色的算法.

最后一个对我来说特别重要.

到目前为止我发现的是此页面上的列表,但没有一个具有上述任何算法.此外,最好的一个是Joe Culberson的图形着色代码并且是在90年代后期实现的,所以在没有文档化API的情况下已经过时了(不是这对于这个问题的重要性,但我认为我'提到它).

还有的考拉图着色库有什么我要找的精神,但如果你看看他们的源代码,它并没有在承诺交付,只是还没有.它似乎处于发展的早期阶段.

此stackoverflow问题中提到了其他常规图库.他们包括:

1. 的Graphviz
2. 提升图库
3. 柠檬
4. IGRAPH
5. OGDF

我应该注意到我使用Boost Graph Library做了很多事情.实际上,它提供了一个天真的顶点着色实现.Joe Culberson的代码(如上所述)做得更多.

以下是图形着色代码的列表,我发现(并在大多数情况下进行了测试),但它们在上述三种算法类别方面仍然大部分都不足.

1. GraphCol - 文档不是英文,叹气.
2. 平面性 - 包含着色算法,可确保平面图的5色或更好.
3. 图形着色 - 似乎是Joe Culberson已经实现的少量算法的重新实现(上图).

我必须制作一个程序,它将说明图形是否可着色 - 基本上我必须检查色度指数是d还是d + 1,其中d是所有顶点的最大度数(vizing定理).我知道这个问题是NP完全的,基本上它必须是强制性的.我有一个想法,但不知道它是否正确 -

1)找到具有deg(v)= d的顶点并用v与d区分颜色的所有边缘着色.

2)对于与v相邻的顶点入射的所有边,从d组颜色中应用一些颜色

3)重复2)"发现"边缘

如果所有边缘都用d颜色着色,则色度指数为d,并且我有一个图G的着色.

如果某些边缘不能用d颜色的颜色着色,那么用d + 1-st颜色为颜色设置颜色,用d + 1颜色设置颜色剩余边缘颜色 - 这是问题 - 使用这个方案,如果我宣称色度指数为d + 1,是否有可能与其他一些着色色度指数为d？(对于每个要着色的边缘,我选择一种可以使用的颜色)

此外,哪个图形表示最适合此问题？在输入文件中,图形写在邻接矩阵中.我知道它可以通过递归来解决,但我不知道如何.我坚持一些太复杂的想法:S(一些提示或伪代码将被赞赏).

编辑:

只是想到了我的想法,我觉得它应该没问题(纯粹的暴力).我还没有尝试实现这个.如果你看错了,请评论.再说一遍 - 算法应检查图形是否可用d或d + 1颜色进行边缘着色,其中d是给定简单图形中所有顶点的最大度数,并找到一个着色...

colorEdge(edge, color, extra) {
    if (edge colored) return;  //if already colored, return
    if (can be colored in color) color it; //if color can be applied, apply it
    else {
        //else, 'd+1'-st color neded, so color it with that color, continue finding 
        //coloring with d+1 colors
        extra = true; 
        color it in …

给定未加权无向图的邻接矩阵,是否有一种有效的方法(多项式算法)来扩展/增加任何给定的两个节点s和t之间的最短路径的长度？

例:

在下面的例子中,从顶点s = 1到顶点t = 5有5个不同的"最短路径",每个都有3个长度.我想删除最少数量的边缘,以便最短路径长度被强制为4或更多.(断开图表是可以的.)

邻接矩阵(扩展以纠正示例):

 0 1 0 0 0 1 1 1 0 1 0 
 1 0 1 1 0 0 0 0 0 0 0  
 0 1 0 0 1 0 0 0 0 0 1 
 0 1 0 0 1 1 0 0 0 0 0  
 0 0 1 1 0 1 0 0 0 0 0 
 1 0 0 1 1 0 0 0 1 0 0 
 1 0 0 0 0 0 …

我正在寻找一种算法(或任何其他方式)来确定给定的加权图是否在O(ElogV)中具有唯一的MST(最小生成树)？

我对权重没有任何了解(例如权重(e1)!=权重(e2)),如果该图只有一个唯一的MST,算法只返回True,否则返回False.

我开始使用Kruskal的算法,并检查是否find-set(u)== find-set(v)所以在MST中有一个圆圈,但这种方式并没有涵盖我想的所有场景:(

非常感谢!托梅尔.

我有一个庞大的路由器网络,所有路由器都在社区网络中互连.我试图通过不同的方式分析这个网络并获得有用的见解以及通过分析图表(使用gephi)来改进它的方法.所以我遇到了这个称为"模块化"的措施,其定义为:

衡量网络划分为模块(也称为组,集群或社区)的强度.具有高模块性的网络在模块内的节点之间具有密集连接,但是在不同模块中的节点之间具有稀疏连接.

我的问题是,通过使用"模块化"度量,我可以从网络中学到什么？例如,当我在gephi中使用它时,每个网段都会对网络进行着色,但它有什么用呢？

我想创建一个图表,显示来自邻接矩阵的节点之间的连接,如下所示.

gplot似乎是最好的工具.但是,为了使用它,我需要传递每个节点的坐标.问题是我不知道坐标应该在哪里,我希望这个函数能够为我找出一个好的布局.

例如,这是我的输出使用以下任意坐标:

 A = [1 1 0 0 1 0;
      1 0 1 0 1 0;
      0 1 0 1 0 0;
      0 0 1 0 1 1;
      1 1 0 1 0 0;
      0 0 0 1 0 0];

 crd = [0 1;
        1 1;
        2 1;
        0 2;
        1 2;
        2 2];

 gplot (A, crd, "o-");

这很难读,但是如果我稍微使用坐标并将它们更改为以下内容就会变得更具可读性.

   crd = [0.5 0;
         0 1;
         0 2;
         1 2;
         1 1;
         1.5 2.5];

我不希望完美优化的坐标或任何东西,但我怎么能告诉MATLAB自动为我找出一组坐标看起来没问题使用某种算法,所以我可以绘制一些看起来像顶部图片的东西.

提前致谢.

我试图找到使用apache spark在大量数据上搜索不相交集(连接组件/ union-find)的算法.问题是数据量.甚至图顶点的Raw表示也不适合单机上的ram.边缘也不适合公羊.

源数据是hdfs上图形边缘的文本文件:"id1\t id2".

id作为字符串值存在,而不是int.

我发现天真的解决方案是:

1. 拿rdd of edges - > [id1:id2] [id3:id4] [id1:id3]
2. 按键分组边缘. - >[id1:[id2;id3]][id3:[id4]]
3. 为每个记录设置每组最小ID - > (flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. 从第3阶段逆转 [id2:id1] -> [id1:id2]
5. leftOuterJoin 第3阶段和第4阶段的rdds
6. 从第2阶段开始重复,而第3步的rdd大小不会改变

但这导致节点之间传输大量数据(改组)

有什么建议吗？

我使用Gephi和NetworkX计算了平均聚类系数.对于同一图表,NetworkX给出0.2399而Gephi给出0.644.

1. 它为什么不同？
2. NetworkX和Gephi如何计算平均聚类系数？
3. 在具体断开组件的情况下; NetworkX和Gephi如何计算系数？