Tiago de Paula Peixoto wrote:
Am 20.08.21 um 20:51 schrieb oliver.baumann(a)uni-bayreuth.de:
Hi all,
I'm currently offloading construction of the uni-modal projection of a bipartite graph from Python to C++ (NB: I am not very familiar with C++ or BGL, _yet_). Thanks to the docs on writing such extensions, I know roughly where I'm heading.
This is the signature of the projection-function:
template <class Graph, class ProjectedGraph> void projection(const Graph &g, ProjectedGraph &pg)
Here, g is the bipartite graph, and pg is constructed in Python as: pg = Graph(GraphView(g, vfilt=lambda v: g.vp.type == 0)) This would remove every vertex from the graph, since g.vp.type == 0 will always return False.
This was a typo whilst drafting my message, it is of course `lambda v: g.vp.type[v] == 0`.
I also do not understand why do you construct a new Graph object, instead of working with the GraphView directly.
To my understanding, modifying the GraphView by adding edges to it would also reflect in the original, bipartite graph, which I don't want. Would an EdgePropertyMap only on the view with a binary "exists/missing" be the cleaner approach, you reckon?
I am thus passing in the graph containing only the vertices I wish to project onto, and add the edges between them in C++.
In Python, pg.num_edges() correctly returns zero. In C++, it returns the same number of edges as the base-graph it was constructed from, g.
How can I obtain the filtered view of pg in C++, which I expect to have no edges? Since you have not provided any code, I can only guess what is going on.
A typical pitfall is that the C++ function num_edges(g) will always return the number of edges in the _unfiltered_ graph, even if the graph is being filtered. This is due to the BGL semantics that requires the function to be computed in time O(1). But that does not mean that the graph is not being filtered... If you iterate over it, you will get what you expect.
This is exactly it, thanks for clarifying that iteration will be performed on the filtered set. The result is as expected, however with the full bipartite graph (|V| 32k, |E| 280k), I run out of memory on a 16GB machine. Slightly hijacking the topic, is there any room for improvement on the projection code: #include <graph_tool.hh> namespace gt = graph_tool; template <class Graph, class ProjectedGraph> void projection(const Graph &g, ProjectedGraph &pg) { // iterate the filtered nodes, type==0 for (const auto v : gt::vertices_range(pg)) { // iterate the neighbourhood of type == 1 for (const auto direct_neigh : gt::all_neighbors_range(v, g)) { // iterate this neighbourhood, again of type == 0 to determine edges between type-0-nodes for (const auto next_neigh : gt::all_neighbors_range(direct_neigh, g)) { if (v != nn) { boost::add_edge(v, next_neigh, pg); } } } } } This is the direct translation of what networkx.bipartite_projection [1] does.
Best, Tiago
Thanks a lot, Oliver [1] https://networkx.org/documentation/stable/_modules/networkx/algorithms/bipar...