java - Fast way of determining whether two nodes in a JUNG graph are connected by more than one path? -

given 2 nodes a , b directed jung graph, want determine whether there more 1 path a b (not necessarely shortest path).

i can think of 2 approaches only, both time-consuming.

1. retrieve paths connecting 2 nodes (question finding paths in jung?) , check if there more one.

2. retrieve shortest path using class dijkstrashortestpath, break path , search shortest path again. if there still one, means there multiple paths. note requires clone graph, since not want alter original graph.

how can smarter (i.e. faster)?

i found solution myself.

my problem has additional constraint want check whether there more 1 path only 2 nodes directly connected , edge. means computing shortest path single edge path.

so, question can reformulated as:

is there path connecting 2 nodes of edge, aside edge itself?

the solution use weighted shortest path. if assign high weight our edge of interest, , weight 1 others, if minimal distance lower our high weight, answer yes, otherwise no.

here code:

public static boolean aretheremultiplepaths(final edge edge, directedgraph<entity, edge> graph) {         transformer<edge, integer> transformer = new transformer<edge, integer>() {             public integer transform(edge otheredge) {                 if (otheredge.equals(edge))                     return integer.max_value;                 else                     return 1;             }         };          dijkstrashortestpath<entity, edge> algorithm = new dijkstrashortestpath<entity, edge>(graph, transformer);         double distance = (double) algorithm.getdistance(edge.getstartnode(), edge.getendnode());          return distance < integer.max_value;      }