{-# 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 :: Int -> [UNode]
genUNodes Int
n = [Int] -> [()] -> [UNode]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
n] (() -> [()]
forall a. a -> [a]
repeat ())

-- | generate list of labeled nodes
genLNodes :: (Enum a) => a -> Int -> [LNode a]
genLNodes :: a -> Int -> [LNode a]
genLNodes a
q Int
i = Int -> [LNode a] -> [LNode a]
forall a. Int -> [a] -> [a]
take Int
i ([Int] -> [a] -> [LNode a]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
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 (\(Int
i,Int
j) -> (Int
i,Int
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    = ([],Int
1,Char
'a',[]) Context Char () -> Gr Char () -> Gr Char ()
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& Gr Char ()
forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty                  -- just a node
b :: Gr Char ()
b    = [LNode Char] -> [UEdge] -> Gr Char ()
forall (gr :: * -> * -> *) a b.
Graph gr =>
[LNode a] -> [LEdge b] -> gr a b
mkGraph ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
2] [Char]
"ab") [UEdge]
noEdges      -- just two nodes
c :: Gr Char ()
c    = [LNode Char] -> [UEdge] -> Gr Char ()
forall (gr :: * -> * -> *) a b.
Graph gr =>
[LNode a] -> [LEdge b] -> gr a b
mkGraph ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
3] [Char]
"abc") [UEdge]
noEdges     -- just three nodes
e :: Gr Char ()
e    = ([((),Int
1)],Int
2,Char
'b',[]) Context Char () -> Gr Char () -> Gr Char ()
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 (gr :: * -> * -> *) a b.
Graph gr =>
[LNode a] -> [LEdge b] -> gr a b
mkGraph (Int -> [UNode]
genUNodes Int
2)
       [(Int
1,Int
2,[Char]
"a"),(Int
1,Int
2,[Char]
"b"),(Int
1,Int
2,[Char]
"a")]        -- three edges (two labels) a-->b
loop :: Gr Char ()
loop = ([],Int
1,Char
'a',[((),Int
1)]) Context Char () -> Gr Char () -> Gr Char ()
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& Gr Char ()
forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty            -- loop on single node
ab :: Gr Char ()
ab   = ([((),Int
1)],Int
2,Char
'b',[((),Int
1)]) Context Char () -> Gr Char () -> Gr Char ()
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 (gr :: * -> * -> *) a b.
Graph gr =>
[LNode a] -> [LEdge b] -> gr a b
mkGraph ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
2] [Char]
"ab") ([Edge] -> [UEdge]
labUEdges [(Int
2,Int
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",Int
3)],Int
1,Char
'a',[([Char]
"ab",Int
2)]),
                ([],Int
2,Char
'b',[([Char]
"bc",Int
3)]),
                ([],Int
3,Char
'c',[])]

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

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

g3 :: Gr Char [Char]
g3 = ([([Char]
"left",Int
2),([Char]
"up",Int
3)],Int
1,Char
'a',[([Char]
"right",Int
2)]) Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& (
                        ([],Int
2,Char
'b',[([Char]
"down",Int
3)])  Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& (
                        ([],Int
3,Char
'c',[])            Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& Gr Char [Char]
forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty ))
g3b :: Gr Char [Char]
g3b = ([([Char]
"down",Int
2)], Int
3,Char
'c',[([Char]
"up",Int
1)])   Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& (
      ([([Char]
"right",Int
1)],Int
2,Char
'b',[([Char]
"left",Int
1)]) Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& (
                 ([],Int
1,Char
'a',[])           Context Char [Char] -> Gr Char [Char] -> Gr Char [Char]
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
Context a b -> gr a b -> gr a b
& Gr Char [Char]
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 (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM [(Int
1,Char
'a')] [UEdge]
noEdges              -- just a node
b' :: IO (SGr Char ())
b'    = [LNode Char] -> [UEdge] -> IO (SGr Char ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
2] [Char]
"ab") [UEdge]
noEdges      -- just two nodes
c' :: IO (SGr Char ())
c'    = [LNode Char] -> [UEdge] -> IO (SGr Char ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
3] [Char]
"abc") [UEdge]
noEdges     -- just three nodes
e' :: IO (SGr Char ())
e'    = [LNode Char] -> [UEdge] -> IO (SGr Char ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
2] [Char]
"ab") [(Int
1,Int
2,())]   -- just one edge a-->b
e3' :: IO (SGr () [Char])
e3'   = [UNode] -> [LEdge [Char]] -> IO (SGr () [Char])
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM (Int -> [UNode]
genUNodes Int
2)
          [(Int
1,Int
2,[Char]
"a"),(Int
1,Int
2,[Char]
"b"),(Int
1,Int
2,[Char]
"a")]       -- three edges (two labels) a-->b
loop' :: IO (SGr Char ())
loop' = [LNode Char] -> [UEdge] -> IO (SGr Char ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM [(Int
1,Char
'a')] [(Int
1,Int
1,())]           -- loop on single node
ab' :: IO (SGr Char ())
ab'   = [LNode Char] -> [UEdge] -> IO (SGr Char ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
2] [Char]
"ab")
          [(Int
1,Int
2,()),(Int
2,Int
1,())]                   -- cycle of two nodes:  a<-->b
abb' :: IO (SGr Char ())
abb'  = [LNode Char] -> [UEdge] -> IO (SGr Char ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM ([Int] -> [Char] -> [LNode Char]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
2] [Char]
"ab") ([Edge] -> [UEdge]
labUEdges [(Int
2,Int
2)]) -- a and loop on b

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

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

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

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

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

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

