[graph-tool] shortest_distance / concurrency / graph view

François francois.kawala at gmail.com
Mon Oct 10 17:28:37 CEST 2016


Hello,

I suspect the copy_property function not to be thread safe. Remember that
the issue I observe occurs when I re-use the predecessor map returned by
shortest_distance. The copy_property is then called from
topology/__init__.py:1441 and the parameter full is None.

Here how I think it might fail with two concurrent shortest_distance calls.

Timeline
  |
  *time t=0 : Worker #1 executes the following statements from
(graph_tool/__init__.py:2216)*
  | g.set_directed(True)
  | g.clear_filters()
 * time t=1 : Worker #2 executes the following statements from
(graph_tool/__init__.py:2207)*
  | is_directed = g.is_directed() *# True (as a result of worker #1)*
  | efilt = g.get_edge_filter()   *# Empty **(as a result of worker #1)*
  | vfilt = g.get_vertex_filter() *# Empty **(as** a result of worker #1)*
  *time t=2 : **Worker #1 continues until **(graph_tool/__init__.py:2248)
and set back the graph g in its original (ie. t<0) state.*
*  | *g.set_directed(is_directed)
  | g.set_edge_filter(efilt[0], efilt[1])
  | g.set_vertex_filter(vfilt[0], vfilt[1])
  *time t=3 : Worker #2 **continues until (graph_tool/__init__.py:2248) and
set back in its incorrect **(ie. t=1) **state.*

Is there something I miss ?

Bests,
François.


On Wed, Oct 5, 2016 at 11:07 PM, Tiago Peixoto [via Main discussion list
for the graph-tool project] <ml-node+s982480n4026744h21 at n3.nabble.com>
wrote:

> On 04.10.2016 17:55, François Kawala wrote:
>
> > Hello,
> >
> > I have a rather fuzzy question about the topology.shortest_distance
> > function. I'll try to explain my problem as clearly as I can. If I fail
> to
> > be clear enough, don't waste your time, just let me know.
> >
> > I have a pool of workers using one single graph view instance, each work
> > calls a function f described below. The graph view has an edge filter.
> >
> >     def f(g, origin, targets_ids, weights):
> >         d, p = topology.shortest_distance(g, source=origin,
> >     target=targets_ids, weights=weights, pred_map=True)
> >         i = score(d)
> >         path = topology.shortest_path(g, source=origin,
> >     target=targets_ids[i], pred_map=p)
> >
> >         return path
> >
> >
> > Once in a while, the path from function f is not consistant with the
> graph
> > view (it goes through disabled edges).
> >
> > I tried to reproduce the error in a single thread environment. The exact
> > same inputs do not fail as observed previously (ie. with multiple
> workers).
> >
> > It seems highly unlikely, but would it be possible for the predecessor
> map
> > "p" to be overwritten by the actions of an another worker in the pool ?
> I'm
> > asking because I ran out of ideas to explain this problem, although it
> > sounds dumb.
> I don't see how that would happen, but without a complete (and minimal)
> working example, it is not possible to say much.
>
> Best,
> Tiago
>
>
> --
> Tiago de Paula Peixoto <[hidden email]
> <http:///user/SendEmail.jtp?type=node&node=4026744&i=0>>
>
>
> _______________________________________________
> graph-tool mailing list
> [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026744&i=1>
> https://lists.skewed.de/mailman/listinfo/graph-tool
>
> *signature.asc* (817 bytes) Download Attachment
> <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026744/0/signature.asc>
> --
> Tiago de Paula Peixoto <tiago at skewed.de>
>
>
> ------------------------------
> If you reply to this email, your message will be added to the discussion
> below:
> http://main-discussion-list-for-the-graph-tool-project.
> 982480.n3.nabble.com/shortest-distance-concurrency-graph-
> view-tp4026743p4026744.html
> To start a new topic under Main discussion list for the graph-tool
> project, email ml-node+s982480n2141189h16 at n3.nabble.com
> To unsubscribe from Main discussion list for the graph-tool project, click
> here
> <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=2141189&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXwyMTQxMTg5fDIxMTQ0MDk4Nzk=>
> .
> NAML
> <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>



-- 
François Kawala




--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/shortest-distance-concurrency-graph-view-tp4026743p4026752.html
Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20161010/acb74424/attachment.htm>


More information about the graph-tool mailing list