semigroups_iso

README.txt

=== Запуск ===
Чтобы запустить программу выполните файл main.exe
Когда программа закончит работу нажмите <Enter> чтобы выйти.

=== Описание ===
Программа для проверки полурешеток на изоморфизм. 

=== Вход ===
Входные данные: фалй input.txt содержаший две таблицы для полурешеток.
Элементами полуршеток должны являтся числа 0, 1, ..., n-1, где
n -- это порядок полурешетки.
Пример входных данных:

0 0 0
0 1 0
0 0 2

0 0 0
0 1 1
0 1 2

Примечание: оформление ввода не важно, т.к. программа ожидает 
любой файл с 2*n^2 числами. Например, предыдущий пример можно 
оформить и так:

0 0 0 0 1 0 0 0 2
0 0 0 0 1 1 0 1 2

=== Выход ===
На выходе программа дает информацию о деревьях, построенных
на основе введённых полурешеток: рисует структуру дерева и 
код дерева. В последней строке указывается результат проверки 
на изоморфизм.

Пример вывода (для предыдущего примера):

=== Tree of semigroup 1 ===
0
|
+- 1
|
`- 2
Encode Tree: "001011"
=== Tree of semigroup 2 ===
0
|
`- 1
   |
   `- 2
Encode Tree: "000111"
----------
False

input.txt

0 0 0
0 1 0
0 0 2

0 0 0
0 1 1
0 1 2

semigroups_iso.hs

import System.IO  
import Control.Monad
import Data.Tree
import Data.List
import System.Environment

encodeTree (Node root []) = "01"
encodeTree (Node root childs) = "0" ++ intercalate "" (sort $ map encodeTree childs) ++ "1"
isIsomorphic t1 t2 = encodeTree t1 == encodeTree t2

op m [x] = x
op m (x:y:xs) = op m $ (m !! x !! y):xs
am m = [0, 1..length m - 1]
f m x y z = and [z /= x, z /= y, op m [z, y] == z, op m [x, z] == x]
isNext m x y = and [x /= y, op m [x, y] == x, not $ any (f m x y) (am m)]
nexts m x = filter (isNext m x) (am m)
lowerElement m = op m $ am m
goStoT m x = [Node v (goStoT m v) | v <- nexts m x]
semigroupToTree m = Node le (goStoT m le) where le = lowerElement m

isSemiIso s1 s2 = isIsomorphic (semigroupToTree s1) (semigroupToTree s2) 

nums = map read
ca a n = if length a <= n then [take n a] else [take n a] ++ (ca (drop n a) n)

g (Node x []) = Node (show x) []
g (Node x a) = Node (show x) (map g a)

main = do  
  handle <- openFile "input.txt" ReadMode
  contents <- hGetContents handle
  let arr = nums (words contents)
      n = length arr
      half_n = div n 2
      sqrt_half_n = round $ sqrt (fromIntegral half_n :: Double)
      t = ca arr half_n
      ss = [ca (t !! 0) sqrt_half_n, ca (t !! 1) sqrt_half_n]
      t1 = semigroupToTree (ss !! 0)
      t2 = semigroupToTree (ss !! 1)
      ct1 = encodeTree t1
      ct2 = encodeTree t2
  args <- getArgs
  if length args > 0 then do {
    putStr "=== Tree of semigroup 1 ===\n";
    putStr . drawTree $ g t1;
    putStr "Encode Tree: ";
    print ct1;
    putStr "=== Tree of semigroup 2 ===\n";
    putStr . drawTree $ g t2;
    putStr "Encode Tree: ";
    print ct2;
    putStr "----------\n";
    print $ ct1 == ct2
  } else do {
    print $ ct1 == ct2
  }
  getLine