In this section we shall look at the functions provided by ITAP.
‣ proverep( rankvec, nvars, F, optargs ) | ( function ) |
Returns: A list
This function checks if there is a linear representation of an integer polymatroid rank vector. It accepts following arguments:
rankvec - A list of integers specifying a polymatroid rank vector
nvars - Number of ground set elements
F - The finite field over which we wish to find a linear representation. It can be defined by invoking the following in GAP:
q:=4;; F:= GF(q);; # here q must be a prime power
optargs is a list of optional arguments [lazy,..] where
lazy disables lazy evaluation of transporter maps if set to false, which is enabled by default in GAP.
Returns a list [true,code] if there exists such a representation and code is the vector linear code over GF(q) Returns a list [false] otherwise, indicating that no such representation exists
‣ proverate( ncinstance, rvec, F, optargs ) | ( function ) |
Returns: A list
This function checks if there is a vector linear code achieving the rate vector rvec for the network coding instance ncinstance. Uses enumerative generation methods to syetematically search for the code with desired properties. It accepts following arguments:
ncinstance is a list [cons,nsrc,nvars] containing 3 elements:
cons is a list of network coding constraints.
nsrc is the number of sources.
nvars is the number of random variables associated with the network.
rvec - A list of nvars integers specifying a rate vector
F is the finite field over which we wish to find the vector linear code. It can be defined by invoking the following in GAP:
q:=4;; F:= GF(q);; # here q must be a prime power
optargs is a list of optional arguments [lazy,..] where lazy disables lazy evaluation of transporter maps if set to false, which is enabled by default.
Returns a list [true,code] if there exists such a representation and code is the vector linear code over GF(q) Returns a list [false] otherwise, indicating that no such code exists
‣ proveregion( ncinstance, k, F, optargs ) | ( function ) |
Returns: A list
This function computes the all rate vectors achievable via vector linear CodeString over the specified fiite field for the network coding instance ncinstance. Uses enumerative generation methods to syetematically search for codes with desired properties. It accepts following arguments:
ncinstance is a list [cons,nsrc,nvars] containing 3 elements:
cons is a list of network coding constraints.
nsrc is the number of sources.
nvars is the number of random variables associated with the network.
k - Maximum number of symbols per message
F is the finite field over which we wish to find the vector linear codes. It can be defined by invoking the following in GAP:
q:=4;; F:= GF(q);; # here q must be a prime power
optargs is a list of optional arguments [opt_dmax,..] where opt_dmax specifies an upper bound on the dimension of linear codes (alternatively, the rank of underlying polymatroid) to search. By default this is equal to nsrc*k, which may sometimes be unnecessary, and a lower value might suffice.
Returns a list [rays,codes] where rays is a list of all achievable rate vectors and codes is a list of linear codes.
‣ proverate_groebner( ncinstance, rvec, F, optargs ) | ( function ) |
Returns: A list
This function checks if there is a vector linear code achieving the rate vector rvec for the network coding instance ncinstance. Uses GAP interface to Singular to find Groebner basis of the system of polynomial equations given by the path gain algebraic construction of Subramanian and Thangraj [ST10] . It accepts following arguments:
ncinstance is a list [cons,nsrc,nvars] containing 3 elements:
cons is a list of network coding constraints.
nsrc is the number of sources.
nvars is the number of random variables associated with the network.
rvec - A list of nvars integers specifying a rate vector
F is the finite field over which we wish to find the vector linear code. It can be defined by invoking the following in GAP:
q:=4;; F:= GF(q);; # here q must be a prime power
optargs is a list of optional arguments [lazy,..] where lazy disables lazy evaluation of transporter maps if set to false, which is enabled by default.
Returns a list [true,code] if there exists such a representation where code is the vector linear code over GF(q). Returns a list [false] otherwise, indicating that no such code exists
\textbf{NOTE:} Certain naming convensions are followed while defining network coding instances. The source messages are labeled with [1...nsrc] while rest of the messages are labeled [nsrc...nvars]. Furthermore, the list cons includes all network constraints except source independence. This constraint is implied with the labeling i.e. ITAP enforces it by default for the messages labeled [1...nsrc]. See next section for usage examples.
‣ provess( Asets, nvars, svec, F, optargs ) | ( function ) |
Returns: A list
This function checks if there is a multi-linear secret sharing scheme with secret and share sizes given by svec and the access structure Asets with one dealer and nvars-1 parties. It accepts following arguments:
Asets - A list of authorized sets each specified as a subset of [nvars-1]
nvars - Number of participants (including one dealer)
svec - vector of integer share sizes understood as number of \mathbb{F}_q symbols, with index 1 giving secret size and index i,i\in \{2,...,nvars\} specifying share sizes of different parties
F - The finite field over which we wish to find a multi-linear scheme. It can be defined by invoking the following in GAP:
q:=4;; F:= GF(q);; # here q must be a prime power
optargs is a list of optional arguments [lazy,..] where
lazy disables lazy evaluation of transporter maps if set to false, which is enabled by default in GAP.
Returns a list [true,code] if there exists such a scheme where code is the vector linear code over GF(q). Returns a list [false] otherwise, indicating that no such scheme exists.
\textbf{NOTE:} No input checking is performed to verify if input Asets follows labeling convensions. The map returned with a linear scheme is a map f:[nvars]\rightarrow [nvars] with dealer associated with label 1 and parties associated with labels \{2,...,nvars\}. See next section for usage examples.
‣ DisplayCode( code ) | ( function ) |
Returns: nothing
Displays a network code (or an integer polymatroid). It accepts 1 argument:
code - A list [s,map] containing 2 elements:
s - A list of subspaces where is subspace is itself a list of basis vectors
map - A GAP record mapping subspaces in s to network messages or to polymatroid ground set elements
Returns nothing
gap> s:=[ [ [ 0*Z(2), 0*Z(2), Z(2)^0 ] ], [ [ 0*Z(2), Z(2)^0, 0*Z(2) ] ],\ > [ [ 0*Z(2), Z(2)^0, Z(2)^0 ] ], [ [ Z(2)^0, 0*Z(2), 0*Z(2) ] ],\ > [ [ Z(2)^0, 0*Z(2), Z(2)^0 ] ], [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ],\ > [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ];; gap> map:=rec( 1 := 1, 2 := 2, 3 := 4, 4 := 3, 5 := 6, 6 := 5, 7 := 7 );; gap> DisplayCode([s,map]);; 1->1 . . 1 ============================= 2->2 . 1 . ============================= 3->4 . 1 1 ============================= 4->3 1 . . ============================= 5->6 1 . 1 ============================= 6->5 1 1 . ============================= 7->7 1 1 1 =============================
itap comes equipped with a catalog of examples, which contains well-known network coding instances and integer polymatroids. This catalog is intended to be of help to the user for getting started with using ITAP. Most of the network coding instances in this catalog can be found in [Yeu08] and [DFZ07]. Some of the integer polymatroids in the catalog are taken from http://code.ucsd.edu/zeger/linrank/. These polymatroids correspond to the extreme rays of the cone of linear rank inequalities in 5 variables, found by Dougherty, Freiling and Zeger. See [DFZ09] for details.
‣ FanoNet( ) | ( function ) |
Returns: A list
Returns the Fano instance. It accepts no arguments. Returns a list.
gap> FanoNet(); [ [ [ [ 1, 2 ], [ 1, 2, 4 ] ], [ [ 2, 3 ], [ 2, 3, 5 ] ], [ [ 4, 5 ], [ 4, 5, 6 ] ], [ [ 3, 4 ], [ 3, 4, 7 ] ], [ [ 1, 6 ], [ 3, 1, 6 ] ], [ [ 6, 7 ], [ 2, 6, 7 ] ], [ [ 5, 7 ], [ 1, 5, 7 ] ] ], 3, 7 ] gap> rlist:=proverate(FanoNet(),[1,1,1,1,1,1,1],GF(2),[]);; gap> rlist[1]; # Fano matroid is representable over GF(2) true gap> DisplayCode(rlist[2]); 1->1 . . 1 ============================= 2->2 . 1 . ============================= 3->4 . 1 1 ============================= 4->3 1 . . ============================= 5->6 1 . 1 ============================= 6->5 1 1 . ============================= 7->7 1 1 1 ============================= gap> rlist:=proverate(FanoNet(),[1,1,1,1,1,1,1],GF(3),[]);; gap> rlist[1]; # Fano matroid is not representable over GF(3) false
‣ NonFanoNet( ) | ( function ) |
Returns: A list
Returns the NonFano instance. It accepts no arguments. Returns a list.
gap> NonFanoNet(); gap> gap> NonFanoNet(); [ [ [ [ 1, 2, 3 ], [ 1, 2, 3, 4 ] ], [ [ 1, 2 ], [ 1, 2, 5 ] ], [ [ 1, 3 ], [ 1, 3, 6 ] ], [ [ 2, 3 ], [ 2, 3, 7 ] ], [ [ 4, 5 ], [ 3, 4, 5 ] ], [ [ 4, 6 ], [ 2, 4, 6 ] ], [ [ 4, 7 ], [ 1, 4, 7 ] ] ], 3, 7 ]
‣ VamosNet( ) | ( function ) |
Returns: A list
Returns the Vamos instance. It accepts no arguments. Returns a list.
gap> VamosNet(); [ [ [ [ 1, 2, 3, 4 ], [ 1, 2, 3, 4, 5 ] ], [ [ 1, 2, 5 ], [ 1, 2, 5, 6 ] ], [ [ 2, 3, 6 ], [ 2, 3, 6, 7 ] ], [ [ 3, 4, 7 ], [ 3, 4, 7, 8 ] ], [ [ 4, 8 ], [ 2, 4, 8 ] ], [ [ 2, 3, 4, 8 ], [ 1, 2, 3, 4, 8 ] ], [ [ 1, 4, 5, 8 ], [ 1, 2, 3, 4, 5, 8 ] ], [ [ 1, 2, 3, 7 ], [ 1, 2, 3, 4, 7 ] ], [ [ 1, 5, 7 ], [ 1, 3, 5, 7 ] ] ], 3, 7 ]
‣ U2kNet( ) | ( function ) |
Returns: A list
Returns the instance associated with uniform matroid U^2_k. It accepts one argument k specifying the size of uniform matroid. Returns a list.
gap> U2kNet(4); [ [ [ 1, 2 ], [ 1, 2, 3 ] ], [ [ 1, 3 ], [ 1, 3, 4 ] ], [ [ 1, 4 ], [ 1, 2, 4 ] ], [ [ 2, 3 ], [ 1, 2, 3 ] ], [ [ 2, 4 ], [ 1, 2, 4 ] ], [ [ 3, 4 ], [ 1, 3, 4 ] ] ], 2, 4 ]
‣ ButterflyNet( ) | ( function ) |
Returns: A list
Returns the Butterfly instance. It accepts no arguments. Returns a list.
‣ Subspace5( ) | ( function ) |
Returns: A list
Returns the extreme rays of cone formed by linear rank inequalities in 5 variables. It accepts no arguments. Returns a list.
gap> rays5:=Subspace5();; gap> Size(rays5); 162 gap> rlist:=proverep(rays5[46],5,GF(2),[]) > rlist[1]; true gap> gap> DisplayCode(rlist[2]); 1->4 . . . 1 ============================= 2->5 . . 1 . ============================= 3->3 . 1 . . ============================= 4->2 1 . . . . . 1 1 ============================= 5->1 1 . . 1 . 1 1 1 =============================
‣ BenalohLeichter( ) | ( function ) |
Returns: A list of lists specifing authorized subsets of \{1,2,3,4\}
Returns the access structure associated with secret sharing scheme of Benaloh and Leichter that was used to show that share sizes can be larger than secret size. See [BL90] for details. It accepts no arguments. Returns a list.
gap> B:=BenalohLeichter(); [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ] ] gap> rlist:=provess(B,5,[2,2,3,3,2],GF(2),[]);; gap> rlist[1]; true gap> DisplayCode(rlist[2]); 1->1 . . . . 1 . . . . . . 1 ============================= 2->2 . . 1 . . . . . . 1 . . ============================= 3->3 . 1 . . . . . . 1 . . 1 . . . 1 1 . ============================= 4->5 1 . . . . . . 1 . . . . ============================= 5->4 1 . . . . 1 . 1 . . 1 . . . 1 . . . =============================
‣ Threshold( ) | ( function ) |
Returns: A list of lists specifing authorized subsets of [n]
Returns the access structure associated with Shamir's (k,n) threshold scheme. See [Sha79] for details. It accepts following arguments:
n - number of shares
k - threshold
gap> T:=Threshold(4,2); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ] gap> rlist:=provess(T,5,[1,1,1,1,1],GF(2),[]); [ false ] gap> rlist:=provess(T,5,[1,1,1,1,1],GF(3),[]); [ false ] gap> rlist:=provess(T,5,[1,1,1,1,1],GF(5),[]);; gap> rlist[1]; true gap> gap> DisplayCode(rlist[2]); 1->1 . 1 ============================= 2->2 1 . ============================= 3->3 1 1 ============================= 4->4 1 2 ============================= 5->5 1 4 =============================
‣ HyperedgeNet1( ) | ( function ) |
Returns: A list
Returns a general hyperedge network obtained via enumeration of network coding instances. See [LWW15] for details. It accepts no arguments.
gap> N:=HyperedgeNet1(); [ [ [ [ 1, 2, 3 ], [ 1, 2, 3, 4 ] ], [ [ 1, 3, 4 ], [ 1, 3, 4, 5 ] ], [ [ 3, 4, 5 ], [ 3, 4, 5, 6 ] ], [ [ 4, 5 ], [ 1, 3, 4, 5 ] ], [ [ 4, 6 ], [ 2, 3, 4, 6 ] ], [ [ 5, 6 ], [ 2, 3, 5, 6 ] ] ], 3, 6 ] gap> rlist:=proveregion(N,2,GF(2),[4]);; # k=2,opt_dmax=4=max. code dimension gap> Size(rlist[1]); # number of distinct achievable rate vectors found 122 gap> rlist[1][78]; # an achievable rate vector [ 2, 0, 1, 2, 1, 1 ] gap> lrs_path:="/home/aspitrg3-users/jayant/lrslib-061/";; # path to lrslib gap> rrcompute(rlist[1],N[2],N[3],lrs_path); # compute achievable rate region *redund:lrslib v.6.1 2015.11.20(lrsgmp.h gmp v.5.0) *Copyright (C) 1995,2015, David Avis avis@cs.mcgill.ca *Input taken from file /tmp/tmxYdXYT/file1.ext *Output sent to file /tmp/tmxYdXYT/file1red.ext *0.056u 0.004s 648Kb 0 flts 0 swaps 0 blks-in 8 blks-out *lrs:lrslib v.6.1 2015.11.20(lrsgmp.h gmp v.5.0) *Copyright (C) 1995,2015, David Avis avis@cs.mcgill.ca *Input taken from file /tmp/tmxYdXYT/file1red.ext H-representation begin ***** 7 rational 0 0 0 0 1 0 0 0 1 0 0 0 -1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 -1 -1 -1 0 0 1 1 0 -1 -1 0 0 1 0 0 0 0 0 1 1 2 -1 -2 -2 0 1 0 1 0 -1 -1 end *Totals: facets=10 bases=22 *Dictionary Cache: max size= 6 misses= 0/21 Tree Depth= 5 *lrs:lrslib v.6.1 2015.11.20(32bit,lrsgmp.h) *0.000u 0.000s 648Kb 0 flts 0 swaps 0 blks-in 0 blks-out
‣ HyperedgeNet2( ) | ( function ) |
Returns: A list
Returns a general hyperedge network obtained via enumeration of network coding instances. See [LWW15] for details. It accepts no arguments.
gap> N:=HyperedgeNet2(); [ [ [ [ 1, 2, 3, 5 ], [ 1, 2, 3, 4, 5 ] ], [ [ 1, 3 ], [ 1, 3, 5 ] ], [ [ 3, 4, 5 ], [ 3, 4, 5, 6 ] ], [ [ 4, 5 ], [ 1, 3, 4, 5 ] ], [ [ 4, 6 ], [ 2, 3, 4, 6 ] ], [ [ 5, 6 ], [ 2, 3, 5, 6 ] ] ], 3, 6 ]
generated by GAPDoc2HTML