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
```