标签: graph-theory

我想使用看起来很棒的GraphSharp库,但该项目没有文档.

具体来说,我对使用布局引擎感兴趣,对WPF控件不感兴趣.我只想计算给定图形和布局算法的布局(节点的位置).

有没有人有任何关于如何使用GraphSharp的建议,提示和链接.

我正在开发一个Journey Planner网站.目前在这种情况下很少有简单的事情,即现在网站只能规划公交线路,目前公交车的时间不可用.所以这意味着我们只有存储在数据库中的总线路由,因为总线时序不可用,所以旅行者的等待时间也不相关.可用的是单个公共汽车两站之间的时间和距离.

我认为使用无向加权图存储每个公交车站的时间和距离成本是每条公交车的出发点.然后我可以使用Dijkstra算法根据用户偏好计算用户根据时间或距离输入的两个位置之间的最短路径.如果公交车路线在停靠点相交,然后使用这些交叉路口以便旅行者更换公交车,我会发现是否需要通过简单的C#功能使用两辆或三辆公交车.但是每辆公交车都会有一张单独的图表.另一种方法(不确定这是否正确)方法是使用包含城市的每个公共汽车站的图表作为节点,然后使用这种技术找出两站之间的旅行方式.哪种方法正确？我应该使用A*算法代替Dijkstra算法吗？

设计的一些一般要点:我希望应用程序是可扩展的,以便我可以在需要时添加其他运输工具.此外,如果可能的话,也可以在以后添加公交车时间而不对网站进行重大更改.我在这里见过很多专家,他们参与了许多复杂的交通项目.因此,请以最具扩展性,模块化和可扩展的方式帮助我实现此功能的最佳方式.

这是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 …

我正在寻找Java中Dijkstra(或任何其他源到目的地最短路径算法)的双向搜索(也称为"中间相遇"算法)的实现.

由于双向搜索处理比它看起来更棘手(图算法,第26页),我想在重新发明轮子之前考虑现有的实现!

PS:我说的是双向搜索,不要与双向图混淆)

以下是一个棘手的图表示例:

这是一个有监督的学习问题.

我有一个有向无环图(DAG).每个边都有一个特征向量X,每个节点(顶点)有一个标签0或1.任务是找到一个成本函数w(X),这样任何一对节点之间的最短路径具有最高的比率1s到0s(最小分类错误).

解决方案必须很好地概括.我尝试了逻辑回归,并且学习的逻辑函数很好地预测了给出传入边缘特征的节点的标签.但是,该方法不考虑图形的拓扑,因此整个图形中的解决方案不是最优的.换句话说,考虑到上面的问题设置,逻辑函数不是一个好的权重函数.

虽然我的问题设置不是典型的二进制分类问题设置,但这里有一个很好的介绍:http: //en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work

以下是一些更多细节:

1. 每个特征向量X是实数的d维列表.
2. 每条边都有一个特征向量.也就是说,给定边缘集合E = {e1,e2,... en}和特征向量集合F = {X1,X2 ... Xn},则边缘ei与向量Xi相关联.
3. 有可能得出一个函数f(X),因此f(Xi)给出了边ei指向标有1的节点的可能性.这种函数的一个例子是我上面提到的,通过逻辑找到的回归.但是,正如我上面提到的,这种功能是非最佳的.

问题是:给定图形,起始节点和结束节点,如何学习最优成本函数w(X),以便节点1s与0s的比率最大化(最小分类误差)？

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

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

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

非常感谢!托梅尔.

我正在寻找一种算法来解决以下问题.我有一组给定集合(ah)的子集(1-n).我想找到最小的子集合,这些子集将允许我通过组合构造所有给定的子集.此集合可以包含1-n中不存在的子集.

  a b c d e f g h
1 1
2 1   1
3   1     1   1
4 1       1
5   1         1
6 1     1   1   1
7 1       1 1   1
8 1   1       1
9 1         1   1

下面是两个可能的集合,其中最小的集合包含七个子集.我用x表示了新的子集.

1 1
x   1
x     1
x       1
x         1
x           1
x             1
x               1

1 1
x   1         
x     1
x       1        
x         1    
x           1   1
x             1

我相信这一定是一个已知问题,但我对算法并不熟悉.非常感谢任何帮助,以及更好的主题标题的建议.

谢谢!

更新

图形着色让我走了很长的路,谢谢.但是,在我的情况下,允许子集重叠.例如:

  a b …

我正在使用networkx找到二分图的最大基数匹配.

匹配的边缘对于特定图形不是唯一的.

有没有办法找到所有最大匹配？

对于以下示例,下面的所有边可以是最大匹配:

{1: 2, 2: 1}或{1: 3, 3: 1}或{1: 4, 4: 1}

import networkx as nx
import matplotlib.pyplot as plt

G = nx.MultiDiGraph()
edges = [(1,3), (1,4), (1,2)]

nx.is_bipartite(G)
True

nx.draw(G, with_labels=True)
plt.show()

不幸,

nx.bipartite.maximum_matching(G)

只返回

{1: 2, 2: 1}

有没有办法可以获得其他组合？