OKlibrary  0.2.1.6
Statistics.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 21.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/DataStructures/Lisp/HashMaps.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Basic.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00025 
00026 
00027 /* ******************
00028    * Vertex degrees *
00029    ******************
00030 */
00031 
00032 /* The degree of a vertex in a graph: */
00033 degree_g(v,G) := length(neighbours_g(v,G))$
00034 /* For general graphs, counting loops once: */
00035 degree1_gg(v,G) := length(subset(G[2],lambda([e],elementp(v,G[3](e)))))$
00036 /* Counting loops twice: */
00037 degree2_gg(v,G) := gsum_s(
00038   lambda([el],block([e : G[3](el)], 
00039    if elementp(v,e) then if length(e) = 1 then 2 else 1
00040    else 0)),
00041   G[2])$
00042 
00043 /* Out- and in-degrees in digraphs: */
00044 outdegree_dg(v,G) := outdegree_dgl(v,G)$
00045 outdegree_dgl(v,G) := 
00046  length(sublist(listify(G[2]), lambda([e], is(e[1]=v))))$
00047 indegree_dg(v,G) := indegree_dgl(v,G)$
00048 indegree_dgl(v,G) := 
00049  length(sublist(listify(G[2]), lambda([e], is(e[2]=v))))$
00050 
00051 
00052 /* Remark: If degrees for several vertices are needed, then better the 
00053    following functions are used.
00054 */
00055 
00056 /* The vertex-degrees of a general graph as hash-map, as a generic function,
00057    applicable to gg and ogg, counting loops only once: */
00058 vertex_degrees1_genericg(G) := block([h : sm2hm({})],
00059  for e in G[2] do
00060    for v in G[3](e) do enter_new_occurrence(h,v),
00061  for v in G[1] do if ev_hm(h,v) = false then set_hm(h,v,0),
00062  return(h))$
00063 
00064 vertex_degrees_g(G) := vertex_degrees1_genericg(g2gg(G))$
00065 vertex_degrees_og(G) := vertex_degrees1_genericg(og2ogg(G))$
00066 /* For graphs with loops, counting loops once: */
00067 vertex_degrees1_gl(G) := vertex_degrees1_genericg(gl2gg(G))$
00068 vertex_degrees1_ogl(G) := vertex_degrees1_genericg(ogl2ogg(G))$
00069 vertex_degrees1_gg(G) := vertex_degrees1_genericg(G)$
00070 vertex_degrees1_ogg(G) := vertex_degrees1_genericg(G)$
00071 
00072 /* The generic version, counting loops twice (again for
00073    general graphs (ordered or unordered)): */
00074 vertex_degrees2_genericg(G) := block([h : sm2hm({})],
00075  for e in G[2] do
00076    for v in expand_edge(G[3](e)) do enter_new_occurrence(h,v),
00077  for v in G[1] do if ev_hm(h,v) = false then set_hm(h,v,0),
00078  return(h))$
00079 
00080 vertex_degrees2_gl(G) := vertex_degrees2_genericg(gl2gg(G))$
00081 vertex_degrees2_ogl(G) := vertex_degrees2_genericg(ogl2ogg(G))$
00082 vertex_degrees2_gg(G) := vertex_degrees2_genericg(G)$
00083 vertex_degrees2_ogg(G) := vertex_degrees2_genericg(G)$
00084 
00085 /* The vertex out-/in-degrees of a general directed graph as hash-map, as a
00086   generic function, applicable to gdg and ogdg: */
00087 vertex_outdegrees_genericdg(G) := block([h : sm2hm({})],
00088  for e in G[2] do enter_new_occurrence(h,G[3](first(e))),
00089  for v in G[1] do if ev_hm(h,v) = false then set_hm(h,v,0),
00090  return(h))$
00091 vertex_indegrees_genericdg(G) := block([h : sm2hm({})],
00092  for e in G[2] do enter_new_occurrence(h,G[3](second(e))),
00093  for v in G[1] do if ev_hm(h,v) = false then set_hm(h,v,0),
00094  return(h))$
00095 
00096 vertex_outdegrees_dg(G) := vertex_outdegrees_genericdg(dg2gdg(G))$
00097 vertex_outdegrees_dgl(G) := vertex_outdegrees_genericdg(dgl2gdg(G))$
00098 vertex_outdegrees_odg(G) := vertex_outdegrees_genericdg(odg2ogdg(G))$
00099 vertex_outdegrees_odgl(G) := vertex_outdegrees_genericdg(odgl2ogdg(G))$
00100 
00101 vertex_indegrees_dg(G) := vertex_indegrees_genericdg(dg2gdg(G))$
00102 vertex_indegrees_dgl(G) := vertex_indegrees_genericdg(dgl2gdg(G))$
00103 vertex_indegrees_odg(G) := vertex_indegrees_genericdg(odg2ogdg(G))$
00104 vertex_indegrees_odgl(G) := vertex_indegrees_genericdg(odgl2ogdg(G))$
00105 
00106 
00107 /* Returns the pair [min-degree, vertex_of_minimum_degree], using
00108    the vertex occurring earliest in the vertex list of the 
00109    ordered graph. [inf] is returned for the graph
00110    with empty vertex set. */
00111 min_vertex_degree_v_og(G) := block([vd : vertex_degrees_og(G)],
00112   first_smallest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00113 min_vertex_degree1_v_ogl(G) := block([vd : vertex_degrees1_ogl(G)],
00114   first_smallest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00115 min_vertex_degree2_v_ogl(G) := block([vd : vertex_degrees2_ogl(G)],
00116   first_smallest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00117 
00118 max_vertex_degree_v_og(G) := block([vd : vertex_degrees_og(G)],
00119   first_largest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00120 max_vertex_degree1_v_ogl(G) := block([vd : vertex_degrees1_ogl(G)],
00121   first_largest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00122 max_vertex_degree2_v_ogl(G) := block([vd : vertex_degrees2_ogl(G)],
00123   first_largest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00124 
00125 /* Out- and in-degrees, accepting gdg and ogdg: */
00126 min_vertex_outdegree_v_genericdg(G) := block(
00127  [vd : vertex_outdegrees_genericdg(G)],
00128   first_smallest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00129 min_vertex_indegree_v_genericdg(G) := block(
00130  [vd : vertex_indegrees_genericdg(G)],
00131   first_smallest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00132 
00133 min_vertex_outdegree_v_dg(G) := min_vertex_outdegree_v_genericdg(dg2gdg(G))$
00134 min_vertex_outdegree_v_dgl(G) := min_vertex_outdegree_v_genericdg(dgl2gdg(G))$
00135 min_vertex_indegree_v_dg(G) := min_vertex_indegree_v_genericdg(dg2gdg(G))$
00136 min_vertex_indegree_v_dgl(G) := min_vertex_indegree_v_genericdg(dgl2gdg(G))$
00137 
00138 /* Only computing the degrees: */
00139 min_vertex_outdegree_genericdg(G) := block(
00140  [vd : vertex_outdegrees_genericdg(G)],
00141   smallest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00142 min_vertex_indegree_genericdg(G) := block(
00143  [vd : vertex_indegrees_genericdg(G)],
00144   smallest_f_l(lambda([v],ev_hm(vd,v)), G[1]))$
00145 
00146 
00147 min_vertex_outdegree_dg(G) := min_vertex_outdegree_genericdg(dg2gdg(G))$
00148 min_vertex_outdegree_dgl(G) := min_vertex_outdegree_genericdg(dgl2gdg(G))$
00149 min_vertex_indegree_dg(G) := min_vertex_indegree_genericdg(dg2gdg(G))$
00150 min_vertex_indegree_dgl(G) := min_vertex_indegree_genericdg(dgl2gdg(G))$
00151 
00152 
00153 /* The hashmap of [vertex degree, frequency] pairs for a graph (that is,
00154    given a vertex degree, return its frequency): */
00155 vertex_degrees_hm_g(G) := block(
00156   [degrees : hm2sm(vertex_degrees_g(G)), deg_freq : sm2hm({})],
00157   for vd in degrees do
00158     enter_new_occurrence(deg_freq, vd[2]),
00159   return(deg_freq))$
00160 
00161