Sorting.hs

-- Note: this is an automatically generated file. Do not edit.

-- | Test cases for topological sorting algorithms

module Hydra.Test.Sorting where

import qualified Hydra.Testing as Testing
import Prelude hiding  (Enum, Ordering, decodeFloat, encodeFloat, fail, map, pure, sum)
import qualified Data.ByteString as B
import qualified Data.Int as I
import qualified Data.List as L
import qualified Data.Map as M
import qualified Data.Set as S

-- | Test cases for topological sorting
allTests :: Testing.TestGroup
allTests = Testing.TestGroup {
  Testing.testGroupName = "sorting",
  Testing.testGroupDescription = Nothing,
  Testing.testGroupSubgroups = [
    Testing.TestGroup {
      Testing.testGroupName = "topological sort",
      Testing.testGroupDescription = Nothing,
      Testing.testGroupSubgroups = [],
      Testing.testGroupCases = [
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "empty set",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [],
            Testing.topologicalSortTestCaseExpected = (Right [])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "singleton set",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (1, [])],
            Testing.topologicalSortTestCaseExpected = (Right [
              1])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "discrete set with multiple elements",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (3, []),
              (1, []),
              (2, [])],
            Testing.topologicalSortTestCaseExpected = (Right [
              1,
              2,
              3])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "linked list",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (3, [
                1]),
              (2, [
                3]),
              (1, [])],
            Testing.topologicalSortTestCaseExpected = (Right [
              1,
              3,
              2])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "binary tree",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (3, [
                1,
                4]),
              (4, [
                6,
                2]),
              (1, [
                5]),
              (2, []),
              (6, []),
              (5, [])],
            Testing.topologicalSortTestCaseExpected = (Right [
              5,
              1,
              2,
              6,
              4,
              3])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "two trees",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (3, [
                1,
                4]),
              (5, [
                6,
                2]),
              (2, [
                7]),
              (1, []),
              (4, []),
              (6, []),
              (7, [])],
            Testing.topologicalSortTestCaseExpected = (Right [
              1,
              7,
              2,
              4,
              3,
              6,
              5])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "diamond DAG",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (1, [
                3,
                4]),
              (3, [
                2]),
              (4, [
                2]),
              (2, [
                5]),
              (5, [])],
            Testing.topologicalSortTestCaseExpected = (Right [
              5,
              2,
              3,
              4,
              1])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "two-node cycle",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (1, [
                2]),
              (2, [
                1])],
            Testing.topologicalSortTestCaseExpected = (Left [
              [
                1,
                2]])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "cycle with incoming and outgoing edges",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSort (Testing.TopologicalSortTestCase {
            Testing.topologicalSortTestCaseAdjacencyList = [
              (1, [
                3]),
              (3, [
                2]),
              (2, [
                3,
                4]),
              (4, [
                5]),
              (5, [])],
            Testing.topologicalSortTestCaseExpected = (Left [
              [
                2,
                3]])})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []}]},
    Testing.TestGroup {
      Testing.testGroupName = "topological sort SCC",
      Testing.testGroupDescription = Nothing,
      Testing.testGroupSubgroups = [],
      Testing.testGroupCases = [
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "empty set",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [],
            Testing.topologicalSortSCCTestCaseExpected = []})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "singleton set",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (1, [])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "discrete set with multiple elements",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (3, []),
              (1, []),
              (2, [])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1],
              [
                2],
              [
                3]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "single two-element component #1",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (1, [
                2]),
              (2, [])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                2],
              [
                1]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "single two-element component #2",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (2, [
                1]),
              (1, [])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1],
              [
                2]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "multiple-element component",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (2, [
                1,
                3]),
              (1, [
                3]),
              (3, [])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                3],
              [
                1],
              [
                2]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "cycle of two nodes #1",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (1, [
                2]),
              (2, [
                1])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1,
                2]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "cycle of two nodes #2",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (2, [
                1]),
              (1, [
                2])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1,
                2]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "cycle of three nodes #1",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (1, [
                2]),
              (2, [
                3]),
              (3, [
                1])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1,
                2,
                3]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "cycle of three nodes #2",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (2, [
                1]),
              (3, [
                2]),
              (1, [
                3])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1,
                2,
                3]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "multiple disconnected cycles",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (200, []),
              (100, []),
              (300, []),
              (10, [
                20]),
              (20, [
                10]),
              (1, [
                2]),
              (2, [
                3]),
              (3, [
                1])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1,
                2,
                3],
              [
                10,
                20],
              [
                100],
              [
                200],
              [
                300]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "complex cycles",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (1, [
                2,
                3]),
              (2, [
                3]),
              (3, [
                1])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                1,
                2,
                3]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "chain of three SCCs",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (1, [
                2,
                10]),
              (2, [
                3]),
              (3, [
                1]),
              (10, [
                20]),
              (20, [
                100,
                10]),
              (100, [])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                100],
              [
                10,
                20],
              [
                1,
                2,
                3]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []},
        Testing.TestCaseWithMetadata {
          Testing.testCaseWithMetadataName = "SCCs with dependencies to/from non-SCC nodes",
          Testing.testCaseWithMetadataCase = (Testing.TestCaseTopologicalSortSCC (Testing.TopologicalSortSCCTestCase {
            Testing.topologicalSortSCCTestCaseAdjacencyList = [
              (1, [
                2,
                3,
                10]),
              (2, [
                3]),
              (3, [
                1]),
              (10, [
                20,
                30]),
              (20, [
                30]),
              (30, []),
              (100, [
                200,
                2]),
              (200, []),
              (300, [
                100]),
              (1000, []),
              (2000, [])],
            Testing.topologicalSortSCCTestCaseExpected = [
              [
                30],
              [
                20],
              [
                10],
              [
                1,
                2,
                3],
              [
                200],
              [
                100],
              [
                300],
              [
                1000],
              [
                2000]]})),
          Testing.testCaseWithMetadataDescription = Nothing,
          Testing.testCaseWithMetadataTags = []}]}],
  Testing.testGroupCases = []}