001/*
002MIT License
003
004Copyright (c) 2020 earlygrey
005
006Permission is hereby granted, free of charge, to any person obtaining a copy
007of this software and associated documentation files (the "Software"), to deal
008in the Software without restriction, including without limitation the rights
009to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
010copies of the Software, and to permit persons to whom the Software is
011furnished to do so, subject to the following conditions:
012
013The above copyright notice and this permission notice shall be included in all
014copies or substantial portions of the Software.
015
016THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
017IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
018FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
019AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
020LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
021OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
022SOFTWARE.
023 */
024package squidpony.squidai.graph;
025
026import java.util.ArrayList;
027
028/**
029 * Algorithms specific to directed graphs, like {@link CostlyGraph}, as well as general {@link Algorithms}.
030 * Currently, this only adds a {@link #topologicalSort()} method and its overload.
031 * @param <V> the vertex type; often {@link squidpony.squidmath.Coord}
032 * @author earlygrey
033 */
034public class DirectedGraphAlgorithms<V> extends Algorithms<V> {
035
036    DirectedGraphAlgorithms(DirectedGraph<V> graph) {
037        super(graph);
038    }
039
040    /**
041     * Sort the vertices of this graph in topological order. That is, for every edge from vertex u to vertex v, u comes
042     * before v in the ordering. This is reflected in the iteration order of the collection returned by
043     * {@link Graph#getVertices()}. Note that the graph cannot contain any cycles for a topological order to exist. If a
044     * cycle exists, this method will do nothing.
045     * @return true if the sort was successful, false if the graph contains a cycle
046     */
047    public boolean topologicalSort() {
048        return implementations.topologicalSort();
049    }
050
051    /**
052     * Perform a topological sort on the graph, and puts the sorted vertices in the supplied list.
053     * That is, for every edge from vertex u to vertex v, u will come before v in the supplied list.
054     * Note that the graph cannot contain any cycles for a topological order to exist. If a cycle exists, the sorting
055     * procedure will terminate and the supplied list will only contain the vertices up until the point of termination.
056     * @param sortedVertices an ArrayList of V vertices that will be cleared and modified in-place
057     * @return true if the sort was successful, false if the graph contains a cycle
058     */
059    public boolean topologicalSort(ArrayList<V> sortedVertices) {
060        return implementations.topologicalSort(sortedVertices);
061    }
062
063
064}