Music.Theory.Graph.Type

Graph types.

Vertices

v_is_normal :: [Int] -> Maybe Int

v_is_normal_err :: [Int] -> Int

Edge

e_eq_undir :: Eq t => (t, t) -> (t, t) -> Bool

Un-directed edge equality.

e_eq_undir (0,1) (1,0) == True

e_sort :: Ord t => (t, t) -> (t, t)

Sort edge.

map e_sort [(0,1),(1,0)] == [(0,1),(0,1)]

(vertices,edges) graph

type Gr t = ([t], [(t, t)])

(vertices,edges)

gr_map :: (t -> u) -> Gr t -> Gr u

Gr is a functor.

gr_degree :: Gr t -> (Int, Int)

(|V|,|E|)

gr_relabel :: Eq t => [(t, u)] -> Gr t -> Gr u

Re-label graph given table.

gr_mk_undir :: Ord t => Gr t -> Gr t

If (i,j) and (j,i) are both in E delete (j,i) where i < j.

eset_to_gr :: Ord t => [(t, t)] -> Gr t

List of E to G, derives V from E.

gr_sort :: Ord t => Gr t -> Gr t

Sort v and e.

gr_complete_graph :: Ord t => [t] -> Gr t

Complete k-graph (un-directed) given list of vertices

gr_complete_graph "xyz" == ("xyz",[('x','y'),('x','z'),('y','z')])

Int graph

type G = Gr Int

Gr of Int

g_to_text :: G -> String

Simple text representation of G. Requires (and checks) that vertices are (0 .. |v|-1). The first line is the number of vertices, following lines are edges.

graph_to_g :: Graph -> G

Graph to G.

g_to_graph :: G -> Graph

G to Graph

g = ([0,1,2],[(0,1),(0,2),(1,2)])
g == gr_sort (graph_to_g (g_to_graph g))

gr_unlabel :: Eq t => Gr t -> (G, [(Int, t)])

Unlabel graph, make table.

gr_unlabel ("xyz",[('x','y'),('x','z')]) == (([0,1,2],[(0,1),(0,2)]),[(0,'x'),(1,'y'),(2,'z')])

gr_to_g :: Eq t => Gr t -> G

fst of gr_unlabel

gr_to_graph :: Eq t => Gr t -> (Graph, [(Int, t)])

g_to_graph of gr_unlabel.

gr = ("abc",[('a','b'),('a','c'),('b','c')])
(g,tbl) = gr_to_graph gr

g_complete_graph :: Int -> G

Complete k-graph (un-directed).

g_complete_graph 3 == ([0,1,2],[(0,1),(0,2),(1,2)])

Edg = edge list (zero-indexed)

type Edg = ((Int, Int), [(Int, Int)])

((|V|,|E|),[E])

g_to_edg :: G -> Edg

Requires (and checks) that vertices are (0 .. |v| - 1).

edg_to_g :: Edg -> G

Requires (but does not check) that vertices of Edg are all in (0,|v| - 1).

edg_parse :: [String] -> Edg

Parse Edg as printed by nauty-listg.

Adjacencies

type Adj t = [(t, [t])]

Adjacency list [(left-hand-side,[right-hand-side])]

adj_to_eset :: Ord t => Adj t -> [(t, t)]

Adj to edge set.

adj_to_gr :: Ord t => Adj t -> Gr t

Adj to Gr

gr_to_adj :: Ord t => (t -> (t, t) -> Maybe t) -> Gr t -> Adj t

Gr to Adj (selection-function)

gr_to_adj_dir :: Ord t => Gr t -> Adj t

Gr to Adj (directed)

g = ([0,1,2,3],[(0,1),(2,1),(0,3),(3,0)])
r = [(0,[1,3]),(2,[1]),(3,[0])]
gr_to_adj_dir g == r

gr_to_adj_undir :: Ord t => Gr t -> Adj t

Gr to Adj (un-directed)

g = ([0,1,2,3],[(0,1),(2,1),(0,3),(3,0)])
gr_to_adj_undir g == [(0,[1,3,3]),(1,[2])]

type Adj_Mtx t = (Int, [[t]])

Adjacency matrix, (|v|,mtx)

edg_to_adj_mtx_undir :: (t, t) -> Edg -> Adj_Mtx t

Edg to Adj_Mtx for un-directed graph.

e = ((4,3),[(0,3),(1,3),(2,3)])
edg_to_adj_mtx_undir (0,1) e == (4,[[0,0,0,1],[0,0,0,1],[0,0,0,1],[1,1,1,0]])

e = ((4,4),[(0,1),(0,3),(1,2),(2,3)])
edg_to_adj_mtx_undir (0,1) e == (4,[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]])

g_to_adj_mtx_undir :: (t, t) -> G -> Adj_Mtx t

edg_to_adj_mtx_undir of g_to_edg

adj_mtx_con :: Eq t => (t, t) -> Adj_Mtx t -> Int -> [Int]

Lookup Adj_Mtx to find connected vertices.

Labels

type Lbl_Gr v v_lbl e_lbl = ([(v, v_lbl)], [((v, v), e_lbl)])

Labelled graph, distinct vertex and edge labels.

type Lbl v e = Lbl_Gr Int v e

Lbl_Gr of Int

type Lbl_ v = Lbl v ()

Lbl with () edge labels.

lbl_degree :: Lbl v e -> (Int, Int)

Number of vertices and edges.

lbl_bimap :: (v -> v') -> (e -> e') -> Lbl v e -> Lbl v' e'

Apply v at vertex labels and e at edge labels.

lbl_merge :: Lbl v e -> Lbl v e -> Lbl v e

Merge two Lbl graphs, do not share vertices, vertex indices at g1 are stable.

lbl_merge_seq :: [Lbl v e] -> Lbl v e

foldl1 of lbl_merge

lbl_canonical :: (Eq v, Ord v) => Lbl v e -> Lbl v e

Re-write graph so vertex indices are (0 .. n-1) and vertex labels are unique.

lbl_undir :: Lbl v e -> Lbl v e

Re-write edges so that vertex indices are ascending.

lbl_path_graph :: [x] -> Lbl_ x

Lbl path graph.

lbl_complete_graph :: [x] -> Lbl_ x

Lbl complete graph (undirected, no self-edges)

v_label :: v -> Lbl v e -> Int -> v

Lookup vertex label with default value.

v_label_err :: Lbl v e -> Int -> v

v_label with error as default.

e_label :: e -> Lbl v e -> (Int, Int) -> e

Lookup edge label with default value.

e_label_err :: Lbl v e -> (Int, Int) -> e

e_label with error as default.

lbl_gr_to_lbl :: Eq v => Lbl_Gr v v_lbl e_lbl -> Lbl v_lbl e_lbl

Convert from Lbl_Gr to Lbl

gr_to_lbl :: Eq t => Gr t -> Lbl t (t, t)

Convert from Gr to Lbl.

gr_to_lbl ("ab",[('a','b')]) == ([(0,'a'),(1,'b')],[((0,1),('a','b'))])

lbl_delete_edge_labels :: Lbl v e -> Lbl_ v

Delete edge labels from Lbl, replacing with ()

gr_to_lbl_ :: Eq t => Gr t -> Lbl_ t

lbl_delete_edge_labels of gr_to_lbl

eset_to_lbl :: Ord t => [(t, t)] -> Lbl_ t

Construct Lbl from set of E, derives V from E.

lbl_to_g :: Lbl v e -> G

Unlabel Lbl graph.