Add edges of the path to list on Depth first Search Java

Im trying to implement depth first search algorithm on a directed graph. The graph exists of Vertices (V Vertex), each Vertex has a set of edges (E Edge). Each edge has a pointer to the next (.getTo()) and a pointer to the previous (.getFrom()). I want to find the path of edges from a start Vertex to a Target Vertex. To store and create a path I have created a helper class DGPath. I want to do this in a recursive way.

Below the DGPath create path helper class:

/**
     * represents a path of connected vertices and edges in the graph
     */
    public class DGPath {
        private V start = null;
        private LinkedList<E> edges = new LinkedList<>();
        private double totalWeight = 0.0;
        private Set<V> visited = new HashSet<>();

        /**
         * representation invariants:
         * 1. The edges are connected by vertices, i.e. FOR ALL i: 0 < i < edges.length: edges[i].from == edges[i-1].to
         * 2. The path begins at vertex == start
         * 3. if edges is empty, the path also ends at vertex == start
         * otherwise edges[0].from == start and the path continues along edges[i].to for all 0 <= i < edges.length
         **/

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(
                    String.format("Weight=%f Length=%d Visited=%d (",
                            this.totalWeight, 1 + this.edges.size(), this.visited.size()));
            sb.append(start.getId());
            for (E e : edges) {
                sb.append(", " + e.getTo().getId());
            }
            sb.append(")");
            return sb.toString();
        }

        public V getStart() {
            return start;
        }

        public LinkedList<E> getEdges() {
            return edges;
        }

        public double getTotalWeight() {
            return totalWeight;
        }

        public Set<V> getVisited() {
            return visited;
        }
    }

Below the Depth first search method:

/**
     * Uses a depth-first search algorithm to find a path from the start vertex to the target vertex in the graph
     * The path.totalWeight should indicate the number of edges in the result path
     * All vertices that are being visited by the search should also be registered in path.visited
     *
     * @param startId the id of the start Vertex
     * @param targetId the id of the end Vertex
     * @return the DGpath for the path from start to target
     * returns null if either start or target cannot be matched with a vertex in the graph
     * or no path can be found from start to target
     */
    public DGPath depthFirstSearch(String startId, String targetId) {

        V start = this.getVertexById(startId);
        V target = this.getVertexById(targetId);
        if (start == null || target == null) return null;

        DGPath path = new DGPath();
        path.start = start;
        path.visited.add(start);

        // easy target
        if (start == target) return path;

        // TODO calculate the path from start to target by recursive depth-first-search
        //  (create another private recursive helper method)
        //  register all visited vertices while going, for statistical purposes
        //  if you hit the target: complete the path and bail out !!!

        for (E edge : start.getEdges()) {
            if (!path.getVisited().contains(target)) {
                dfsHelper(edge.getTo(), path.visited);
            } else {
                return path;
            }
        }

        // no path found, graph was not connected ???
        return null;
    }

And final, below the recursive helper method for the depth first search method:

private void dfsHelper(V current, Set<V> discovered) {
        discovered.add(current);
        for (E edge : current.getEdges()) {
            while(edge.getTo() != null){
                V nextV = edge.getTo();
                if (!discovered.contains(nextV)) {
                    dfsHelper(nextV, discovered);
                }
            }
        }

    }

This code does not work right now, it keeps stuck in the recursion.

How can I change this code to find the right path from start Vertex to target Vertex?
How can I save the edges that are used to get from start to target in DGPath.edges?

Answer

I think the problem is you call the dfsHelper function inside a for loop (which I see no reason why you need a loop!!). For each iteration you have to empty the path.visited at the end of loop, and again do path.visited.add(start);

Regarding your second question, define another field for path, say edges, and whenever you add a new node to path.visited, add the corresponding edge to path.edges (don’t forget to refresh the path.edges like path.visited for each iteration) the path.visited would have what you want after calling depthFirstSearch

Advertisement

Answer