标签: directed-graph

我有一个有向图，其中有两条有向路径。

我想要一种算法来确定两条路径之间的相似性。

这篇文章提到使用编辑距离来确定近似相似度。我还意识到汉明距离使用类似的度量。

我的问题是：

如何处理两条路径彼此平行的情况。也就是说，如果两条路径没有相似的节点，但仍将被视为“相似”，因为它们的路径在相同方向上行进且彼此非常接近。

谢谢

程序的输入是图中的边集.例如,考虑以下简单有向图:

a -> b -> c

该图的边集是

{ (b, c), (a, b) }

因此,将有向图作为一组边,如何确定有向图是否为树？如果它是树,那么树的根节点是什么？

首先,我在看你如何表示这个图,邻接列表/邻接矩阵/其他什么？如何利用您选择的表示来有效地回答上述问题？

编辑1:

有些人正在考虑使用DFS进行循环检测,但问题是从哪个节点启动DFS.由于它是有向图,我们无法从随机节点启动DFS,例如,如果我从顶点'c'开始DFS,它将不会继续进行,因为没有后边缘去任何其他节点.这里的后续问题应该是如何确定这棵树的根源.

上下文：我正在尝试运行另一位研究人员的代码 - 它描述了湾区道路网络的交通模型，该模型受地震危险的影响。我是 Python 的新手，因此非常感谢调试以下错误的一些帮助。

问题：当我尝试按照自述文件中的说明运行随文件提供的示例数据的代码时，出现以下错误。

DN0a226926:quick_traffic_model gitanjali$ python mahmodel_road_only.py
You are considering 2 ground-motion intensity maps.
You are considering 1743 different site locations.
You are considering 2 different damage maps (1 per ground-motion intensity map).
Traceback (most recent call last):
  File "mahmodel_road_only.py", line 288, in <module>
main()
  File "mahmodel_road_only.py", line 219, in main
  G = get_graph()
  File "mahmodel_road_only.py", line 157, in get_graph
  G = add_superdistrict_centroids(G)
  File "mahmodel_road_only.py", line 46, in add_superdistrict_centroids
  G.add_node(str(1000000 + i))
  File "/Library/Python/2.7/site-packages/networkx-2.0-py2.7.egg/networkx/classes/digraph.py", line …

为了构建有向网络图，Plotly 目前的做法似乎是使用注解。当边缘很少并且可以通过图形布局手动填充每个边缘时，此方法有效，例如，此示例。

但是，如果我要创建一个更复杂的图形，是否有一种好方法可以迭代地定义所有边的箭头坐标（我只能考虑构造一个字符串然后使用eval()，尽管我知道这是不好的做法）？（编辑：似乎这种连接迭代生成的dict()定义字符串的方法不起作用——仅适用于一个dict()定义）

编辑：添加代码片段以更好地说明场景（eval()注释掉该行以进行比较）：

import plotly.offline as py 
import plotly.graph_objs as go 

trace = go.Scatter( 
    x=[1, 2, 2, 1], 
    y=[3, 4, 3, 4], 
    mode='markers',
    marker=dict(size=[100, 100, 100, 100])
)

fig = go.Figure(
    data=[trace],
    layout=go.Layout(
        annotations = [
            dict(
                ax=1, ay=3, axref='x', ayref='y',
                x=2, y=4, xref='x', yref='y'
            ),
            # eval("dict(ax=2, ay=3, axref='x', ayref='y', x=1, y=4, xref='x', yref='y')")
        ]
    )
) 
py.plot(fig)

我也愿意尝试其他可视化包，如果在 Bokeh 或其他人下有这样做的好方法。

免责声明:作者是Erlang的新手.

我想在Erlang中实现某种最短路径算法.

Erlang中有一个图形数据结构的标准实现:http://www.erlang.org/doc/man/digraph.html

但是,我没有找到有关它使用的实际数据结构的任何信息.

大多数情况下我想知道:

• 获得顶点动作的所有'邻居'的最坏情况表现是什么？
• 从图中获取顶点的最坏情况是什么？

我正在为NetworkX中的有向图制作一些代码,并且遇到了一个块,这可能是我可疑的编程经验的结果.我想要做的是以下内容:

我有一个有向图G,顶部有两个"父节点",所有其他节点都从这些节点流出.在绘制这个网络的图形时,我想将每个节点作为"父1"的后代绘制一种颜色,而所有其他节点绘制另一种颜色.这意味着我需要一个名单Parent 1的继承者.

现在,我可以轻松地使用它们获得第一层:

descend= G.successors(parent1)

问题是这只给了我第一代接班人.最好是,我想要继承者的继承者,继承者的继承者的继承者等等.任意地,因为能够运行分析并制作图表而不必确切知道其中有多少代是非常有用的.

知道如何处理这个问题吗？

我发现了这篇SO帖子,建议在有向图中使用DFS进行循环检测由于回溯而更快.在这里我引用该链接:

深度优先搜索比广度优先搜索更有效,因为您可以更快地回溯.如果使用调用堆栈,它也更容易实现,但这依赖于没有溢出堆栈的最长路径.

此外,如果您的图表是定向的,那么您不仅要记住您是否访问过某个节点,还要记得您是如何到达该节点的.否则你可能会认为你找到了一个循环,但实际上你所拥有的是两个独立的路径A-> B,但这并不意味着存在路径B-> A. 通过深度优先搜索,您可以在下降时将节点标记为已访问,并在您回溯时将其标记为未标记.

为什么回溯必不可少？

有人可以用示例图解释给定A->B示例中的含义吗？

最后,我DFS在有向图中有一个循环检测代码,它不使用回溯但仍然检测循环O(E+V).

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited) {
    return true;
  }
  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()) {
    Vertex t = e.next().target;
    // quick test:
    if (t.isVisited) {
      return true;
    }
    // elaborate, recursive test:
    if (isCyclicDirected(t)) {
      return true;
    }
  }
  // none of our adjacent vertices flag as cyclic
  v.setVisited(false);
  return false;
}

我需要一个方法来查找有向无环图的根.我使用布尔邻接matix来表示java中的图.所以请建议.图也是未加权的图

当我使用NetworkD3绘制有向图时,边缘不是定向的,我该如何修复它？一个例子 :

library(networkD3)
data(MisLinks)
data(MisNodes)
forceNetwork(Links = MisLinks, Nodes = MisNodes,
         Source = "source", Target = "target",
         Value = "value", NodeID = "name",
         Group = "group", opacity = 0.8)

我希望结果被定向这是有向图的定义:

"有向图是图形,即连接在一起的一组对象(称为顶点或节点),其中所有边缘都从一个顶点指向另一个顶点.有向图有时被称为有向图或有向网络.

我希望边缘像箭一样,我怎么能在networkD3中做到这一点,我希望它很清楚.

谢谢.

假设图G是有向无环图,其中'n'没有顶点.如果我从图表中删除所有边缘并使其完全断开,这会是DAG吗？