Упрощение ссудного графа в Java: рекурсивная DFS для поиска ориентированных циклов

Класс в этом посте возвращает направленный цикл в график финансового кредита. Граф финансового кредита состоит из узлов и направленных дуг. Если есть дуга $(u, v)$ с весом $ w = w (u, v) $, то мы интерпретируем это как $ u $ одолжил $ w $ количество ресурсов для $v$.

Поскольку в плотном ориентированном графе с $ n $ узлов может быть до $ n ^ 2 – n = Theta (n ^ 2) $ дуг, нас может заинтересовать минимизация количества дуг в графе ссуд, чтобы информация о долге сохранялась. (Видеть этот пост WordPress для более обстоятельного обсуждения.) (Репозиторий проекта здесь.)

Обратите внимание, что без изменения графика метод всегда будет возвращать один и тот же цикл. Он используется в настройках, когда по крайней мере одна дуга цикла удаляется из графика, что, в свою очередь, приводит к получению других циклов.

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;
    }
}

Похожие сообщения:

  1. Упрощение ссудного графа в Java: алгоритм минимизации дуги
  2. Упрощение графа ссуд в Java: структуры данных графа

Запрос на критику

Пожалуйста, расскажите мне все, что придет в голову. ^^

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *