OKlibrary  0.2.1.6
Statistics.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 30.5.2009 (Swansea) */
00002 /* Copyright 2009, 2012 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 
00024 
00025 /* ******************
00026    * Basic measures *
00027    ******************
00028 */
00029 
00030 /* Counting the number of vertices: */
00031 
00032 nver_hg(G) := length(G[1])$
00033 nver_ohg(G) := length(G[1])$
00034 nver_ghg(G) := length(G[1])$
00035 nver_oghg(G) := length(G[1])$
00036 
00037 /* Counting the number of hyperedges: */
00038 
00039 nhyp_hg(G) := length(G[2])$
00040 nhyp_ohg(G) := length(G[2])$
00041 nhyp_ghg(G) := length(G[2])$
00042 nhyp_oghg(G) := length(G[2])$
00043 
00044 /* The list of pairs
00045    [occurring hyperedge-lengths, number of hyperedges of this length],
00046    sorted by ascending hyperedge-length:
00047 */
00048 nhyp_list_ohg(G) := block([n : nver_ohg(G), counts, res : [], l],
00049   counts : make_array(fixnum, n+1),
00050   for H in G[2] do (l : length(H), counts[l] : counts[l] + 1),
00051   delete(0,create_list(if counts[i]=0 then 0 else [i, counts[i]], i,0,n)))$
00052 nhyp_list_hg(G) := nhyp_list_ohg(G)$
00053 /* Remark: Computing the same function as ncl_list_fcl rsp. ncl_list_fcs.
00054 */
00055 
00056 
00057 /* ******************
00058    * Vertex degrees *
00059    ******************
00060 */
00061 
00062 /* The vertex-degrees of a hypergraph, as hash-map. */
00063 vertex_degrees_hg(G) := block([h : sm2hm({})],
00064  for H in G[2] do
00065   for v in H do enter_new_occurrence(h,v),
00066  for v in G[1] do
00067    if ev_hm(h,v)=false then set_hm(h,v,0),
00068  return(h))$
00069 vertex_degrees_ohg(G) := vertex_degrees_hg(G)$
00070 /* The same list, but sorted according to the vertex degrees: */
00071 sorted_vertex_degrees_hg(G) := sort(hm2osm(vertex_degrees_hg(G)), 
00072  lambda([p1,p2],is(second(p1) > second(p2))))$
00073 /* For ordered hypergraphs the sorting is stable w.r.t. the given
00074    order of vertices:
00075 */
00076 sorted_vertex_degrees_ohg(G) := block(
00077  [h : osm2hm(map("[",G[1],create_list(i,i,1,length(G[1]))))],
00078   sort(hm2osm(vertex_degrees_ohg(G)),
00079    lambda([p1,p2],is(second(p1) > second(p2) or (second(p1) = second(p2) and ev_hm(h,first(p1)) < ev_hm(h,first(p2)))))))$
00080 
00081 
00082 /* The extended vertex-degrees of hypergraph G as hash-map, which maps vertex v
00083    to the list of pairs [occurring hyperedge-edge lengths, count], sorted
00084    by ascending hyperedge-length:
00085 */
00086 vertex_degrees_nhyplist_hg(G) := block([h : sm2hm({}), l],
00087  for v in G[1] do set_hm(h,v,sm2hm({})),
00088  for H in G[2] do (
00089    l : length(H),
00090    for v in H do enter_new_occurrence(ev_hm(h,v), l)
00091  ),
00092  for v in G[1] do set_hm(h,v, get_distribution(ev_hm(h,v))),
00093  h)$
00094 /* For vertex v this is nhyp_list_hg(ses2hg(scs_l(G[2],v))). */
00095