    {-# LANGUAGE MultiParamTypeClasses #-}

    -- | Example Graphs
    module Data.Graph.Inductive.Example(
        -- * Auxiliary Functions
        genUNodes, genLNodes, labUEdges, noEdges,
        -- * Small Dynamic Graphs
        a, b, c, e, loop, ab, abb, dag3, e3, cyc3, g3, g3b, dag4, d1, d3,
        -- * Small Static Graphs
        a', b', c', e', loop', ab', abb', dag3', e3', dag4', d1', d3',
        -- * Functions to Create (Regular) Graphs
        ucycle, star, ucycleM, starM,
        -- * More Graphs
        -- | clr : Cormen\/Leiserson\/Rivest

        -- | kin : Kingston

        -- ** Dynamic Versions
        clr479, clr489, clr486, clr508, clr528, clr595, gr1, kin248, vor,
        -- ** Static Versions
        clr479', clr489', clr486', clr508', clr528', kin248', vor'
    )where

    import Data.Graph.Inductive.Graph
    import Data.Graph.Inductive.PatriciaTree

    import Data.Graph.Inductive.Monad
    import Data.Graph.Inductive.Monad.IOArray

    -- | generate list of unlabeled nodes
    genUNodes :: Int -> [UNode]
    genUNodes :: Node -> [UNode]
    genUNodes Node
    n = [Node] -> [()] -> [UNode]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    n] (() -> [()]
    forall a. a -> [a]
    repeat ())

    -- | generate list of labeled nodes
    genLNodes :: (Enum a) => a -> Int -> [LNode a]
    genLNodes :: forall a. Enum a => a -> Node -> [LNode a]
    genLNodes a
    q Node
    i = Node -> [LNode a] -> [LNode a]
    forall a. Node -> [a] -> [a]
    take Node
    i ([Node] -> [a] -> [LNode a]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..] [a
    q..])

    -- | denote unlabeled edges
    labUEdges :: [Edge] -> [UEdge]
    labUEdges :: [Edge] -> [UEdge]
    labUEdges = (Edge -> UEdge) -> [Edge] -> [UEdge]
    forall a b. (a -> b) -> [a] -> [b]
    map (\(Node
    i,Node
    j) -> (Node
    i,Node
    j,()))

    -- | empty (unlabeled) edge list
    noEdges :: [UEdge]
    noEdges :: [UEdge]
    noEdges = []

    a,b,c,e,loop,ab,abb,dag3   :: Gr Char ()
    e3                         :: Gr () String
    cyc3,g3,g3b                :: Gr Char String
    dag4                       :: Gr Int ()
    d1,d3                      :: Gr Int Int

    a :: Gr Char ()
    a    = ([],Node
    1,Char
    'a',[]) Context Char () -> Gr Char () -> Gr Char ()
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & Gr Char ()
    forall a b. Gr a b
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b
    empty                  -- just a node
    b :: Gr Char ()
    b    = [LNode Char] -> [UEdge] -> Gr Char ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    2] [Char]
    "ab") [UEdge]
    noEdges      -- just two nodes
    c :: Gr Char ()
    c    = [LNode Char] -> [UEdge] -> Gr Char ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    3] [Char]
    "abc") [UEdge]
    noEdges     -- just three nodes
    e :: Gr Char ()
    e    = ([((),Node
    1)],Node
    2,Char
    'b',[]) Context Char () -> Gr Char () -> Gr Char ()
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & Gr Char ()
    a                -- just one edge a-->b
    e3 :: Gr () [Char]
    e3   = [UNode] -> [LEdge [Char]] -> Gr () [Char]
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Node -> [UNode]
    genUNodes Node
    2)
           [(Node
    1,Node
    2,[Char]
    "a"),(Node
    1,Node
    2,[Char]
    "b"),(Node
    1,Node
    2,[Char]
    "a")]        -- three edges (two labels) a-->b
    loop :: Gr Char ()
    loop = ([],Node
    1,Char
    'a',[((),Node
    1)]) Context Char () -> Gr Char () -> Gr Char ()
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & Gr Char ()
    forall a b. Gr a b
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b
    empty            -- loop on single node
    ab :: Gr Char ()
    ab   = ([((),Node
    1)],Node
    2,Char
    'b',[((),Node
    1)]) Context Char () -> Gr Char () -> Gr Char ()
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & Gr Char ()
    a          -- cycle of two nodes:  a<-->b
    abb :: Gr Char ()
    abb  = [LNode Char] -> [UEdge] -> Gr Char ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    2] [Char]
    "ab") ([Edge] -> [UEdge]
    labUEdges [(Node
    2,Node
    2)]) -- a and loop on b

    cyc3 :: Gr Char [Char]
    cyc3 = [Context Char [Char]] -> Gr Char [Char]
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    [Context a b] -> gr a b
    buildGr                                -- cycle of three nodes
           [([([Char]
    "ca",Node
    3)],Node
    1,Char
    'a',[([Char]
    "ab",Node
    2)]),
                    ([],Node
    2,Char
    'b',[([Char]
    "bc",Node
    3)]),
                    ([],Node
    3,Char
    'c',[])]

    dag3 :: Gr Char ()
    dag3 = [LNode Char] -> [UEdge] -> Gr Char ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    3] [Char]
    "abc") ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    3)])
    dag4 :: Gr Node ()
    dag4 = [Edge] -> [UEdge] -> Gr Node ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    4) ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    1,Node
    4),(Node
    2,Node
    3),(Node
    2,Node
    4),(Node
    4,Node
    3)])

    d1 :: Gr Node Node
    d1   = [Edge] -> [LEdge Node] -> Gr Node Node
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    2) [(Node
    1,Node
    2,Node
    1)]
    d3 :: Gr Node Node
    d3   = [Edge] -> [LEdge Node] -> Gr Node Node
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    3) [(Node
    1,Node
    2,Node
    1),(Node
    1,Node
    3,Node
    4),(Node
    2,Node
    3,Node
    2)]

    g3 :: Gr Char [Char]
    g3 = ([([Char]
    "left",Node
    2),([Char]
    "up",Node
    3)],Node
    1,Char
    'a',[([Char]
    "right",Node
    2)]) Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & (
                            ([],Node
    2,Char
    'b',[([Char]
    "down",Node
    3)])  Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & (
                            ([],Node
    3,Char
    'c',[])            Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & Gr Char [Char]
    forall a b. Gr a b
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b
    empty ))
    g3b :: Gr Char [Char]
    g3b = ([([Char]
    "down",Node
    2)], Node
    3,Char
    'c',[([Char]
    "up",Node
    1)])   Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & (
          ([([Char]
    "right",Node
    1)],Node
    2,Char
    'b',[([Char]
    "left",Node
    1)]) Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & (
                     ([],Node
    1,Char
    'a',[])           Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
    forall a b. Context a b -> Gr a b -> Gr a b
    forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    Context a b -> gr a b -> gr a b
    & Gr Char [Char]
    forall a b. Gr a b
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b
    empty ))

    a',b',c',e',loop',ab',abb',dag3' :: IO (SGr Char ())
    e3'                              :: IO (SGr () String)
    dag4'                            :: IO (SGr Int ())
    d1',d3'                          :: IO (SGr Int Int)

    a' :: IO (SGr Char ())
    a'    = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM [(Node
    1,Char
    'a')] [UEdge]
    noEdges              -- just a node
    b' :: IO (SGr Char ())
    b'    = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    2] [Char]
    "ab") [UEdge]
    noEdges      -- just two nodes
    c' :: IO (SGr Char ())
    c'    = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    3] [Char]
    "abc") [UEdge]
    noEdges     -- just three nodes
    e' :: IO (SGr Char ())
    e'    = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    2] [Char]
    "ab") [(Node
    1,Node
    2,())]   -- just one edge a-->b
    e3' :: IO (SGr () [Char])
    e3'   = [UNode] -> [LEdge [Char]] -> IO (SGr () [Char])
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Node -> [UNode]
    genUNodes Node
    2)
              [(Node
    1,Node
    2,[Char]
    "a"),(Node
    1,Node
    2,[Char]
    "b"),(Node
    1,Node
    2,[Char]
    "a")]       -- three edges (two labels) a-->b
    loop' :: IO (SGr Char ())
    loop' = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM [(Node
    1,Char
    'a')] [(Node
    1,Node
    1,())]           -- loop on single node
    ab' :: IO (SGr Char ())
    ab'   = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    2] [Char]
    "ab")
              [(Node
    1,Node
    2,()),(Node
    2,Node
    1,())]                   -- cycle of two nodes:  a<-->b
    abb' :: IO (SGr Char ())
    abb'  = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    2] [Char]
    "ab") ([Edge] -> [UEdge]
    labUEdges [(Node
    2,Node
    2)]) -- a and loop on b

    dag3' :: IO (SGr Char ())
    dag3' = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [Char] -> [LNode Char]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    3] [Char]
    "abc") ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    3)])
    dag4' :: IO (SGr Node ())
    dag4' = [Edge] -> [UEdge] -> IO (SGr Node ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    4) ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    1,Node
    4),(Node
    2,Node
    3),(Node
    2,Node
    4),(Node
    4,Node
    3)])

    d1' :: IO (SGr Node Node)
    d1'   = [Edge] -> [LEdge Node] -> IO (SGr Node Node)
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    2) [(Node
    1,Node
    2,Node
    1)]
    d3' :: IO (SGr Node Node)
    d3'   = [Edge] -> [LEdge Node] -> IO (SGr Node Node)
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    3) [(Node
    1,Node
    2,Node
    1),(Node
    1,Node
    3,Node
    4),(Node
    2,Node
    3,Node
    2)]

    ucycle :: (Graph gr) => Int -> gr () ()
    ucycle :: forall (gr :: * -> * -> *). Graph gr => Node -> gr () ()
    ucycle Node
    n = [Node] -> [Edge] -> gr () ()
    forall (gr :: * -> * -> *).
    Graph gr =>
    [Node] -> [Edge] -> gr () ()
    mkUGraph [Node]
    vs ((Node -> Edge) -> [Node] -> [Edge]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Node
    v->(Node
    v,Node
    v Node -> Node -> Node
    forall a. Integral a => a -> a -> a
    `mod` Node
    nNode -> Node -> Node
    forall a. Num a => a -> a -> a
    +Node
    1)) [Node]
    vs)
               where vs :: [Node]
    vs = [Node
    1..Node
    n]

    star :: (Graph gr) => Int -> gr () ()
    star :: forall (gr :: * -> * -> *). Graph gr => Node -> gr () ()
    star Node
    n = [Node] -> [Edge] -> gr () ()
    forall (gr :: * -> * -> *).
    Graph gr =>
    [Node] -> [Edge] -> gr () ()
    mkUGraph [Node
    1..Node
    n] ((Node -> Edge) -> [Node] -> [Edge]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Node
    v->(Node
    1,Node
    v)) [Node
    2..Node
    n])

    ucycleM :: (GraphM m gr) => Int -> m (gr () ())
    ucycleM :: forall (m :: * -> *) (gr :: * -> * -> *).
    GraphM m gr =>
    Node -> m (gr () ())
    ucycleM Node
    n = [Node] -> [Edge] -> m (gr () ())
    forall (m :: * -> *) (gr :: * -> * -> *).
    GraphM m gr =>
    [Node] -> [Edge] -> m (gr () ())
    mkUGraphM [Node]
    vs ((Node -> Edge) -> [Node] -> [Edge]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Node
    v->(Node
    v,Node
    v Node -> Node -> Node
    forall a. Integral a => a -> a -> a
    `mod` Node
    nNode -> Node -> Node
    forall a. Num a => a -> a -> a
    +Node
    1)) [Node]
    vs)
                where vs :: [Node]
    vs = [Node
    1..Node
    n]

    starM :: (GraphM m gr) => Int -> m (gr () ())
    starM :: forall (m :: * -> *) (gr :: * -> * -> *).
    GraphM m gr =>
    Node -> m (gr () ())
    starM Node
    n = [Node] -> [Edge] -> m (gr () ())
    forall (m :: * -> *) (gr :: * -> * -> *).
    GraphM m gr =>
    [Node] -> [Edge] -> m (gr () ())
    mkUGraphM [Node
    1..Node
    n] ((Node -> Edge) -> [Node] -> [Edge]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Node
    v->(Node
    1,Node
    v)) [Node
    2..Node
    n])

    clr479,clr489    :: Gr Char ()
    clr486           :: Gr String ()
    clr508,clr528    :: Gr Char Int
    clr595,gr1       :: Gr Int Int
    kin248           :: Gr Int ()
    vor              :: Gr String Int

    clr479 :: Gr Char ()
    clr479 = [LNode Char] -> [UEdge] -> Gr Char ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Char -> Node -> [LNode Char]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Char
    'u' Node
    6)
             ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    1,Node
    4),(Node
    2,Node
    5),(Node
    3,Node
    5),(Node
    3,Node
    6),(Node
    4,Node
    2),(Node
    5,Node
    4),(Node
    6,Node
    6)])
    clr486 :: Gr [Char] ()
    clr486 = [LNode [Char]] -> [UEdge] -> Gr [Char] ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [[Char]] -> [LNode [Char]]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    9] [[Char]
    "shorts",[Char]
    "socks",[Char]
    "watch",[Char]
    "pants",[Char]
    "shoes",
                                  [Char]
    "shirt",[Char]
    "belt",[Char]
    "tie",[Char]
    "jacket"])
                     ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    4),(Node
    1,Node
    5),(Node
    2,Node
    5),(Node
    4,Node
    5),(Node
    4,Node
    7),(Node
    6,Node
    7),(Node
    6,Node
    8),(Node
    7,Node
    9),(Node
    8,Node
    9)])
    clr489 :: Gr Char ()
    clr489 = [LNode Char] -> [UEdge] -> Gr Char ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Char -> Node -> [LNode Char]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Char
    'a' Node
    8)
                     ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    2,Node
    3),(Node
    2,Node
    5),(Node
    2,Node
    6),(Node
    3,Node
    4),(Node
    3,Node
    7),(Node
    4,Node
    3),(Node
    4,Node
    8),
                             (Node
    5,Node
    1),(Node
    5,Node
    6),(Node
    6,Node
    7),(Node
    7,Node
    6),(Node
    7,Node
    8),(Node
    8,Node
    8)])
    clr508 :: Gr Char Node
    clr508 = [LNode Char] -> [LEdge Node] -> Gr Char Node
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Char -> Node -> [LNode Char]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Char
    'a' Node
    9)
                     [(Node
    1,Node
    2,Node
    4),(Node
    1,Node
    8,Node
    8),(Node
    2,Node
    3,Node
    8),(Node
    2,Node
    8,Node
    11),(Node
    3,Node
    4,Node
    7),(Node
    3,Node
    6,Node
    4),(Node
    3,Node
    9,Node
    2),
                      (Node
    4,Node
    5,Node
    9),(Node
    4,Node
    6,Node
    14),(Node
    5,Node
    6,Node
    10),(Node
    6,Node
    7,Node
    2),(Node
    7,Node
    8,Node
    1),(Node
    7,Node
    9,Node
    6),(Node
    8,Node
    9,Node
    7)]
    clr528 :: Gr Char Node
    clr528 = [LNode Char] -> [LEdge Node] -> Gr Char Node
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph [(Node
    1,Char
    's'),(Node
    2,Char
    'u'),(Node
    3,Char
    'v'),(Node
    4,Char
    'x'),(Node
    5,Char
    'y')]
                     [(Node
    1,Node
    2,Node
    10),(Node
    1,Node
    4,Node
    5),(Node
    2,Node
    3,Node
    1),(Node
    2,Node
    4,Node
    2),(Node
    3,Node
    5,Node
    4),
                      (Node
    4,Node
    2,Node
    3),(Node
    4,Node
    3,Node
    9),(Node
    4,Node
    5,Node
    2),(Node
    5,Node
    1,Node
    7),(Node
    5,Node
    3,Node
    6)]
    clr595 :: Gr Node Node
    clr595 = [Edge] -> [LEdge Node] -> Gr Node Node
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [Node] -> [Edge]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    6] [Node
    1..Node
    6])
                     [(Node
    1,Node
    2,Node
    16),(Node
    1,Node
    3,Node
    13),(Node
    2,Node
    3,Node
    10),(Node
    2,Node
    4,Node
    12),(Node
    3,Node
    2,Node
    4),
                      (Node
    3,Node
    5,Node
    14),(Node
    4,Node
    3,Node
    9),(Node
    4,Node
    6,Node
    20),(Node
    5,Node
    4,Node
    7),(Node
    5,Node
    6,Node
    4)]
    gr1 :: Gr Node Node
    gr1    = [Edge] -> [LEdge Node] -> Gr Node Node
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [Node] -> [Edge]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    10] [Node
    1..Node
    10])
                     [(Node
    1,Node
    2,Node
    12),(Node
    1,Node
    3,Node
    1),(Node
    1,Node
    4,Node
    2),(Node
    2,Node
    3,Node
    1),(Node
    2,Node
    5,Node
    7),(Node
    2,Node
    6,Node
    5),(Node
    3,Node
    6,Node
    1),
                      (Node
    3,Node
    7,Node
    7),(Node
    4,Node
    3,Node
    3),(Node
    4,Node
    6,Node
    2),(Node
    4,Node
    7,Node
    5),(Node
    5,Node
    3,Node
    2),(Node
    5,Node
    6,Node
    3),(Node
    5,Node
    8,Node
    3),
                      (Node
    6,Node
    7,Node
    2),(Node
    6,Node
    8,Node
    3),(Node
    6,Node
    9,Node
    1),(Node
    7,Node
    9,Node
    9),(Node
    8,Node
    9,Node
    1),(Node
    8,Node
    10,Node
    4),(Node
    9,Node
    10,Node
    11)]
    kin248 :: Gr Node ()
    kin248 = [Edge] -> [UEdge] -> Gr Node ()
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    10)
                     ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    1,Node
    4),(Node
    1,Node
    7),(Node
    2,Node
    4),(Node
    2,Node
    5),(Node
    3,Node
    4),(Node
    3,Node
    10),
                             (Node
    4,Node
    5),(Node
    4,Node
    8),(Node
    5,Node
    2),(Node
    5,Node
    3),(Node
    6,Node
    7),(Node
    7,Node
    6),(Node
    7,Node
    8),
                             (Node
    8,Node
    10),(Node
    9,Node
    9),(Node
    9,Node
    10),(Node
    10,Node
    8),(Node
    10,Node
    9)])
             -- this is the inverse graph shown on the bottom of the page

    vor :: Gr [Char] Node
    vor = [LNode [Char]] -> [LEdge Node] -> Gr [Char] Node
    forall a b. [LNode a] -> [LEdge b] -> Gr a b
    forall (gr :: * -> * -> *) a b.
    Graph gr =>
    [LNode a] -> [LEdge b] -> gr a b
    mkGraph ([Node] -> [[Char]] -> [LNode [Char]]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    8] [[Char]
    "A",[Char]
    "B",[Char]
    "C",[Char]
    "H1",[Char]
    "H2",[Char]
    "D",[Char]
    "E",[Char]
    "F"])
                  [(Node
    1,Node
    4,Node
    3),(Node
    2,Node
    3,Node
    3),(Node
    2,Node
    4,Node
    3),(Node
    4,Node
    2,Node
    4),(Node
    4,Node
    6,Node
    2),
                   (Node
    5,Node
    2,Node
    5),(Node
    5,Node
    3,Node
    6),(Node
    5,Node
    7,Node
    5),(Node
    5,Node
    8,Node
    6),
                   (Node
    6,Node
    5,Node
    3),(Node
    6,Node
    7,Node
    2),(Node
    7,Node
    8,Node
    3),(Node
    8,Node
    7,Node
    3)]

    clr479',clr489'  :: IO (SGr Char ())
    clr486'          :: IO (SGr String ())
    clr508',clr528'  :: IO (SGr Char Int)
    kin248'          :: IO (SGr Int ())
    vor'             :: IO (SGr String Int)

    clr479' :: IO (SGr Char ())
    clr479' = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Char -> Node -> [LNode Char]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Char
    'u' Node
    6)
              ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    1,Node
    4),(Node
    2,Node
    5),(Node
    3,Node
    5),(Node
    3,Node
    6),(Node
    4,Node
    2),(Node
    5,Node
    4),(Node
    6,Node
    6)])
    clr486' :: IO (SGr [Char] ())
    clr486' = [LNode [Char]] -> [UEdge] -> IO (SGr [Char] ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [[Char]] -> [LNode [Char]]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    9] [[Char]
    "shorts",[Char]
    "socks",[Char]
    "watch",[Char]
    "pants",[Char]
    "shoes",
                                    [Char]
    "shirt",[Char]
    "belt",[Char]
    "tie",[Char]
    "jacket"])
                       ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    4),(Node
    1,Node
    5),(Node
    2,Node
    5),(Node
    4,Node
    5),(Node
    4,Node
    7),(Node
    6,Node
    7),(Node
    6,Node
    8),(Node
    7,Node
    9),(Node
    8,Node
    9)])
    clr489' :: IO (SGr Char ())
    clr489' = [LNode Char] -> [UEdge] -> IO (SGr Char ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Char -> Node -> [LNode Char]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Char
    'a' Node
    8)
                       ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    2,Node
    3),(Node
    2,Node
    5),(Node
    2,Node
    6),(Node
    3,Node
    4),(Node
    3,Node
    7),(Node
    4,Node
    3),(Node
    4,Node
    8),
                               (Node
    5,Node
    1),(Node
    5,Node
    6),(Node
    6,Node
    7),(Node
    7,Node
    6),(Node
    7,Node
    8),(Node
    8,Node
    8)])
    clr508' :: IO (SGr Char Node)
    clr508' = [LNode Char] -> [LEdge Node] -> IO (SGr Char Node)
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Char -> Node -> [LNode Char]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Char
    'a' Node
    9)
                       [(Node
    1,Node
    2,Node
    4),(Node
    1,Node
    8,Node
    8),(Node
    2,Node
    3,Node
    8),(Node
    2,Node
    8,Node
    11),(Node
    3,Node
    4,Node
    7),(Node
    3,Node
    6,Node
    4),(Node
    3,Node
    9,Node
    2),
                       (Node
    4,Node
    5,Node
    9),(Node
    4,Node
    6,Node
    14),(Node
    5,Node
    6,Node
    10),(Node
    6,Node
    7,Node
    2),(Node
    7,Node
    8,Node
    1),(Node
    7,Node
    9,Node
    6),(Node
    8,Node
    9,Node
    7)]
    clr528' :: IO (SGr Char Node)
    clr528' = [LNode Char] -> [LEdge Node] -> IO (SGr Char Node)
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM [(Node
    1,Char
    's'),(Node
    2,Char
    'u'),(Node
    3,Char
    'v'),(Node
    4,Char
    'x'),(Node
    5,Char
    'y')]
                       [(Node
    1,Node
    2,Node
    10),(Node
    1,Node
    4,Node
    5),(Node
    2,Node
    3,Node
    1),(Node
    2,Node
    4,Node
    2),(Node
    3,Node
    5,Node
    4),
                        (Node
    4,Node
    2,Node
    3),(Node
    4,Node
    3,Node
    9),(Node
    4,Node
    5,Node
    2),(Node
    5,Node
    1,Node
    7),(Node
    5,Node
    3,Node
    6)]
    kin248' :: IO (SGr Node ())
    kin248' = [Edge] -> [UEdge] -> IO (SGr Node ())
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM (Node -> Node -> [Edge]
    forall a. Enum a => a -> Node -> [LNode a]
    genLNodes Node
    1 Node
    10)
                       ([Edge] -> [UEdge]
    labUEdges [(Node
    1,Node
    2),(Node
    1,Node
    4),(Node
    1,Node
    7),(Node
    2,Node
    4),(Node
    2,Node
    5),(Node
    3,Node
    4),(Node
    3,Node
    10),
                               (Node
    4,Node
    5),(Node
    4,Node
    8),(Node
    5,Node
    2),(Node
    5,Node
    3),(Node
    6,Node
    7),(Node
    7,Node
    6),(Node
    7,Node
    8),
                               (Node
    8,Node
    10),(Node
    9,Node
    9),(Node
    9,Node
    10),(Node
    10,Node
    8),(Node
    10,Node
    9)])
             -- this is the inverse graph shown on the bottom of the page

    vor' :: IO (SGr [Char] Node)
    vor' = [LNode [Char]] -> [LEdge Node] -> IO (SGr [Char] Node)
    forall a b. [LNode a] -> [LEdge b] -> IO (SGr a b)
    forall (m :: * -> *) (gr :: * -> * -> *) a b.
    GraphM m gr =>
    [LNode a] -> [LEdge b] -> m (gr a b)
    mkGraphM ([Node] -> [[Char]] -> [LNode [Char]]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Node
    1..Node
    8] [[Char]
    "A",[Char]
    "B",[Char]
    "C",[Char]
    "H1",[Char]
    "H2",[Char]
    "D",[Char]
    "E",[Char]
    "F"])
                    [(Node
    1,Node
    4,Node
    3),(Node
    2,Node
    3,Node
    3),(Node
    2,Node
    4,Node
    3),(Node
    4,Node
    2,Node
    4),(Node
    4,Node
    6,Node
    2),
                     (Node
    5,Node
    2,Node
    5),(Node
    5,Node
    3,Node
    6),(Node
    5,Node
    7,Node
    5),(Node
    5,Node
    8,Node
    6),
                     (Node
    6,Node
    5,Node
    3),(Node
    6,Node
    7,Node
    2),(Node
    7,Node
    8,Node
    3),(Node
    8,Node
    7,Node
    3)]