Finding all edges within a certain distance in a graph containing loops in Java

Finding all edges within a certain distance in a graph containing loops in Java

I have a graph of Node objects connected by Edge objects that needs to be explored in the following way:

I am given a starting Edge source and need to find all other Edge objects so that the sum of lengths of passed edges along the path is no longer than MAX_RANGE as well as perform some operation at each Edge that meets the condition.

My solution to this problem is to recursively branch out, keeping track of travelled distance as I go (Edge#getEdgeConnections() returns an ArrayList containing all Edge objects that connect to the Edge it's called upon) :

private final ArrayList occupiedEdges = new ArrayList<>();    private void doStuffWithinRangeOf(Edge source) {      doStuffAtEdge(source);      for (Edge connection : source.getEdgeConnections()) {          doStuffAtBranch(connection, source, 0);      }  }    private void doStuffAtBranch(Edge edge, Edge source, double distance) {      double newDistance = distance + edge.getLength();      doStuffAtEdge(edge);      for (Edge connection : edge.getEdgeConnections()) {          if (!connection.equals(source)                   && !isOccupied(connection)                   && (newDistance < MAX_AP_RANGE)) {              doStuffAtBranch(connection, edge, newDistance);          }      }  }    private void duStuffAtEdge(Edge edge) {      occupiedEdges.add(edge);      ... // Some amount of work that mustn't be done more than once per Edge  }    private boolean isOccupied(Edge edge) {      return occupiedEdges.contains(edge);  }  

Now, this should work fine, except for one thing - the graph contains several cases of loops.

As such, if the recursive algorithm starts with the longer path around the loop, some edges that are within the specified range when choosing the shorter path may be missed, as shown below

  ----------- C ---- D - E    // The algorithm explores AB, BC, CD and makes them occupied    |           |    B           |               // DE is too far along this path, and isn't occupied    |           |    ------------A               // When the algorithm explores along AC, it finds that CD                                 // is already occupied and stops                                // even though DE is really within range  

Now, the solution I thought of was to do a different search pattern, where I would have a list (or map) of "frontier" edges, and explore them in order of increasing distance (adding new edges to this frontier every time an edge was explored).

There may be a large amount of edges involved, so I'd rather not loop through the whole list every time to find the one the shortest distance away from the source.

Is there some type of collection that automatically keeps an order in this fashion and is efficient in adding/removing elements?

Is SortedMap what I'm looking for? How would I use it in this case?

Edit: Thanks to all responders. I ended up using a PriorityQueue with a wrapper class (see my answer for details and code).

Answer by Mackiavelli for Finding all edges within a certain distance in a graph containing loops in Java

You can use a modification of either BFS or DFS, where you also add an extra rule for the MAX_LENGTH of the path (besides checking whether you have visited all of the neighbor nodes).

I would suggest that you went for DFS as it is a bit close to what you are doing at the moment. You can also easily "put in" the doSomethingToEdge in either method

Answer by H W for Finding all edges within a certain distance in a graph containing loops in Java

Rather than using some other datastructure, i would suggest adapting your algorithm:

You have implemented some sort of depth-first-search to go through your graph. If you use some kind of breadth-first-search instead, you can just stop when you reach the specified range and have visited every edge within range exactly once (by using the isOccupied logic you already implemented).

Answer by Karthik for Finding all edges within a certain distance in a graph containing loops in Java

NOTE: After writing the answer, I realised that you are talking in terms of edges, but same example and same theory I mentioned in terms of Nodes will also work with edges.

If you do simply BFS, it's not going to work, because you will mark a node as visited prematurely. Consider this example

Your max_range is 20 & d(x,y) represents edge weight between x and y

         A->(10)E->D(10)->(5)F // d(A,E)=d(E,D)=10 & d(D,F)=5             A->(5)B->(5)C->(5)D->(5)F //d(A,B)=d(B,C)=d(C,D)=d(D,F)=5    

In a situation like this, You would reach D in the path (A-> E-> D) first (since it is closer to A in this path) and you would mark D as visited. Which is actually wrong, because marking D as visited stops you from visiting F, which you could have done, if your path was (A->B->C->D->F).

So to avoid repetitions and also solve this problem, with each node you are adding you should also add List of nodes that you have seen in the current path. This way you can still visit F, because when you reach D in the path (A->B->C->D) you will see it as unvisited because it did not occur in your path.

Coming to implementation, I will give you a rough idea:

create a wrapper class

   NodeWrapper{        Node node;        List Parents;        int pathSum;     }  

Your BFS should look like this :

 {        Queue queue = new LinkedList<>();     Queue.add(new NodeWrapper(sourceNode,new ArrayList));       while(!queue.isEmpty()){           NodeWrapper temp = queue.poll();           Node presentNode = temp.getNode();           List parentsList = temp.getParentsList();           for all neighbours of presentNode                if neighbour is not in presentNode && (pathSum +currentEdgeWeight )< max && your conditions               add currentNode to parent list               queue.add(new NodeWrapper(neighbour,parentList,(pathSum +currentEdgeWeight)));       }     }  

Answer by tucuxi for Finding all edges within a certain distance in a graph containing loops in Java

The algorithm that you are looking for is a modified Dijkstra, where instead of search for the shortest path from A to B, you are searching for all shortest-paths shorter than X. Dijkstra guarantees that you will visit each node in increasing order of distance from the start, and through the shortest path from the start. Additionally, if there are no negative-length edges, then parenthood will never change -- and you are guaranteed that the inner if will be executed once and only once with each edge along a minimal path to a node. However, since the set of "nodes closer than X" is only known at the end (= those with final distance < max), you could wait until the algorithm finishes to doStuffAtBranch only for branches that actually lead somewhere interesting.

The pseudocode would go as follows:

final HashMap distances = new HashMap<>();  HashMap parents = new HashMap<>();  distances.put(start, 0);  // start is at distance 0 from start    PriorityQueue q = new PriorityQueue(allVertices.size(),       new Comparator() {          public int compare(Vertex a, Vertex b) {              return distances.get(a) - distances.get(b);          }  });    for (Vertex v : allVertices) {      q.add(v, distances.contains(v) ?           distances.get(v) : Double.POSITIVE_INFINITY);  }    while ( ! q.isEmpty()) {      Vertex u = q.poll(); // extract closest      double current = distances.get(u);      if (current > max) {          // all nodes that are reachable in < max have been found          break;      }      for (Edge e : u.getEdges()) {          Vertex v = u.getNeighbor(e);          double alt = current + e.length();          if (alt < distances.get(v)) {              q.remove(v);       // remove before updating distance              distances.put(v, alt);              parents.put(v, u); // v will now be reached via u              q.add(v);          // re-add with updated distance              // if there are no negative-weight edges, e will never be re-visited          }      }  }  

Answer by Svj0hn for Finding all edges within a certain distance in a graph containing loops in Java

After a few iterations, I ended up using a solution similar to that of user tucuxi. I used a PriorityQueue with a wrapper class implementing the Comparable interface. As I realised I needed to explore the graph in several different cases and do different things, I made a general use method in the Edge class that returns all other edges within a provided range.

Code:

public ArrayList uniqueEdgesWithinRange(double range) {      ArrayList edgeList = new ArrayList<>();      PriorityQueue frontier = new PriorityQueue<>();      frontier.add(new ComparableEdge(0.0, this));        while(!frontier.isEmpty()) {          ComparableEdge cEdge = frontier.poll();            edgeList.add(cEdge.edge);            if (cEdge.distance < range) {              for (Edge connection : cEdge.edge.getEdgeConnections()) {                  if (!edgeList.contains(connection)) {                      frontier.add(new ComparableEdge(cEdge.distance + connection.getLength(), connection));                  }              }          }      }        return edgeList;  }    private class ComparableEdge implements Comparable {      private double distance; // Distance from closest point on source to furthest point on edge      private Edge edge;        private ComparableEdge(double distance, Edge edge) {          this.distance = distance;          this.edge = edge;      }        @Override      public int compareTo(ComparableEdge another) {          return Double.compare(distance, another.distance);      }  }  

The amount of indentation in the method makes me feel abit iffy, so I'll probably refactor it abit, but otherwise it should be functionally complete.

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72