グラフ理論

• まずは、ブログの最初にある、k次元超立方グラフ(こちら)

module Main (main) where
import Math.Combinatorics.Graph
main = print $ q 2

• • Gのあとに、二つのリストがあって、第一のリストはベクトル型、第二のリストは、長さ２のベクトルのリスト。第一のリストはノードのリスト、第二のリストはノードペア＝エッジのリスト

G [0,1,2,3] [[0,1],[0,2],[1,3],[2,3]]

• これがどうなっているか、と見ると、qという関数の背後にq'という関数があり、それは、k次元の[0,1]の総当たりをしつつ、隣接ノードにだけエッジを発生させている
• その上で、q'が利用したノードが「座標」だったので、それをノードIDに変換するために、二進法を使っている

>||haskell|

• • |q k is the graph of the k-cube

q :: (Integral t) => Int -> Graph t
q k = fromBinary $ q' k

q' :: (Integral t) => Int -> Graph [t]
q' k = graph (vs,es) where
vs = sequence $ replicate k [0,1] -- ptsAn k f2
es = [ [u,v] | [u,v] <- combinationsOf 2 vs, hammingDistance u v == 1 ]
hammingDistance as bs = length $ filter id $ zipWith (/=) as bs

• • can probably type-coerce this to be Graph [F2] if required

|