Hoogle Search
Within LTS Haskell 24.32 (ghc-9.10.3)
Note that Stackage only displays results for the latest LTS and Nightly snapshot. Learn more.
topSort :: Ord a => AdjacencyMap a -> Either (Cycle a) [a]algebraic-graphs Algebra.Graph.AdjacencyMap.Algorithm Compute a topological sort of a graph or discover a cycle. Vertices are explored in the decreasing order according to their Ord instance. This gives the lexicographically smallest topological ordering in the case of success. In the case of failure, the cycle is characterized by being the lexicographically smallest up to rotation with respect to Ord (Dual Int) in the first connected component of the graph containing a cycle, where the connected components are ordered by their largest vertex with respect to Ord a. Complexity: O((n + m) * min(n,W)) time and O(n) space.
topSort (1 * 2 + 3 * 1) == Right [3,1,2] topSort (path [1..5]) == Right [1..5] topSort (3 * (1 * 4 + 2 * 5)) == Right [3,1,2,4,5] topSort (1 * 2 + 2 * 1) == Left (2 :| [1]) topSort (path [5,4..1] + edge 2 4) == Left (4 :| [3,2]) topSort (circuit [1..3]) == Left (3 :| [1,2]) topSort (circuit [1..3] + circuit [3,2,1]) == Left (3 :| [2]) topSort (1 * 2 + (5 + 2) * 1 + 3 * 4 * 3) == Left (1 :| [2]) fmap (flip isTopSortOf x) (topSort x) /= Right False isRight . topSort == isAcyclic topSort . vertices == Right . nub . sort
isTopSortOf :: ToGraph t => [ToVertex t] -> t -> Boolalgebraic-graphs Algebra.Graph.ToGraph Check if a given list of vertices is a valid topological sort of a graph.
isTopSortOf vs == Algebra.Graph.AdjacencyMap.isTopSortOf vs . toAdjacencyMap
topSort :: ToGraph t => t -> Either (Cycle (ToVertex t)) [ToVertex t]algebraic-graphs Algebra.Graph.ToGraph Compute the topological sort of a graph or a AM.Cycle if the graph is cyclic.
topSort == Algebra.Graph.AdjacencyMap.topSort . toAdjacencyMap
-
algebraic-graphs Data.Graph.Typed Compute the topological sort of a graph. Note that this function returns a result even if the graph is cyclic. In the following examples we will use the helper function:
(%) :: Ord a => (GraphKL a -> b) -> AdjacencyMap a -> b f % x = f (fromAdjacencyMap x)
for greater clarity.topSort % (1 * 2 + 3 * 1) == [3,1,2] topSort % (1 * 2 + 2 * 1) == [1,2]
showCSSortedByFrequency :: ConflictMap -> ConflictSet -> Stringcabal-install-solver Distribution.Solver.Modular.ConflictSet No documentation available.
topSort :: Graph e -> [Vertex]cabal-install-solver Distribution.Solver.Modular.LabeledGraph No documentation available.
-
data-sketches-core DataSketches.Quantiles.RelativeErrorQuantile.Internal.Auxiliary No documentation available.
isSorted :: PrimMonad m => DoubleBuffer (PrimState m) -> m Booldata-sketches-core DataSketches.Quantiles.RelativeErrorQuantile.Internal.DoubleBuffer No documentation available.
-
data-sketches-core DataSketches.Quantiles.RelativeErrorQuantile.Internal.DoubleBuffer Merges the incoming sorted buffer into this sorted buffer.
toAscListSortedOn :: (a -> String) -> Set a -> [a]distribution-nixpkgs Language.Nix.PrettyPrinting No documentation available.