1
\$\begingroup\$

The class in this post returns a directed cycle in a financial loan graph. A financial loan graph consists of nodes and directed arcs. If there is an arc \$(u, v)\$ with weight \$w = w(u, v)\$, then we interpret it as that \$u\$ has lent \$w\$ number of resources to \$v\$.

Since in a dense directed graph with \$n\$ nodes there may be up to \$n^2 - n = \Theta(n^2)\$ arcs, we might be interested in minimizing the number of arcs in the loan graph such that debt information is preserved. (See this Wordpress post for more thourough discussion.) (The project repository is here.)

Please note that without modifying the graph, the method will return always the same cycle. It is used in a setting where at least one arc of a cycle is removed from the graph, which, in turn, will result obtaining another cycles.

net.coderodde.loan.model.support.RecursiveDepthFirstSearch:

package net.coderodde.loan.model.support;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import net.coderodde.loan.model.Graph;
import net.coderodde.loan.model.Node;

/**
 * This class implements a recursive depth-first search variant returning a 
 * directed cycle.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 4, 2021)
 * @since 1.6 (Sep 4, 2021)
 */
public class RecursiveDepthFirstSearch {

    private final Set<Node> marked = new HashSet<>();
    private final Set<Node> stack = new HashSet<>();
    private final Map<Node, Node> parents = new HashMap<>();
    
    public List<Node> findCycle(Graph graph) {
        for (Node root : graph) {
            if (!marked.contains(root)) {
                parents.put(root, null);
                
                List<Node> cycle = findCycleImpl(root);

                if (cycle != null) {
                    clearDataStructures();
                    return cycle;
                }
            }
        }
        
        clearDataStructures();
        return null;
    }
    
    private void clearDataStructures() {
        marked.clear();
        stack.clear();
        parents.clear();
    }
    
    private List<Node> findCycleImpl(Node root) {
        if (marked.contains(root)) {
            return null;
        }
        
        if (stack.contains(root)) {
            List<Node> cycle = new ArrayList<>();
            Node currentNode = parents.get(root);
            
            while (currentNode != root) {
                cycle.add(currentNode);
                currentNode = parents.get(currentNode);
            }
            
            cycle.add(root);
            Collections.<Node>reverse(cycle);
            return cycle;
        }
        
        stack.add(root);
        
        for (Node child : root) {
            parents.put(child, root);
            List<Node> cycleCandidate = findCycleImpl(child);
            
            if (cycleCandidate != null) {
                return cycleCandidate;
            }
        }
        
        stack.remove(root);
        marked.add(root);
        return null;
    }
}

Related posts:

  1. Loan graph simplification in Java: an arc minimization algorithm
  2. Loan graph simplification in Java: the graph data structures

Critique request

Please, tell me anything that comes to mind. ^^

\$\endgroup\$
1
\$\begingroup\$

Couldn't this class just have static methods and members? You wouldn't need to create an instance every time you want to DFS and you reset the internal sets/maps after each search anyways. I'm not sure about how you plan on using this class later on or if it still works if everything is static, so it might be fine as-is.

Also, consider renaming the class to just DFS. You don't have any other ...DepthFirstSearch classes, so you could drop the Recursive part. Also, it might sound like the class is trying to distinguish itself from a IterativeDFS and both classes are extensions of an AbstractDFS / DFS. DFS seems to be a common enough shorthand to use and someone using an IDE will also see your doc comments.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.