framework/base/src/main/java/org/apache/ofbiz/base/util/Digraph.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.ofbiz.base.util;

import static java.util.stream.Collectors.toSet;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * A basic directed graph utilitary.
 * <p>
 * A directed graph is a data structure consisting of nodes and arrows connecting those nodes
 * which are called <em>edges</em>. In a directed graph edges are ordered pairs of respectively
 * source and target nodes.
 * <p>
 * This implementation is adapted to small in-memory graphs.
 *
 * @param <T> the type of the nodes
 * @see <a href="https://www.wikipedia.org/wiki/Directed_graph">Directed graph</a>
 */
public class Digraph<T> {
    /** The map associating source nodes to their adjacent target nodes. */
    private final Map<T, Collection<T>> edges;
    /** The set of nodes */
    private final Set<T> nodes;

    /**
     * Constructs a directed graph from a specification Map.
     * @param spec  the map defining a set of source nodes (keys) that are linked to a collection
     *              of adjacent target nodes (values). Both keys and values must not be {@code null}.
     * @throws IllegalArgumentException when a target node is not present in the sources nodes.
     */
    public Digraph(Map<T, Collection<T>> spec) throws IllegalArgumentException {
        this.edges = spec;
        this.nodes = spec.keySet();
        // Check that all adjacent nodes are present as keys in the map.
        Set<T> undeclaredNodes = spec.values().stream()
                .flatMap(Collection::stream)
                .filter(child -> !nodes.contains(child))
                .collect(toSet());
        if (!undeclaredNodes.isEmpty()) {
            String msg = String.format("%s nodes are not present in the graph", undeclaredNodes);
            throw new IllegalArgumentException(msg);
        }
    }

    /**
     * Sort nodes in a topological ordering assuming that this graph is acyclic.
     * <p>
     * A graph without cycles is often called a <em>Directed Acyclic Graph</em> (DAG).
     * @return a linear ordering of nodes such for every edge in the graph its target node
     *         is present before its source node.
     * @throws IllegalStateException when this graph contains a cycle.
     * @see <a href="https://www.wikipedia.org/wiki/Topological_sorting">topological sorting</a>
     * @see <a href="https://www.wikipedia.org/wiki/Directed_acyclic_graph">DAG</a>
     */
    public List<T> sort() throws IllegalStateException {
        Set<T> permanents = new HashSet<>();
        Set<T> temporaries = new HashSet<>();
        List<T> result = new ArrayList<>();
        for (T node : nodes) {
            if (!permanents.contains(node)) {
                visit(result, node, permanents, temporaries);
            }
        }
        return result;
    }

    /**
     * Traverses the graph using <em>Depth First Search</em> (DFS) to construct a topological ordering.
     * @param res  the ordered list that we are building
     * @param root  the current node we are visiting
     * @param permanents  the nodes that have been successfully been visited
     * @param temporaries  the nodes that we have started to visit but might contain cycles.
     * @throws IllegalStateException when a cycle is found.
     * @see #sort
     * @see <a href="https://www.wikipedia.org/wiki/Depth-first_search">Depth Dirst Search</a>
     */
    private void visit(List<T> res, T root, Set<T> permanents, Set<T> temporaries) throws IllegalStateException {
        if (permanents.contains(root)) {
            return;
        } else if (temporaries.contains(root)) {
            throw new IllegalStateException("A cycle has been found");
        } else {
            temporaries.add(root);
            for (T next : edges.get(root)) {
                visit(res, next, permanents, temporaries);
            }
            temporaries.remove(root);
            permanents.add(root);
            res.add(root);
        }
    }
}