Efficient way to have unique edges (with given vertices and type)
Hi, I would like to know if there is a computationally efficient way of creating edges only if an edge with the same extremities and the same type (= a given edge property, in the sense of graph-tool edge properties) does not exist already. Of course I can use the following algorithm: before creating edge (v1,v2) of type t1: take all edges out-going from v1: check how many of them have v2 as target, among them: check whether one of them has type t1 if yes do not create a new edge and return this one if not, create a new edge As this seems to be a bit slow (I have to do many such edge creations) I was wondering if there is a more efficient « create-only-if-doesnt-exist-already » method, of maybe simply a query method including the type (a single method for checking if there exists an edge of a given type between two given vertices). Thanks in advance Yannis -- ------------------------------------------------------- Yannis Haralambous Professor Institut Mines-Télécom, Télécom Bretagne Computer Science Department UMR CNRS 6285 Lab-STICC Technopôle Brest Iroise CS 83818, 29238 Brest Cedex 3, France Email: yannis.haralambous@telecom-bretagne.eu Internet: http://perso.telecom-bretagne.eu/yannisharalambous/ ICBM address: 48°21'31.57"N 4°34'16.76"W Twitter: y_haralambous ------------------------------------------------------- ...the ball I threw while playing in the park has not yet reached the ground (Dylan Thomas) Es gab eine Zeit, wo ich nur ungern über Schubert sprechen, nur Nächtens den Bäumen und Sternen von ihm vorerzählen mögen. (Robert Schumann)
On 14.10.2015 13:59, Yannis Haralambous wrote:
Hi,
I would like to know if there is a computationally efficient way of creating edges only if an edge with the same extremities and the same type (= a given edge property, in the sense of graph-tool edge properties) does not exist already.
Of course I can use the following algorithm:
before creating edge (v1,v2) of type t1: take all edges out-going from v1: check how many of them have v2 as target, among them: check whether one of them has type t1 if yes do not create a new edge and return this one if not, create a new edge
As this seems to be a bit slow (I have to do many such edge creations) I was wondering if there is a more efficient « create-only-if-doesnt-exist-already » method, of maybe simply a query method including the type (a single method for checking if there exists an edge of a given type between two given vertices).
It is worthwhile to look at the documentation for questions like this. What you are looking for is the Graph.edge() function: https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.edg... If you pass "all_edges=True" this will give you a list of all the existing parallel edges incident on two nodes. You can then iterate through them and check if one of them has the correct property value. If not, you create a new edge. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
Tiago de Paula Peixoto -
Yannis Haralambous