标签: graph-theory

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

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

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

我正在寻找一种算法来解决以下问题.我有一组给定集合(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}

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

我在网上发现了一些文章,提供了如何在SQL中对各种图形(特别是DAG)进行建模的示例,但考虑到它们的建模相对简单,它们看起来都非常复杂.

这样做有最佳/标准的方法吗？我目前的想法是这样的:

create table node (
  id int not null auto_increment,
  name TEXT
)

create table edge (
  from_node int not null,
  to_node int not null,  
  weight float
) 

那有什么不对吗？任何人都知道更好(更强大,也许)的方式？

图的传递闭包在此处定义:http://mathworld.wolfram.com/TransitiveClosure.html

在O(n ^ 3)中很容易实现,其中n是顶点的数量.我想知道它是否可以及时完成O(n ^ 2).

我知道这个问题有很多答案.但是,我发现它们中没有一个能够真正实现它.
有人认为一个循环(几乎)与强连通组件相同(s.在有向图中查找所有循环),因此可以使用为该目标设计的算法.
有人认为找到一个循环可以通过DFS完成并检查后端(s.文件依赖关系的boost图文档).

我现在想对是否可以通过DFS检测图中的所有循环并检查后沿有一些建议？
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf(在SO上找到)陈述了一种基于循环基础的方法.我个人而言,我觉得它不是很直观,所以我正在寻找一个不同的解决方案.

编辑:我最初的意见显然是错误的.S."Moron"的下一个回答.
初步意见:我的观点是它确实可以这样工作,因为DFS-VISIT(DFS的伪代码)刚刚进入尚未访问过的每个节点.从这个意义上讲,每个顶点都表现出一个潜在的循环开始.此外,由于DFS每次访问每个边缘,因此也会覆盖通向循环起点的每条边.因此,通过使用DFS和后沿检查,确实可以检测图中的所有周期.注意,如果存在具有不同数量的参与者节点的循环(例如,三角形,矩形等),则必须进行额外的工作以区分每个循环的实际"形状".

给定图G,为什么跟随贪心算法不能保证找到最大的独立 G 集:

Greedy(G):
S = {}
While G is not empty:
    Let v be a node with minimum degree in G
    S = union(S, {v})
    remove v and its neighbors from G
return S

我想知道有人能告诉我一个简单的图表示例,这个算法失败了吗？

我试图在不使用get_edge_attributes()函数的情况下从图形中获取具有特定属性的边.我需要一种更灵活的方式.我可以得到节点属性,但因为我在python边缘是新的似乎很难

G = nx.read_graphml("test.graphml")

for n in G:
  print "%s\t%s" %(n, G.node[n].get(attr))

for (s,d) in G:       # and here is my problem
  print "%s->%s\t%s" %(s, d, G.edge[s][d].get(attr))

我想使用这个jgrapht接口类在我的图上包含边的权重或成本:

package org.jgrapht;

public interface WeightedGraph<V extends Object, E extends Object> extends Graph<V, E> {

    public static final double DEFAULT_EDGE_WEIGHT = 1.0;

    public void setEdgeWeight(E e, double d);
}

有人能帮我吗？谢谢.

我正在尝试生成具有给定数量节点的所有有向图，直至图同构，以便我可以将它们输入到另一个 Python 程序中。这是一个使用 NetworkX 的简单参考实现，我想加快速度：

from itertools import combinations, product
import networkx as nx

def generate_digraphs(n):
  graphs_so_far = list()
  nodes = list(range(n))
  possible_edges = [(i, j) for i, j in product(nodes, nodes) if i != j]
  for edge_mask in product([True, False], repeat=len(possible_edges)):
    edges = [edge for include, edge in zip(edge_mask, possible_edges) if include]
    g = nx.DiGraph()
    g.add_nodes_from(nodes)
    g.add_edges_from(edges)
    if not any(nx.is_isomorphic(g_before, g) for g_before in graphs_so_far):
      graphs_so_far.append(g)
  return graphs_so_far

assert len(generate_digraphs(1)) == 1
assert len(generate_digraphs(2)) == 3
assert …