# Loan graph simplification in Java: the recursive DFS for searching for directed cycles

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) {
currentNode = parents.get(currentNode);
}

Collections.<Node>reverse(cycle);
return cycle;
}

for (Node child : root) {
parents.put(child, root);
List<Node> cycleCandidate = findCycleImpl(child);

if (cycleCandidate != null) {
return cycleCandidate;
}
}

stack.remove(root);
return null;
}
}


## Critique request

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

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.