How to filter the result of KNeighborhoodFilter?

Question

I have a UndirectedSparseGraph g in which I have stored two kind of Node, namely User and Thread that both extend Node. I would like, for a User u, to retrieve its 2-dist neighborhood, i.e. other users that are linked with u because they have an edge to the threads belonging to u's 1-dist neighborhood. I know that KNeighborhoodFilter is the way to retrieve nodes "in radius" k from the caller node... this means, in my case, that both threads at 1 hop and users at 2 hops will be returned, and thus I have to filter the resulting collection. This is what I have so far:

// filter users in 2-dist nei
Predicate<Node> onlyUsers = new Predicate<Node>() {
    @Override
    public boolean apply(Node node) {
        return node.getName().startsWith("u");
    }
};
// find neighbors of nodes with degree i
Filter<Node, Edge> filter = new KNeighborhoodFilter<Node, Edge>(u, 2, KNeighborhoodFilter.EdgeType.IN_OUT);
// retrieve the nodes - but here we have both types of nodes
Collection<Node> twoDistNei = filter.transform(g).getVertices();
// filter the collection to retain only threads
Collection<Node> twoDistUsers = Collections2.filter(twoDistNei, onlyUsers);

Am I on the right track with this approach? or should I follow a different pattern to accomplish my task, which is to retrieve users at distance two from a selected user?

Best regards, Simone

Answer 1

What you're doing will work, except that you need to remove the original 'root' node as well.

Fundamentally, you have three choices: 1. Do what you're doing now. 2. Write your own code to collect the neighbors of u's neighbors in a set. If this is a bipartite graph, then you only have to remove the root and you're done. This is probably more space efficient, because the set you're building is never bigger than it has to be. 3. If this is a bipartite graph, use a hypergraph instead, where the nodes are users and the hyperedges are threads. Then you just ask the hypergraph for the nodes' neighbors.