OKlibrary  0.2.1.6
ReingoldTilford.mac
Go to the documentation of this file.
00001 /* Rui Wang, 6.10.2009 (Swansea) */
00002 /* Copyright 2009 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/TestSystem/Lisp/Asserts.mac")$
00023 
00024 kill(f)$
00025 
00026 
00027 /* ******************************
00028    * Reingold-Tilford algorithm *
00029    ******************************
00030 */
00031 
00032 okltest_reingold_tilford_rt(f) := block([x,y],
00033   assert(f([],[x,y]) = [[[x,y]]]),
00034   assert(f([[]],[0,0]) = [[[0,0]],[[[0,-1]]]]),
00035   assert(f([[],[]],[0,0]) = [[[0,0]],[[[-1,-1]]],[[[1,-1]]]]),
00036   assert(f([[[]],[[]]],[0,0]) = [[[0,0]],[[[-1,-1]],[[[-1,-2]]]],[[[1,-1]],[[[1,-2]]]]]),
00037   assert(f([[[],[]],[[]]],[0,0]) = [[[0,0]],[[[-1,-1]],[[[-2,-2]]],[[[0,-2]]]],[[[1,-1]],[[[1,-2]]]]]),
00038   assert(f([[[],[]],[[],[]]],[0,0]) = [[[0,0]],[[[-2,-1]],[[[-3,-2]]],[[[-1,-2]]]],[[[2,-1]],[[[1,-2]]],[[[3,-2]]]]]),
00039   assert(f([[]],[4,5]) = [[[4,5]],[[[4,4]]]]),
00040   assert(f([[],[]],[4,5]) = [[[4,5]],[[[3,4]]],[[[5,4]]]]),
00041   assert(f([[[]],[[]]],[4,5]) = [[[4,5]],[[[3,4]],[[[3,3]]]],[[[5,4]],[[[5,3]]]]]),
00042   assert(f([[[],[]],[[]]],[4,5]) = [[[4,5]],[[[3,4]],[[[2,3]]],[[[4,3]]]],[[[5,4]],[[[5,3]]]]]),
00043   assert(f([[[],[]],[[],[]]],[4,5]) = [[[4,5]],[[[2,4]],[[[1,3]]],[[[3,3]]]],[[[6,4]],[[[5,3]]],[[[7,3]]]]]),
00044   true)$
00045 
00046 okltest_reingold_tilford_remove_annotations(f) := block([x,y],
00047   assert(f([[[x,y],[x,x]]]) = [[[x,y]]]),
00048   assert(f([[[0,0],[0,0]],[[[0,-1],[0,0]]]]) = [[[0,0]],[[[0,-1]]]]),
00049   assert(f([[[0,0],[-1,1]],[[[-1,-1],[0,0]]],[[[1,-1],[0,0]]]]) = [[[0,0]],[[[-1,-1]]],[[[1,-1]]]]),
00050   assert(f([[[0,0],[-1,1]],[[[-1,-1],[0,0]],[[[-1,-2],[0,0]]]],[[[1,-1],[0,0]],[[[1,-2],[0,0]]]]]) = [[[0,0]],[[[-1,-1]],[[[-1,-2]]]],[[[1,-1]],[[[1,-2]]]]]),
00051   assert(f([[[0,0],[-2,1]],[[[-1,-1],[-1,1]],[[[-2,-2],[0,0]]],[[[0,-2],[0,0]]]],[[[1,-1],[0,0]],[[[1,-2],[0,0]]]]]) = [[[0,0]],[[[-1,-1]],[[[-2,-2]]],[[[0,-2]]]],[[[1,-1]],[[[1,-2]]]]]),
00052   assert(f([[[0,0],[-3,3]],[[[-2,-1],[-1,1]],[[[-3,-2],[0,0]]],[[[-1,-2],[0,0]]]],[[[2,-1],[-1,1]],[[[1,-2],[0,0]]],[[[3,-2],[0,0]]]]]) = [[[0,0]],[[[-2,-1]],[[[-3,-2]]],[[[-1,-2]]]],[[[2,-1]],[[[1,-2]]],[[[3,-2]]]]]),
00053   true)$
00054  
00055 okltest_reingold_tilford_annotated(f) := block([x,y],
00056   assert(f([],[x,y]) = [[[x,y],[x,x]]]),
00057   assert(f([[]],[0,0]) = [[[0,0],[0,0]],[[[0,-1],[0,0]]]]),
00058   assert(f([[],[]],[0,0]) = [[[0,0],[-1,1]],[[[-1,-1],[0,0]]],[[[1,-1],[0,0]]]]),
00059   assert(f([[[]],[[]]],[0,0]) = [[[0,0],[-1,1]],[[[-1,-1],[0,0]],[[[-1,-2],[0,0]]]],[[[1,-1],[0,0]],[[[1,-2],[0,0]]]]]),
00060   assert(f([[[],[]],[[]]],[0,0]) = [[[0,0],[-2,1]],[[[-1,-1],[-1,1]],[[[-2,-2],[0,0]]],[[[0,-2],[0,0]]]],[[[1,-1],[0,0]],[[[1,-2],[0,0]]]]]),
00061   assert(f([[[],[]],[[],[]]],[0,0]) = [[[0,0],[-3,3]],[[[-2,-1],[-1,1]],[[[-3,-2],[0,0]]],[[[-1,-2],[0,0]]]],[[[2,-1],[-1,1]],[[[1,-2],[0,0]]],[[[3,-2],[0,0]]]]]),    
00062   true)$
00063 
00064