vor :: Gr [Char] Int
vor = [LNode [Char]] -> [LEdge Int] -> Gr [Char] Int
forall (gr :: * -> * -> *) a b.
Graph gr =>
[LNode a] -> [LEdge b] -> gr a b
mkGraph ([Int] -> [[Char]] -> [LNode [Char]]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
8] [[Char]
"A",[Char]
"B",[Char]
"C",[Char]
"H1",[Char]
"H2",[Char]
"D",[Char]
"E",[Char]
"F"])
              [(Int
1,Int
4,Int
3),(Int
2,Int
3,Int
3),(Int
2,Int
4,Int
3),(Int
4,Int
2,Int
4),(Int
4,Int
6,Int
2),
               (Int
5,Int
2,Int
5),(Int
5,Int
3,Int
6),(Int
5,Int
7,Int
5),(Int
5,Int
8,Int
6),
               (Int
6,Int
5,Int
3),(Int
6,Int
7,Int
2),(Int
7,Int
8,Int
3),(Int
8,Int
7,Int
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 (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM (Char -> Int -> [LNode Char]
forall a. Enum a => a -> Int -> [LNode a]
genLNodes Char
'u' Int
6)
          ([Edge] -> [UEdge]
labUEdges [(Int
1,Int
2),(Int
1,Int
4),(Int
2,Int
5),(Int
3,Int
5),(Int
3,Int
6),(Int
4,Int
2),(Int
5,Int
4),(Int
6,Int
6)])
clr486' :: IO (SGr [Char] ())
clr486' = [LNode [Char]] -> [UEdge] -> IO (SGr [Char] ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM ([Int] -> [[Char]] -> [LNode [Char]]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..Int
9] [[Char]
"shorts",[Char]
"socks",[Char]
"watch",[Char]
"pants",[Char]
"shoes",
                                [Char]
"shirt",[Char]
"belt",[Char]
"tie",[Char]
"jacket"])
                   ([Edge] -> [UEdge]
labUEdges [(Int
1,Int
4),(Int
1,Int
5),(Int
2,Int
5),(Int
4,Int
5),(Int
4,Int
7),(Int
6,Int
7),(Int
6,Int
8),(Int
7,Int
9),(Int
8,Int
9)])
clr489' :: IO (SGr Char ())
clr489' = [LNode Char] -> [UEdge] -> IO (SGr Char ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM (Char -> Int -> [LNode Char]
forall a. Enum a => a -> Int -> [LNode a]
genLNodes Char
'a' Int
8)
                   ([Edge] -> [UEdge]
labUEdges [(Int
1,Int
2),(Int
2,Int
3),(Int
2,Int
5),(Int
2,Int
6),(Int
3,Int
4),(Int
3,Int
7),(Int
4,Int
3),(Int
4,Int
8),
                           (Int
5,Int
1),(Int
5,Int
6),(Int
6,Int
7),(Int
7,Int
6),(Int
7,Int
8),(Int
8,Int
8)])
clr508' :: IO (SGr Char Int)
clr508' = [LNode Char] -> [LEdge Int] -> IO (SGr Char Int)
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM (Char -> Int -> [LNode Char]
forall a. Enum a => a -> Int -> [LNode a]
genLNodes Char
'a' Int
9)
                   [(Int
1,Int
2,Int
4),(Int
1,Int
8,Int
8),(Int
2,Int
3,Int
8),(Int
2,Int
8,Int
11),(Int
3,Int
4,Int
7),(Int
3,Int
6,Int
4),(Int
3,Int
9,Int
2),
                   (Int
4,Int
5,Int
9),(Int
4,Int
6,Int
14),(Int
5,Int
6,Int
10),(Int
6,Int
7,Int
2),(Int
7,Int
8,Int
1),(Int
7,Int
9,Int
6),(Int
8,Int
9,Int
7)]
clr528' :: IO (SGr Char Int)
clr528' = [LNode Char] -> [LEdge Int] -> IO (SGr Char Int)
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM [(Int
1,Char
's'),(Int
2,Char
'u'),(Int
3,Char
'v'),(Int
4,Char
'x'),(Int
5,Char
'y')]
                   [(Int
1,Int
2,Int
10),(Int
1,Int
4,Int
5),(Int
2,Int
3,Int
1),(Int
2,Int
4,Int
2),(Int
3,Int
5,Int
4),
                    (Int
4,Int
2,Int
3),(Int
4,Int
3,Int
9),(Int
4,Int
5,Int
2),(Int
5,Int
1,Int
7),(Int
5,Int
3,Int
6)]
kin248' :: IO (SGr Int ())
kin248' = [Edge] -> [UEdge] -> IO (SGr Int ())
forall (m :: * -> *) (gr :: * -> * -> *) a b.
GraphM m gr =>
[LNode a] -> [LEdge b] -> m (gr a b)
mkGraphM (Int -> Int -> [Edge]
forall a. Enum a => a -> Int -> [LNode a]
genLNodes Int
1 Int
10)
                   ([Edge] -> [UEdge]
labUEdges [(Int
1,Int
2),(Int
1,Int
4),(Int
1,Int
7),(Int
2,Int
4),(Int
2,Int
5),(Int
3,Int
4),(Int
3,Int
10),
                           (Int
4,Int
5),(Int
4,Int
8),(Int
5,Int
2),(Int
5,Int
3),(Int
6,Int
7),(Int
7,Int
6),(Int
7,Int
8),
                           (Int
8,Int
10),(Int
9,Int
9),(Int
9,Int
10),(Int
10,Int
8),(Int
10,Int
9)])
         -- this is the inverse graph shown on the bottom of the page

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