Java Code Review: Generate a subgraph

Question

I'm using JGraphT and I want to generate a subgraph, like this:

If there's a graph like {stuff -> a -> b -> stuff}, and you ask for the subgraph in direction of {a -> b}, you'll get {a -> b -> stuff}. (stuff = collection of nodes and edges, -> = an edge, a and b are nodes.)

My idea is as follows: if the start is A, and the sink is B, remove all edges from A that don't lead to B. Then, traverse the entire graph, and if no path exists from a given vertex to A, remove it.

Here is the full method. I would appreciate any comments reflecting any metric of code quality:

/**
 * subgraph that contains everything in the direction of sink
 * so if there's a graph like {stuff -> a -> b -> stuff}
 * and you ask for the subgraph in direction of {a -> b}
 * you'll get {a -> b -> stuff}
 * @param <V> vertex type
 * @param <E> edge type
 * @param g should be a dag
 * @param start a in the example above
 * @param sink b in the example above
 * @return a sub graph as specified above
 */
public static <V, E extends DefaultEdge> Graph<V, E> subgraphInDirection(UndirectedGraph<V, E> g, final V start, final V sink) {
 g = removeEdges(g, start, sink);
 return removeUnconnectedNodes(g, start);
}

private static <Vertex, Edge> UndirectedGraph<Vertex, Edge> removeEdges(UndirectedGraph<Vertex, Edge> g, Vertex start, Vertex sink) {
 final Set<Edge> outEdges = new HashSet<Edge>(g.edgesOf(start));
 boolean removedEdge;

 for (Edge e : outEdges) {
  if (! (g.getEdgeTarget(e).equals(sink) || g.getEdgeSource(e).equals(sink))) {
   removedEdge = g.removeEdge(e);
   assert removedEdge;
  }
 }
 return g;
}

private static <Vertex, Edge> Graph<Vertex, Edge> removeUnconnectedNodes(UndirectedGraph<Vertex, Edge> g, Vertex start) {
 ConnectivityInspector<Vertex, Edge> conn = new ConnectivityInspector<Vertex, Edge>(g);
 boolean removedVertex;

 final Set<Vertex> nodes = new HashSet<Vertex>(g.vertexSet());
 for (Vertex v : nodes) {
  if (! conn.pathExists(start, v)) {
   removedVertex = g.removeVertex(v);
   assert removedVertex;
  }
 }
 return g;
}

UPDATED to reflect initial comments.

Answer 1

First of all, your javadoc is wrong - either remove the attributes you haven't written anything in, or fill in the details.

Second, I would have broken it down to 2 separate methods, one for handling the edges, and the other for handling the vertices, which will make the code easier to understand and tidier.

Another small thing, the name removedE is a bit ugly (IMHO), and I'd use something longer than just E, like Edges.

Other than that, nothing else pops to mind, and the code looks good to me.

Regarding the ConcurrentModificationException: I'm not familiar with the library, and so don't know off the top of my head if that's the expected result, but usually removing elements during iteration causes problems, unless there's a special method for removing items during iteration to update the Iterator (for example, Iterator.remove).

Edit: After the changes you've made, the code is easier to understand. This might just be me, but I'd extract a method for the long conditional in the first method to something like isVertexConnectedToEdge().

Answer 2

That should have worked:

Set<V> nodes = new HashSet<V>(g.vertexSet());
for (V v : nodes) {
  if (! conn.pathExists(start, v)) {
    g.removeVertex(v);
  }
}

That copies the nodes to a new collection and it should eliminate the concurrent modification issues.