{- | Lcf (Lederberg/Coxeter/Frucht) notation

The notation only applies to Hamiltonian graphs, since it achieves its
symmetry and conciseness by placing a Hamiltonian cycle in a circular
embedding and then connecting specified pairs of nodes with edges. (EW)

-}
module Music.Theory.Graph.Lcf where

import Data.Complex {- base -}
import Data.List {- base -}

import qualified Music.Theory.Graph.Type as T {- hmt-base -}

-- | Lcf notation (/l/,/k/). ([3,-3],4) is the cubical graph.
type Lcf = ([Int],Int)

-- | Real, alias for 'Double'
type R = Double

-- | Sequence, ie. /l/ /k/ times.
lcf_seq :: Lcf -> [Int]
lcf_seq :: Lcf -> [Int]
lcf_seq ([Int]
l,Int
k) = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat (forall a. Int -> a -> [a]
replicate Int
k [Int]
l)

-- | Length of 'lcf_seq', ie. |l|k
lcf_degree :: Lcf -> Int
lcf_degree :: Lcf -> Int
lcf_degree ([Int]
l,Int
k) = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
l forall a. Num a => a -> a -> a
* Int
k

-- | 'Lcf' to 'T.Edg' (an edge list)
lcf_to_edg :: Lcf -> T.Edg
lcf_to_edg :: Lcf -> Edg
lcf_to_edg ([Int]
l,Int
k) =
  let v_n :: Int
v_n = forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
l forall a. Num a => a -> a -> a
* Int
k
      add :: Int -> Int -> Int
add Int
i Int
j = (Int
i forall a. Num a => a -> a -> a
+ Int
j) forall a. Integral a => a -> a -> a
`mod` Int
v_n
      v :: [Int]
v = [Int
0 .. Int
v_n forall a. Num a => a -> a -> a
- Int
1]
  in ((Int
v_n,Int
v_n forall a. Num a => a -> a -> a
+ (Int
v_n forall a. Integral a => a -> a -> a
`div` Int
2))
     ,forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[(Int
i,Int
i Int -> Int -> Int
`add` Int
1) | Int
i <- [Int]
v]
             ,forall a. Eq a => [a] -> [a]
nub (forall a. Ord a => [a] -> [a]
sort (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (forall a b c. ((a, b) -> c) -> a -> b -> c
curry forall t. Ord t => (t, t) -> (t, t)
T.e_sort) [Int]
v (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> Int -> Int
add [Int]
v (Lcf -> [Int]
lcf_seq ([Int]
l,Int
k)))))])

-- | Lcf edge-list to graph labeled with circular co-ordinates.
edg_circ_gr :: R -> T.Edg -> T.Lbl (R,R) ()
edg_circ_gr :: R -> Edg -> Lbl (R, R) ()
edg_circ_gr R
rad ((Int
n,Int
_),[(Int, Int)]
e) =
  let polar_to_rectangular :: (b, b) -> (b, b)
polar_to_rectangular (b
mg,b
ph) = let c :: Complex b
c = forall a. Floating a => a -> a -> Complex a
mkPolar b
mg b
ph in (forall a. Complex a -> a
realPart Complex b
c,forall a. Complex a -> a
imagPart Complex b
c)
      ph_incr :: R
ph_incr = (R
2 forall a. Num a => a -> a -> a
* forall a. Floating a => a
pi) forall a. Fractional a => a -> a -> a
/ forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n
      v :: [(Int, (R, R))]
v = forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0 .. Int
n forall a. Num a => a -> a -> a
- Int
1] (forall a b. (a -> b) -> [a] -> [b]
map (forall a b c. ((a, b) -> c) -> a -> b -> c
curry forall {b}. Floating b => (b, b) -> (b, b)
polar_to_rectangular R
rad) [R
0, R
ph_incr ..])
  in ([(Int, (R, R))]
v,forall a b. [a] -> [b] -> [(a, b)]
zip [(Int, Int)]
e (forall a. a -> [a]
repeat ()))

