Find minimum value of edge property for all edges connected to a given node

I have a network where each of my edges is labelled with a date. I want to
now also label my vertices so that each vertex has a date assigned to it
corresponding to the minimum date of all edges incident and emanating from
it. Is there an inbuilt function to find this which would be faster than me
looping over all vertices and then all edges for each vertex manually? My
current code idea is:

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

Ni! Hello Phillip,

Don't think there's a boxed method for this task, but you can easily
improve your algorithm, though that is no longer a question for graph-tool.

Two possible ways to improve it:

* you could use the fact that the min() function in Python takes an
iterable as argument, and pass it something like the generator below:

# chain must be imported from itertools
for v in g.vertices():
    g.vp.year[v] = min( g.ep.year[e] for e in chain(v.out_edges(),
v.in_edges()) )

* you could iterate only once over g.edges() and then, update the g.vp.year
of source and target for each edge.

I would go with something like this:

# this assumes g.vp.year was initlized to a large value by passing 'val' to
new_vertex_property()
for e in g.edges():
    for v in (e.source(), e.target()):
        if g.vp.year[v] > g.ep.year[e]:
            g.vp.year[v] = g.ep.year[e]

Yet again, this has little to do with graph tool, you might prefer to look
for advice in general programming.

Cheers,

ale
.~'

attachment.html (3.25 KB)

Don't think there's a boxed method for this task, [...]

In this particular case, in fact there is:

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

Here are the docs:

    https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.incident_edges_op

Some small comments to your tips:

Two possible ways to improve it:

* you could use the fact that the min() function in Python takes an iterable
as argument, and pass it something like the generator below:

# chain must be imported from itertools
for v in g.vertices():
    g.vp.year[v] = min( g.ep.year[e] for e in chain(v.out_edges(),
v.in_edges()) )

I think it would be better to use v.all_edges() instead of chain(), but
chain() is a good general tip to have in mind.

* you could iterate only once over g.edges() and then, update the g.vp.year
of source and target for each edge.

I would go with something like this:

# this assumes g.vp.year was initlized to a large value by passing 'val' to
new_vertex_property()
for e in g.edges():
    for v in (e.source(), e.target()):
        if g.vp.year[v] > g.ep.year[e]:
            g.vp.year[v] = g.ep.year[e]

Definitely the most elegant. The only reason why "incident_edges_op()"
is not implemented like this in C++ is because doing it like your first
option can be parallelized. But this is a moot point in Python.

Best,
Tiago