2

我有一个网络，我的每个边缘都标有日期。我现在还想标记我的顶点，以便每个顶点都有一个分配给它的日期，对应于所有边缘事件的最小日期并从它发出。是否有一个内置函数可以找到它，它比我手动遍历所有顶点然后遍历每个顶点的所有边要快？换句话说：我正在寻找一个函数来找到给定边缘子集的给定边缘属性的最小值。

我目前的代码想法是：

lowest_year = 2016
for v in g.vertices():
    for e in v.in_edges():
        year = g.ep.year[e]
        lowest_year = min(year,lowest_year)
    for e in v.out_edges():
        year = g.ep.year[e]
        lowest_year = min(year,lowest_year)
    g.vp.year[v]=lowest_year
    lowest_year = 2016
4

2 回答 2

2

几乎没有任何解决方案不需要检查所有边缘以找到最小值。

但是，您可以通过对整个数据进行一次调用而不是多次调用来优化您的调用，min并且您也不再需要lowest_year：

from itertools import chain

for v in g.vertices():
    g.vp.year[v] = min(map(g.ep.year.__getitem__, chain(v.in_edges(), v.out_edges())))

方法in_edges和out_edges两者都返回列表，您可以轻松地与+运算符合并。

在更一般的情况下，您会itertools.chain在忘记要合并的类型时使用，但+在这种情况下会更好，因为我们知道这些项目是列表。

于 2016-09-16T12:18:13.900 回答
0

这个讨论（http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Find-minimum-value-of-edge-property-for-all-edges-connected -to-a-given-node-td4026722.html）也包含一些对这个主题有用的建议。它还强调了 graph-tool 实际上有一个内置方法可以在所有传出的边上找到最小值（https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.incident_edges_op ):

g.vp.year = incident_edges_op(g, "out", "min", g.ep.year)

这也需要对进入的边缘重复，然后必须找到两者之间的最小值。

于 2016-09-27T15:37:05.353 回答