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/bipartite/projection.html#projected_graph
_______________________________________________
graph-tool mailing list -- [email protected]
To unsubscribe send an email to [email protected]
