GraphView and subclasses of Graph
Hi! Thanks for graph-tools, it looks like a fab project! I am toying around with a particular class of graphs for which I wrote a subclass of `graph_tools.Graph`. It should be great to be able to use `GraphView` for filtering (I'm implementing a divide-and-conquer algorithm and want to recur on subgraphs), but it seems that those will always behave as `Graph`, even if I instantiate them with an object of my subclass. Is there a better way to filter my graphs than writing a custom `GraphView` subclass for it? Cheers, Patrick
On 21.09.2016 10:28, Patrick Totzke wrote:
I am toying around with a particular class of graphs for which I wrote a subclass of `graph_tools.Graph`. It should be great to be able to use `GraphView` for filtering (I'm implementing a divide-and-conquer algorithm and want to recur on subgraphs), but it seems that those will always behave as `Graph`, even if I instantiate them with an object of my subclass.
Of course, GraphView is a subclass of Graph, not of your subclass.
Is there a better way to filter my graphs than writing a custom `GraphView` subclass for it?
You can just use the set_edge/vertex_filter() methods of Graph. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Hi Tiago, thanks for your prompt reply. Quoting Tiago de Paula Peixoto (2016-09-21 10:35:39)
On 21.09.2016 10:28, Patrick Totzke wrote:
I am toying around with a particular class of graphs for which I wrote a subclass of `graph_tools.Graph`. It should be great to be able to use `GraphView` for filtering (I'm implementing a divide-and-conquer algorithm and want to recur on subgraphs), but it seems that those will always behave as `Graph`, even if I instantiate them with an object of my subclass.
Of course, GraphView is a subclass of Graph, not of your subclass.
Sure I understand. I was hoping for some magic via mixins or the like to make this work anyway..
Is there a better way to filter my graphs than writing a custom `GraphView` subclass for it?
You can just use the set_edge/vertex_filter() methods of Graph.
Yes, but as far as I understand one cannot add multiple vertex-filters right? I mean in order to solve my problem recursively on subgraphs, I can of course set a filter and then recur. But then "setting a filter" would amount to amending an already existing one... Another related question: my algorithm could potentially parallelize the recursive calls dealing with subgraphs. If I use filters as you suggest to identify subgraphs, does the fact that concurrent recursive calls handle the same graph object with different filters cause any problems? Could you point me towards example (python) code that utilizes parallel threads? Or is this done only on a libboost level? Thanks again for your help and apologies for my rather vague noob questions. Best, Patrick BTW: I believe there is a typo in the docstring for `Graph.set_filters`: "Only the vertices and edges with value different than True are kept in the filtered graph" Shouldn't it say values different from `False`, as in `set_vertex_filter`?
On 21.09.2016 14:53, Patrick Totzke wrote:
Is there a better way to filter my graphs than writing a custom `GraphView` subclass for it?
You can just use the set_edge/vertex_filter() methods of Graph.et
Yes, but as far as I understand one cannot add multiple vertex-filters right? I mean in order to solve my problem recursively on subgraphs, I can of course set a filter and then recur. But then "setting a filter" would amount to amending an already existing one...
You can just keep several copies of the mask, and compose them by hand: old_mask = g.get_vertex_filter()[0] mask = old_mask.copy() for v in sub_graph_vertices: mask[v] = False g.set_vertex_filter(mask) # now g does no longer contains those vertices It is easy to do this recursively, and it amounts to what is actually done with GraphView, although it is less elegant.
Another related question: my algorithm could potentially parallelize the recursive calls dealing with subgraphs. If I use filters as you suggest to identify subgraphs, does the fact that concurrent recursive calls handle the same graph object with different filters cause any problems?
Yes, it would cause problems, since you would have only one graph instance, whereas with GraphView it would not. However, this is an entirely moot point, since you cannot truly parallelize things in (pure) Python. You would get nothing for it.
Could you point me towards example (python) code that utilizes parallel threads? Or is this done only on a libboost level?
It can't be done in Pure python, only if you drop to C/C++. You can read more here: https://wiki.python.org/moin/GlobalInterpreterLock
BTW: I believe there is a typo in the docstring for `Graph.set_filters`: "Only the vertices and edges with value different than True are kept in the filtered graph" Shouldn't it say values different from `False`, as in `set_vertex_filter`?
Yes, it is a typo. Thanks for catching it. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Quoting Tiago de Paula Peixoto (2016-09-21 17:45:32)
On 21.09.2016 14:53, Patrick Totzke wrote:
Is there a better way to filter my graphs than writing a custom `GraphView` subclass for it?
You can just use the set_edge/vertex_filter() methods of Graph.et
Yes, but as far as I understand one cannot add multiple vertex-filters right? I mean in order to solve my problem recursively on subgraphs, I can of course set a filter and then recur. But then "setting a filter" would amount to amending an already existing one...
You can just keep several copies of the mask, and compose them by hand:
old_mask = g.get_vertex_filter()[0] mask = old_mask.copy() for v in sub_graph_vertices: mask[v] = False g.set_vertex_filter(mask) # now g does no longer contains those vertices
It is easy to do this recursively, and it amounts to what is actually done with GraphView, although it is less elegant.
Cool, thanks for this and also for the detailed pointers re parallelisation! Best wishes, Patrick
participants (2)
-
Patrick Totzke -
Tiago de Paula Peixoto