javagraphjung2

K farthest points from vertex in graph edu.uci.ics.jung

I want to find K farthest points from a given vertex in a jung implementation of directed graph.

I assume that BFSDistanceLabeler does the job. However, it doesn't provide api for returning K farthest points, so I'll have to do it manually by traversing all vertices in graph and calling getDistance method. Or is there a better way?

But there is a bigger challenge for me. Despite the fact the graph is directed, I want to treat it as undirected for the distance labeler. Is it possible to somehow switch fast from from directed graph to its undirected version?

Why do I need to treat graph as undirected?

I analyze a very large network (milions of vertices) in consequent steps. In every step a small part of network (thousands of vertices) is loaded into a graph and analysed. This analysis requires directed graph and provides result for a one specific vertex which has to be located in the center of loaded area.

When I move from step A to step B, I could delete the whole previous graph and create a new one. Nevertheless, this would be very time consuming. Because I know my new vertex of interest is near to the previous one, a big part of graph can be reused.

And that is why I need to remove K farthest vertices for the new main vertex and replace them with new vertices from surrounding of this vertex.

Lets take a look at bottom picture with graph and lets say that vertex 1 is our vertex of interest. Since the graph is directed vertex number 6 is farthest. However, if graph was treated as undirected, then vertex number 4 would be the farthest and that is what i need.

enter image description here

Solution

  • There is not going to be an asymptotically faster way to find all the farthest vertices from a given input vertex than finding the distances to all vertices.

    You can get the farthest vertices more efficiently by calling getVerticesInOrderVisited(), and then traversing the list in reverse order starting from the 'tail': this list should be populated in increasing order of distance from the root (set), so just get vertices from the list until the distance for each one starts decreasing.

    (Note: this will not pick up the vertices that may be completely disconnected from the root vertex, which you may consider to be the "farthest"; getUnvisitedVertices() will do that.)

    To answer your second question*: essentially what you want to do is to treat the directed edges as undirected. JUNG allows you to do this; instead of using getSuccessors()/getPredecessors(), you can call getNeighbors(), for instance.

    As you've inferred, BFSDistanceLabeler doesn't do this; it wants to respect the edge direction if it exists, so it uses getSuccessors(). So here are some options:

    1. Use jung.algorithms.transformation.DirectionTransformer.toUndirected(). This is very easy, but involves creating a bunch of new (undirected) edges

    2. Create a subclass of BFSDistanceLabeler that overrides labelDistances(), and replaces getSuccessors() with getNeighbors(). This is pretty easy, if not very elegant.

    3. Create a GraphDecorator subclass that overrides getSuccessors() to call getNeighbors() on its delegate graph. Then create an instance of your subclass where your original graph is the delegate. This is the most elegant and general solution. (And at some point it may be useful for us to provide utilities that do this for you; please feel free to file an issue on the JUNG GitHub page: https://github.com/jrtom/jung/issues)

    Hope this helps.

    *For future reference, please split unrelated questions into separate StackOverflow questions; it makes them easier to answer and to find.