OKlibrary  0.2.1.6
Homomorphisms.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 25.6.2008 (Swansea) */
00002 /* Copyright 2008, 2010 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00024 
00025 
00026 /* A "homomorphisms" between graphs (with loops) is a map between the vertex
00027    sets which preserves the edges.
00028 */
00029 
00030 /* ***************************
00031    * Checking the properties *
00032    ***************************
00033 */
00034 
00035 full_homomorphism_gl_p(G1,G2,f) := subsetp(map(f,G1[1]),G2[1]) and
00036   homomorphism_gl_p(G1,G2,f)$
00037 
00038 /* Assumes that f(G1[1]) <= G2[1] holds: */
00039 homomorphism_gl_p(G1,G2,f) := every_s(
00040   lambda([e],elementp(map(f,e),G2[2])), G1[2])$
00041 /* Remark: For covered vertices in G1 the inclusion condition is implicitely
00042    checked by this condition.
00043 */
00044 
00045 full_isomorphism_gl_p(G1,G2,f) := is(map(f,G1[1]) = G2[1]) and 
00046   is(length(G1[2]) = length(G2[2])) and homomorphism_gl_p(G1,G2,f)$
00047 
00048 
00049 /* ****************************
00050    * Brute-force enumerations *
00051    ****************************
00052 */
00053 
00054 /* Computing the list of all automorphisms of a graph (with loops), assuming
00055    that the vertex set is {1, ..., n}: */
00056 monitor_all_isomorphisms_bydef_stgl() := 
00057   if oklib_monitor then 
00058     print("[all_isomorphisms_bydef_stgl]: no. ", length(res), ", ", p)$
00059 all_isomorphisms_bydef_stgl(G) := block([res : [], n : length(G[1])],
00060   for p in permutations(G[1]) do block(
00061    [a : il2array(p), h],
00062     h : lambda_array(a),
00063     if homomorphism_gl_p(G,G,h) then (
00064       res : endcons(h,res),
00065       monitor_all_isomorphisms_bydef_stgl()
00066   )),
00067   return(res))$
00068 /* Computing the "usual" list of isomorphisms, ordered lexicographically: */
00069 all_pisomorphisms_bydef_stgl(G) := 
00070   map(extract_arraylist,all_isomorphisms_bydef_stgl(G))$
00071