OKlibrary  0.2.1.6
Statistics.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 24.7.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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Basic.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Generators.mac")$
00026 
00027 
00028 kill(f)$
00029 
00030 /* ******************
00031    * Vertex degrees *
00032    ******************
00033 */
00034 
00035 okltest_degree_g(f) := (
00036   assert(f(1,[{1},{}]) = 0),
00037   assert(f(1,[{1,2},{}]) = 0),
00038   assert(f(1,[{1,2},{{1,2}}]) = 1),
00039   for n : 0 thru 3 do block([G : complete_stdg(n)],
00040     for v in G[1] do
00041       assert(f(v,G) = n-1)
00042   ),
00043   for n : 2 thru 4 do block([G : og2g(pathgraph_og(n))],
00044     for v in G[1] do block([d : f(v,G)],
00045       if elementp(v,{1,n}) then assert(d = 1)
00046       else assert(d = 2)
00047   )),
00048   for n : 3 thru 5 do block([G : ogl2gl(cyclegraph_ogl(n))],
00049     for v in G[1] do
00050       assert(f(v,G) = 2)
00051   ),
00052   true)$
00053 
00054 okltest_degree1_gg(f) := (
00055   for n : 0 thru 3 do block([G : ogg2gg(dipole_ogg(n))],
00056     for v in G[1] do
00057       assert(f(v,G) = n)
00058   ),
00059    for n : 0 thru 3 do block([G : ogg2gg(bouquet_ogg(n))],
00060     assert(f(1,G) = n)
00061   ),
00062   assert(okltest_degree_g(buildq([f],lambda([v,G],f(v,g2gg(G)))))),
00063   true)$
00064 
00065 okltest_degree2_gg(f) := (
00066   for n : 0 thru 3 do block([G : ogg2gg(dipole_ogg(n))],
00067     for v in G[1] do
00068       assert(f(v,G) = n)
00069   ),
00070    for n : 0 thru 3 do block([G : ogg2gg(bouquet_ogg(n))],
00071     assert(f(1,G) = 2* n)
00072   ),
00073   assert(okltest_degree_g(buildq([f],lambda([v,G],f(v,g2gg(G)))))),
00074   true)$
00075 
00076 okltest_outdegree_dg(f) := (
00077   assert(f(1,[{1},{}]) = 0),
00078   assert(f(1,[{1,2,3},{[1,2],[2,3]}]) = 1),
00079   assert(f(2,[{1,2,3},{[1,2],[2,3]}]) = 1),
00080   assert(f(3,[{1,2,3},{[1,2],[2,3]}]) = 0),
00081   true)$
00082 
00083 okltest_outdegree_dgl(f) := (
00084   assert(f(1,[{1},{[1,1]}]) = 1),
00085   assert(okltest_outdegree_dg(f) = true),
00086   true)$
00087 
00088 okltest_indegree_dg(f) := (
00089   assert(f(1,[{1,2},{[2,1]}]) = 1),
00090   assert(okltest_outdegree_dg(buildq([f], lambda([v,G], f(v,transposed_dg(G))))) = true),
00091   true)$
00092 
00093 okltest_indegree_dgl(f) := (
00094   assert(f(1,[{1,2},{[1,1],[2,1]}]) = 2),
00095   assert(okltest_indegree_dg(f) = true),
00096   assert(okltest_outdegree_dg(buildq([f], lambda([v,G], f(v,transposed_dg(G))))) = true),
00097   true)$
00098 
00099 okltest_vertex_degrees_g(f) := block(
00100   assert(hm2sm(f([{},{}])) = {}),
00101   assert(hm2sm(f([{1},{}])) = {[1,0]}),
00102   assert(hm2sm(f([{1,2},{}])) = {[1,0],[2,0]}),
00103   assert(hm2sm(f([{1,2},{{1,2}}])) = {[1,1],[2,1]}),
00104   assert(hm2sm(f([{1,2,3,4,5,6},{{1,2},{3,2},{2,4},{4,5},{4,6}}])) =
00105     {[1,1],[3,1],[2,3],[4,3],[5,1],[6,1]}),
00106   assert(okltest_degree_g(buildq([f],lambda([v,G],ev_hm(f(G),v))))),
00107   true)$
00108 
00109 okltest_vertex_degrees_og(f) := block(
00110   assert(hm2sm(f([[],[]])) = {}),
00111   assert(hm2sm(f([[1],[]])) = {[1,0]}),
00112   assert(hm2sm(f([[1,2],[]])) = {[1,0],[2,0]}),
00113   assert(hm2sm(f([[1,2],[[1,2]]])) = {[1,1],[2,1]}),
00114   assert(hm2sm(f([[1,2,3,4,5,6],[[1,2],[3,2],[2,4],[4,5],[4,6]]])) =
00115     {[1,1],[3,1],[2,3],[4,3],[5,1],[6,1]}),
00116   assert(okltest_vertex_degrees_g(buildq([f],lambda([G],f(g2og(G)))))),
00117   true)$
00118 
00119 okltest_vertex_degrees1_gl(f) := block(
00120   assert(okltest_vertex_degrees_g(f)),
00121   assert(hm2sm(f([{1},{{1}}])) = {[1,1]}),
00122   assert(hm2sm(f([{1,2},{{2},{1,2}}])) = {[1,1],[2,2]}),
00123   true)$
00124 
00125 okltest_vertex_degrees1_ogl(f) := block(
00126   assert(okltest_vertex_degrees1_gl(buildq([f],lambda([G],f(gl2ogl(G)))))),
00127   true)$
00128 
00129 okltest_vertex_degrees1_gg(f) := (
00130   assert(okltest_vertex_degrees1_gl(buildq([f],lambda([G],f(gl2gg(G)))))),
00131   assert(okltest_degree1_gg(buildq([f],lambda([v,G],ev_hm(f(G),v))))),
00132   true)$
00133 
00134 okltest_vertex_degrees1_ogg(f) := block(
00135   assert(okltest_vertex_degrees1_gg(buildq([f],lambda([G],f(gg2ogg(G)))))),
00136   true)$
00137 
00138 okltest_vertex_degrees2_gl(f) := block(
00139   assert(okltest_vertex_degrees_g(f)),
00140   assert(hm2sm(f([{1},{{1}}])) = {[1,2]}),
00141   assert(hm2sm(f([{1,2},{{2},{1,2}}])) = {[1,1],[2,3]}),
00142   true)$
00143 
00144 okltest_vertex_degrees2_ogl(f) := block(
00145   assert(okltest_vertex_degrees2_gl(buildq([f],lambda([G],f(gl2ogl(G)))))),
00146   true)$
00147 
00148 okltest_vertex_degrees2_gg(f) := (
00149   assert(okltest_vertex_degrees2_gl(buildq([f],lambda([G],f(gl2gg(G)))))),
00150   assert(okltest_degree2_gg(buildq([f],lambda([v,G],ev_hm(f(G),v))))),
00151   true)$
00152 
00153 okltest_vertex_degrees2_ogg(f) := block(
00154   assert(okltest_vertex_degrees2_gg(buildq([f],lambda([G],f(gg2ogg(G)))))),
00155   true)$
00156 
00157 okltest_vertex_outdegrees_dg(f) := (
00158   assert(hm2sm(f([{},{}])) = {}),
00159   assert(hm2sm(f([{1},{}])) = {[1,0]}),
00160   assert(hm2sm(f([{1,2,3,4},{[1,2],[1,3],[2,1]}])) = {[1,2],[2,1],[3,0],[4,0]}),
00161   true)$
00162 
00163 okltest_vertex_outdegrees_dgl(f) := (
00164   assert(hm2sm(f([{1},{[1,1]}])) = {[1,1]}),
00165   assert(okltest_vertex_outdegrees_dg(f) = true),
00166   true)$
00167 
00168 okltest_vertex_outdegrees_odg(f) := (
00169   assert(okltest_vertex_outdegrees_dg(buildq([f], lambda([G], f(dg2odg(G))))) = true),
00170   true)$
00171 
00172 okltest_vertex_outdegrees_odgl(f) := (
00173   assert(okltest_vertex_outdegrees_dgl(buildq([f], lambda([G], f(dgl2odgl(G))))) = true),
00174   true)$
00175 
00176 okltest_vertex_indegrees_dg(f) := (
00177   assert(okltest_vertex_outdegrees_dg(buildq([f], lambda([G], f(transposed_dg(G))))) = true),
00178   true)$
00179 
00180 okltest_vertex_indegrees_dgl(f) := (
00181   assert(okltest_vertex_outdegrees_dgl(buildq([f], lambda([G], f(transposed_dgl(G))))) = true),
00182   true)$
00183 
00184 okltest_vertex_indegrees_odg(f) := (
00185   assert(okltest_vertex_outdegrees_odg(buildq([f], lambda([G], f(transposed_odg(G))))) = true),
00186   true)$
00187 
00188 okltest_vertex_indegrees_odgl(f) := (
00189 assert(okltest_vertex_outdegrees_odgl(buildq([f], lambda([G], f(transposed_odgl(G))))) = true),
00190   true)$
00191 
00192 okltest_min_vertex_degree_v_og(f) := block(
00193   assert(f([[],[]]) = [inf]),
00194   assert(f([[1],[]]) = [0,1]),
00195   assert(f([[1,2],[]]) = [0,1]),
00196   assert(f([[2,1],[]]) = [0,2]),
00197   assert(f([[1,2],[{1,2}]]) = [1,1]),
00198   assert(f([[2,1],[{1,2}]]) = [1,2]),
00199   assert(f([[1,2,3,4,5,6],[{1,2},{3,2},{2,4},{4,5},{4,6}]]) =
00200     [1,1]),
00201   assert(f([[1,2,3,4,5,6],[{1,2},{3,1},{1,4},{4,5},{4,6}]]) =
00202     [1,2]),
00203   assert(f([[3,2,1,4,5,6],[{1,2},{3,1},{1,4},{4,5},{4,6}]]) =
00204     [1,3]),
00205   assert(f([[1,2,3,4,5,6,7],[{1,2},{3,2},{2,4},{4,5},{4,6}]]) =
00206     [0,7]),
00207   true)$
00208 
00209 okltest_min_vertex_degree1_v_ogl(f) := (
00210   assert(f([[1],[{1}]]) = [1,1]),
00211   assert(okltest_min_vertex_degree_v_og(f)),
00212   true)$
00213 
00214 okltest_min_vertex_degree2_v_ogl(f) := (
00215   assert(f([[1],[{1}]]) = [2,1]),
00216   assert(okltest_min_vertex_degree_v_og(f)),
00217   true)$
00218 
00219 okltest_max_vertex_degree_v_og(f) := (
00220   assert(f([[],[]]) = [minf]),
00221   assert(f([[1],[]]) = [0,1]),
00222   assert(f([[1,2],[]]) = [0,1]),
00223   assert(f([[2,1],[]]) = [0,2]),
00224   assert(f([[1,2],[{1,2}]]) = [1,1]),
00225   assert(f([[2,1],[{1,2}]]) = [1,2]),
00226   assert(f([[1,2,3],[{1,2},{1,3}]]) = [2,1]),
00227   assert(f([[1,2,3],[{2,1},{2,3}]]) = [2,2]),
00228   true)$
00229 
00230 okltest_max_vertex_degree1_v_ogl(f) := (
00231   assert(f([[1],[{1}]]) = [1,1]),
00232   assert(okltest_max_vertex_degree_v_og(f)),
00233   true)$
00234 
00235 okltest_max_vertex_degree2_v_ogl(f) := (
00236   assert(f([[1],[{1}]]) = [2,1]),
00237   assert(okltest_max_vertex_degree_v_og(f)),
00238   true)$
00239 
00240 okltest_min_vertex_outdegree_v_dg(f) := (
00241   assert(f([{},{}]) = [inf]),
00242   assert(f([{1},{}]) = [0,1]),
00243   assert(f([{-1,1},{}]) = [0,-1]),
00244   assert(f([{1,2,3},{[1,2],[2,3],[3,1],[1,3]}]) = [1,2]),
00245   assert(okltest_min_vertex_outdegree_dg(buildq([f], lambda([G], first(f(G))))) = true),
00246   true)$
00247 
00248 okltest_min_vertex_outdegree_v_dgl(f) := (
00249   assert(f([{1},{[1,1]}]) = [1,1]),
00250   assert(okltest_min_vertex_outdegree_v_dg(f) = true),
00251   assert(okltest_min_vertex_outdegree_dgl(buildq([f], lambda([G], first(f(G))))) = true),
00252   true)$
00253 
00254 okltest_min_vertex_indegree_v_dg(f) := (
00255   assert(okltest_min_vertex_outdegree_v_dg(buildq([f], lambda([G], f(transposed_dg(G))))) = true),
00256   assert(okltest_min_vertex_indegree_dg(buildq([f], lambda([G], first(f(G))))) = true),
00257   true)$
00258 
00259 okltest_min_vertex_indegree_v_dgl(f) := (
00260   assert(okltest_min_vertex_outdegree_v_dgl(buildq([f], lambda([G], f(transposed_dgl(G))))) = true),
00261   assert(okltest_min_vertex_indegree_dgl(buildq([f], lambda([G], first(f(G))))) = true),
00262   true)$
00263 
00264 okltest_min_vertex_outdegree_dg(f) := (
00265   assert(f([{},{}]) = inf),
00266   assert(f([{1},{}]) = 0),
00267   assert(f([{-1,1},{}]) = 0),
00268   assert(f([{1,2,3},{[1,2],[2,3],[3,1],[2,3],[3,2]}]) = 1),
00269   true)$
00270 
00271 okltest_min_vertex_outdegree_dgl(f) := (
00272   assert(f([{1},{[1,1]}]) = 1),
00273   assert(okltest_min_vertex_outdegree_dg(f) = true),
00274   true)$
00275 
00276 okltest_min_vertex_indegree_dg(f) := (
00277   assert(okltest_min_vertex_outdegree_dg(buildq([f], lambda([G], f(transposed_dg(G))))) = true),
00278   true)$
00279 
00280 okltest_min_vertex_indegree_dgl(f) := (
00281   assert(okltest_min_vertex_outdegree_dgl(buildq([f], lambda([G], f(transposed_dgl(G))))) = true),
00282   true)$
00283 
00284 okltest_vertex_degrees_hm_g(f) := block(
00285   assert(hm2sm(f([{},{}])) = {}),
00286   assert(hm2sm(f([{1},{}])) = {[0,1]}),
00287   assert(hm2sm(f([{1,2},{}])) = {[0,2]}),
00288   assert(hm2sm(f([{1,2},{{1,2}}])) = {[1,2]}),
00289   assert(hm2sm(f([{1,2,3,4,5,6},{{1,2},{3,2},{2,4},{4,5},{4,6}}])) =
00290     {[1,4],[3,2]}),
00291   true)$
00292 
00293 
00294