{- | Lcf graph set given at <http://mathworld.wolfram.com/LcfNotation.html>

> length lcf_mw_set == 57
> length (nub (map snd lcf_mw_set)) == 57 -- IE. UNIQ
-}
lcf_mw_set :: [(String, Lcf)]
lcf_mw_set :: [(String, Lcf)]
lcf_mw_set =
  [(String
"Tetrahedral graph",([Int
2,-Int
2],Int
2)) -- ([2],4)
  ,(String
"Utility graph",([Int
3],Int
6)) -- ([3,-3],3)
  ,(String
"3-prism graph",([-Int
3,-Int
2,Int
2],Int
2))
  ,(String
"Cubical graph",([Int
3,-Int
3],Int
4))
  ,(String
"Wagner graph",([Int
4],Int
8))
  ,(String
"3-matchstick graph",([-Int
2,-Int
2,Int
2,Int
2],Int
2))
  ,(String
"4-Möbius ladder",([-Int
4],Int
8))
  ,(String
"5-Möbius ladder",([-Int
5],Int
10))
  ,(String
"5-prism graph",([-Int
5,Int
3,-Int
4,Int
4,-Int
3],Int
2))
  ,(String
"Bidiakis cube",([Int
6,Int
4,-Int
4],Int
4))
  ,(String
"Franklin graph",([Int
5,-Int
5],Int
6))
  ,(String
"Frucht graph",([-Int
5,-Int
2,-Int
4,Int
2,Int
5,-Int
2,Int
2,Int
5,-Int
2,-Int
5,Int
4,Int
2],Int
1))
  ,(String
"Truncated tetrahedral graph",([Int
2,Int
6,-Int
2],Int
4))
  ,(String
"Generalized Petersen graph (6,2)",([-Int
5,Int
2,Int
4,-Int
2,-Int
5,Int
4,-Int
4,Int
5,Int
2,-Int
4,-Int
2,Int
5],Int
1))
  ,(String
"6-Möbius ladder",([-Int
6],Int
12))
  ,(String
"6-prism graph",([-Int
3,Int
3],Int
6))
  ,(String
"Heawood graph",([Int
5,-Int
5],Int
7))
  ,(String
"Generalized Petersen graph (7,2)",([-Int
7,-Int
5,Int
4,-Int
6,-Int
5,Int
4,-Int
4,-Int
7,Int
4,-Int
4,Int
5,Int
6,-Int
4,Int
5],Int
1))
  ,(String
"7-Möbius ladder",([-Int
7],Int
14))
  ,(String
"7-prism graph",([-Int
7,Int
5,Int
3,-Int
6,Int
6,-Int
3,-Int
5],Int
2))
  ,(String
"Cubic vertex-transitive graph Ct19",([-Int
7,Int
7],Int
8))
  ,(String
"Möbius-Kantor graph",([Int
5,-Int
5],Int
8))
  ,(String
"8-Möbius ladder",([-Int
8],Int
16))
  ,(String
"8-prism graph",([-Int
3,Int
3],Int
8))
  ,(String
"Pappus graph",([Int
5,Int
7,-Int
7,Int
7,-Int
7,-Int
5],Int
3))
  ,(String
"Cubic vertex-transitive graph Ct20",([-Int
7,Int
7],Int
9)) -- ([5,-5],9)
  ,(String
"Cubic vertex-transitive graph Ct23",([-Int
9,-Int
2,Int
2],Int
6))
  ,(String
"Generalized Petersen graph (9,2)",([-Int
9,-Int
8,-Int
4,-Int
9,Int
4,Int
8],Int
3))
  ,(String
"Generalized Petersen graph (9,3)",([-Int
9,-Int
6,Int
2,Int
5,-Int
2,-Int
9,Int
5,-Int
9,-Int
5,-Int
9,Int
2,-Int
5,-Int
2,Int
6,-Int
9,Int
2,-Int
9,-Int
2],Int
1))
  ,(String
"9-Möbius ladder",([-Int
9],Int
18))
  ,(String
"9-prism graph",([-Int
9,Int
7,Int
5,Int
3,-Int
8,Int
8,-Int
3,-Int
5,-Int
7],Int
2))
  ,(String
"Desargues graph",([Int
5,-Int
5,Int
9,-Int
9],Int
5))
  ,(String
"Dodecahedral graph",([Int
10,Int
7,Int
4,-Int
4,-Int
7,Int
10,-Int
4,Int
7,-Int
7,Int
4],Int
2))
  ,(String
"Cubic vertex-transitive graph Ct25",([-Int
7,Int
7],Int
10))
  ,(String
"Cubic vertex-transitive graph Ct28",([-Int
6,-Int
6,Int
6,Int
6],Int
5))
  ,(String
"Cubic vertex-transitive graph Ct29",([-Int
9,Int
9],Int
10))
  ,(String
"Generalized Petersen graph (10,4)",([-Int
10,-Int
7,Int
5,-Int
5,Int
7,-Int
6,-Int
10,-Int
5,Int
5,Int
6],Int
2))
  ,(String
"Largest cubic nonplanar graph with diameter 3",([-Int
10,-Int
7,-Int
5,Int
4,Int
7,-Int
10,-Int
7,-Int
4,Int
5,Int
7,-Int
10,-Int
7,Int
6,-Int
5,Int
7,-Int
10,-Int
7,Int
5,-Int
6,Int
7],Int
1))
  ,(String
"10-Möbius ladder",([-Int
10],Int
20))
  ,(String
"10-prism graph",([-Int
3,Int
3],Int
10))
  ,(String
"McGee graph",([Int
12,Int
7,-Int
7],Int
8))
  ,(String
"Truncated cubical graph",([Int
2,Int
9,-Int
2,Int
2,-Int
9,-Int
2],Int
4))
  ,(String
"Truncated octahedral graph",([Int
3,-Int
7,Int
7,-Int
3],Int
6))
  ,(String
"Nauru graph",([Int
5,-Int
9,Int
7,-Int
7,Int
9,-Int
5],Int
4))
  ,(String
"F26A graph",([-Int
7,Int
7],Int
13))
  ,(String
"Tutte-Coxeter graph",([-Int
13,-Int
9,Int
7,-Int
7,Int
9,Int
13],Int
5))
  ,(String
"Dyck graph",([Int
5,-Int
5,Int
13,-Int
13],Int
8))
  ,(String
"Gray graph",([-Int
25,Int
7,-Int
7,Int
13,-Int
13,Int
25],Int
9))
  ,(String
"Truncated dodecahedral graph",([Int
30,-Int
2,Int
2,Int
21,-Int
2,Int
2,Int
12,-Int
2,Int
2,-Int
12,-Int
2,Int
2,-Int
21,-Int
2,Int
2,Int
30,-Int
2,Int
2,-Int
12,-Int
2,Int
2,Int
21,-Int
2,Int
2,-Int
21,-Int
2,Int
2,Int
12,-Int
2,Int
2],Int
2))
  ,(String
"Harries graph",([-Int
29,-Int
19,-Int
13,Int
13,Int
21,-Int
27,Int
27,Int
33,-Int
13,Int
13,Int
19,-Int
21,-Int
33,Int
29],Int
5))
  ,(String
"Harries-Wong graph",([Int
9,Int
25,Int
31,-Int
17,Int
17,Int
33,Int
9,-Int
29,-Int
15,-Int
9,Int
9,Int
25,-Int
25,Int
29,Int
17,-Int
9,Int
9,-Int
27,Int
35,-Int
9,Int
9,-Int
17,Int
21,Int
27,-Int
29,-Int
9,-Int
25,Int
13,Int
19,-Int
9,-Int
33,-Int
17,Int
19,-Int
31,Int
27,Int
11,-Int
25,Int
29,-Int
33,Int
13,-Int
13,Int
21,-Int
29,-Int
21,Int
25,Int
9,-Int
11,-Int
19,Int
29,Int
9,-Int
27,-Int
19,-Int
13,-Int
35,-Int
9,Int
9,Int
17,Int
25,-Int
9,Int
9,Int
27,-Int
27,-Int
21,Int
15,-Int
9,Int
29,-Int
29,Int
33,-Int
9,-Int
25],Int
1))
  ,(String
"Balaban 10-cage",([-Int
9,-Int
25,-Int
19,Int
29,Int
13,Int
35,-Int
13,-Int
29,Int
19,Int
25,Int
9,-Int
29,Int
29,Int
17,Int
33,Int
21,Int
9,-Int
13,-Int
31,-Int
9,Int
25,Int
17,Int
9,-Int
31,Int
27,-Int
9,Int
17,-Int
19,-Int
29,Int
27,-Int
17,-Int
9,-Int
29,Int
33,-Int
25,Int
25,-Int
21,Int
17,-Int
17,Int
29,Int
35,-Int
29,Int
17,-Int
17,Int
21,-Int
25,Int
25,-Int
33,Int
29,Int
9,Int
17,-Int
27,Int
29,Int
19,-Int
17,Int
9,-Int
27,Int
31,-Int
9,-Int
17,-Int
25,Int
9,Int
31,Int
13,-Int
9,-Int
21,-Int
33,-Int
17,-Int
29,Int
29],Int
1))
  ,(String
"Foster graph",([Int
17,-Int
9,Int
37,-Int
37,Int
9,-Int
17],Int
15))
  ,(String
"Biggs-Smith graph",([Int
16,Int
24,-Int
38,Int
17,Int
34,Int
48,-Int
19,Int
41,-Int
35,Int
47,-Int
20,Int
34,-Int
36,Int
21,Int
14,Int
48,-Int
16,-Int
36,-Int
43,Int
28,-Int
17,Int
21,Int
29,-Int
43,Int
46,-Int
24,Int
28,-Int
38,-Int
14,-Int
50,-Int
45,Int
21,Int
8,Int
27,-Int
21,Int
20,-Int
37,Int
39,-Int
34,-Int
44,-Int
8,Int
38,-Int
21,Int
25,Int
15,-Int
34,Int
18,-Int
28,-Int
41,Int
36,Int
8,-Int
29,-Int
21,-Int
48,-Int
28,-Int
20,-Int
47,Int
14,-Int
8,-Int
15,-Int
27,Int
38,Int
24,-Int
48,-Int
18,Int
25,Int
38,Int
31,-Int
25,Int
24,-Int
46,-Int
14,Int
28,Int
11,Int
21,Int
35,-Int
39,Int
43,Int
36,-Int
38,Int
14,Int
50,Int
43,Int
36,-Int
11,-Int
36,-Int
24,Int
45,Int
8,Int
19,-Int
25,Int
38,Int
20,-Int
24,-Int
14,-Int
21,-Int
8,Int
44,-Int
31,-Int
38,-Int
28,Int
37],Int
1))
  ,(String
"Balaban 11-cage",([Int
44,Int
26,-Int
47,-Int
15,Int
35,-Int
39,Int
11,-Int
27,Int
38,-Int
37,Int
43,Int
14,Int
28,Int
51,-Int
29,-Int
16,Int
41,-Int
11,-Int
26,Int
15,Int
22,-Int
51,-Int
35,Int
36,Int
52,-Int
14,-Int
33,-Int
26,-Int
46,Int
52,Int
26,Int
16,Int
43,Int
33,-Int
15,Int
17,-Int
53,Int
23,-Int
42,-Int
35,-Int
28,Int
30,-Int
22,Int
45,-Int
44,Int
16,-Int
38,-Int
16,Int
50,-Int
55,Int
20,Int
28,-Int
17,-Int
43,Int
47,Int
34,-Int
26,-Int
41,Int
11,-Int
36,-Int
23,-Int
16,Int
41,Int
17,-Int
51,Int
26,-Int
33,Int
47,Int
17,-Int
11,-Int
20,-Int
30,Int
21,Int
29,Int
36,-Int
43,-Int
52,Int
10,Int
39,-Int
28,-Int
17,-Int
52,Int
51,Int
26,Int
37,-Int
17,Int
10,-Int
10,-Int
45,-Int
34,Int
17,-Int
26,Int
27,-Int
21,Int
46,Int
53,-Int
10,Int
29,-Int
50,Int
35,Int
15,-Int
47,-Int
29,-Int
41,Int
26,Int
33,Int
55,-Int
17,Int
42,-Int
26,-Int
36,Int
16],Int
1))
  ,(String
"Ljubljana graph",([Int
47,-Int
23,-Int
31,Int
39,Int
25,-Int
21,-Int
31,-Int
41,Int
25,Int
15,Int
29,-Int
41,-Int
19,Int
15,-Int
49,Int
33,Int
39,-Int
35,-Int
21,Int
17,-Int
33,Int
49,Int
41,Int
31,-Int
15,-Int
29,Int
41,Int
31,-Int
15,-Int
25,Int
21,Int
31,-Int
51,-Int
25,Int
23,Int
9,-Int
17,Int
51,Int
35,-Int
29,Int
21,-Int
51,-Int
39,Int
33,-Int
9,-Int
51,Int
51,-Int
47,-Int
33,Int
19,Int
51,-Int
21,Int
29,Int
21,-Int
31,-Int
39],Int
2))
  ,(String
"Tutte 12-cage",([Int
17,Int
27,-Int
13,-Int
59,-Int
35,Int
35,-Int
11,Int
13,-Int
53,Int
53,-Int
27,Int
21,Int
57,Int
11,-Int
21,-Int
57,Int
59,-Int
17],Int
7))]

-- Local Variables:
-- truncate-lines:t
-- End: