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 -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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 .~' On Fri, Sep 16, 2016 at 1:57 PM, P-M <pmj27@cam.ac.uk> wrote:
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
-- View this message in context: 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- tp4026722.html Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com. _______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
On 16.09.2016 16:22, Alexandre Hannud Abdo wrote:
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_... 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 -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
Alexandre Hannud Abdo -
P-M -
Tiago de Paula Peixoto