{-# 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)]