From ef0a8f98e9b33d00578b0b7a21363eb093517947 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Wed, 22 Jan 2014 09:04:28 +0100 Subject: add topological sort MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/algorithms/sorting/other/TopologicalSort.java | 243 ++++++++++++++++++++++ 1 file changed, 243 insertions(+) create mode 100644 src/algorithms/sorting/other/TopologicalSort.java (limited to 'src/algorithms/sorting/other') diff --git a/src/algorithms/sorting/other/TopologicalSort.java b/src/algorithms/sorting/other/TopologicalSort.java new file mode 100644 index 0000000..48ff604 --- /dev/null +++ b/src/algorithms/sorting/other/TopologicalSort.java @@ -0,0 +1,243 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see . + */ +package algorithms.sorting.other; + +import java.util.*; + + +/** + * Topological sorting class. There are a few ways to perform + * a topological sort, this class implements an topological + * sort with advisory dependencies and strict dependencies. + * Dependencies are broken when there are cyclic dependencies, + * but if the dependency is strict rather than advisory, the + * algorithm fails. Additionally, this this, implementation + * uses two input parameters, a map from items to sets of + * dependencies, and a map from items, to a set of strict + * dependencies. The strict dependencies must appear in both + * of the sets, whilst the advisory dependencies must only + * appear in the first set of dependencies. This implemention + * tries to minimise the number of transversially broken + * dependencies. It is advisable to use both hash based maps + * and sets. + * + * @param The data type that has been sorted + */ +public class TopologicalSort +{ + /** + * Constructor + */ + private TopologicalSort() + { + /* Do nothing */ + } + + + + /** + * List of missing dependencies. There may be duplicates, + * see {@link #missingDependent}. + */ + public ArrayList missingDependency = new ArrayList(); + + /** + * List of items with missing dependencies. For any give index + * i, the element in {@link #missingDependency} with index i + * is required by the element with index i in this list. + */ + public ArrayList missingDependent = new ArrayList(); + + /** + * The items in topological order + */ + public ArrayList order = new ArrayList(); + + /** + * If an items exists as a key in this map it has been used + * to break a cyclic dependency. The associated value of a + * key is a set of all direct dependencies that will appear + * later in the topologically ordered list {@link #order}. + */ + public HashMap> breaks = new HashMap>(); + + /** + * Whether the topological sort was successful, i.e., not + * absolute dependencies needed to be broken. If this value + * is {@code false}, the topologically ordered list and + * the map of cyclic dependency breaks may no be complete. + */ + public boolean successful = false; + + + + /** + * Topolocally sort data. + * + * @param dependencies Map for items to their advisory dependencies, will be modified + * @param absolutes Map for items to their absolute dependencies + * @return A data structure with the result of the topological sort + */ + @SuppressWarnings("unchecked") + public static TopologicalSort tsort(Map> dependencies, Map> absolutes) + { + TopologicalSort rc = new TopologicalSort(); + if (absolutes == null) /* sugar */ + absolutes = new HashMap>(); + + /* Find, list and remove missing dependencies */ + { + HashMap> removed = new HashMap>(); + for (Map.Entry> req_deps : dependencies.entrySet()) + { + T req = req_deps.getKey(); + for (T dep : req_deps.getValue()) + if (dependencies.containsKey(dep) == false) + { + rc.missingDependency.add(dep); + rc.missingDependent.add(req); + if (removed.containsKey(dep) == false) + removed.put(dep, new ArrayList()); + removed.get(dep).add(req); + } + } + for (Map.Entry> remove_reqs : removed.entrySet()) + { + T remove = remove_reqs.getKey(); + for (T req : remove_reqs.getValue()) + dependencies.get(req).remove(remove); + } + } + + /* Sort cyclic graph topologically */ + { + ArrayList removed = new ArrayList(); + removed.add(null); + while (removed.size() > 0) + { + /* Sort acyclic graph topologically */ + while (removed.size() > 0) + { + removed.clear(); + /* Report and remove items with no unresolved dependency */ + T[] dependencies_ = (T[])(new Object[dependencies.size()]); /* needed to avoid concurrent modification */ + int i = 0; + for (T key : dependencies.keySet()) + dependencies_[i++] = key; + for (T item : dependencies_) + if (dependencies.get(item).size() == 0) + { + rc.order.add(item); + removed.add(item); + dependencies.remove(item); + } + /* Remove reported items from dependency lists */ + for (Map.Entry> req_deps : dependencies.entrySet()) + { + T req = req_deps.getKey(); + Set deps = req_deps.getValue(); + for (T old : removed) + if (deps.contains(old)) + deps.remove(old); + } + } + + /* Break one cycle with as few transversial dependencies as possible */ + if (dependencies.size() > 0) + { + T best = null; + HashSet bestBreaks = null; + /* Find best cycle break */ + for (Map.Entry> item_deps : dependencies.entrySet()) + { + T item = item_deps.getKey(); + Set queue_ = item_deps.getValue(); + Set abs_ = absolutes.get(item); + + HashSet abs = new HashSet(); + if (abs_ != null) + for (T elem : abs_) + abs.add(elem); + + HashSet deps = new HashSet(); + T[] queue = (T[])(new Object[queue_.size()]); + int queue_h = 0, queue_t = 0; + for (T elem : queue_) + queue[queue_t++] = elem; + deps.add(item); + boolean bad = false; + + while (queue_h != queue_t) + { + T dep = queue[queue_h++]; + if (abs.contains(dep)) + { + bad = true; + break; + } + if (deps.contains(dep)) + continue; + deps.add(dep); + + Set extra = dependencies.get(dep); + queue_t -= queue_h; + System.arraycopy(queue, queue_h, queue = (T[])(new Object[queue_t + extra.size()]), 0, queue_t); + queue_h = 0; + for (T elem : extra) + queue[queue_t++] = elem; + + if ((extra = absolutes.get(dep)) != null) + for (T elem : extra) + abs.add(elem); + } + + if (bad) + continue; + deps.remove(item); + if ((best == null) || (bestBreaks.size() > deps.size())) + { + best = item; + bestBreaks = deps; + } + } + + /* List cycle break and remove item */ + if (best == null) + return rc; + rc.order.add(best); + rc.breaks.put(best, bestBreaks); + removed.add(best); + dependencies.remove(best); + + /* Remove item from dependency lists */ + for (Map.Entry> item_deps : dependencies.entrySet()) + { + T item = item_deps.getKey(); + Set deps = item_deps.getValue(); + if (deps.contains(item) == false) + deps.remove(best); + } + } + } + } + + rc.successful = true; + return rc; + } + +} + -- cgit v1.2.3-70-g09d2