查找连接到给定节点的所有边的边 属性 的最小值

Question

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

我目前的代码思路是：

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

Answer 1

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

不过，您可以通过对整个数据进行一次调用而不是多次调用来优化对 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 and out_edges 两个 returns 列表，您可以轻松地与 + 运算符合并。

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

Answer 2

本次讨论（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 ) contains some useful suggestions for this topic too. It also highlights that there is actually an inbuilt method in graph-tool for finding the lowest value across all outgoing, say, edges (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)

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