README file for the RateRegionCalculation package; Oct 30, 2015

The main purpose of this package is to generate several types of bounds on rate
regions of multi-source multi-sink hyperedge networks. Extra features include:
I) the generation of matroid bounds on entropic vector region; II) the comparison
between bounds on rate regions;  

a) Contents
b) System Requirements
c) Installation
d) Usage
e) Verify results in [1]
f) Version history
g) Contact
h) Copyright
i) Reference

=================================================================================
a) CONTENTS:

1. folder “src”: MATLAB source files, installed lrs package, optional packages such
   as chmlib, cdd, etc;
2. folder “table”: network instances with various numbers of sources and hyperedges;
3. folder “bounds”: various bounds on entropic vector region, including the Shannon
   outer bound, binary (ternary) matroid inner bounds;
4. folder “results”: to store rate region results for different network instances, the calculated results in [1] can be obtained via the link: https://goo.gl/lyZfD9
5. folder “temp”: files and results generated when an arbitrary network configuration
   matrix is input.
6. README.txt: this file

==================================================================================
b) SYSTEM REQUIREMENTS:
Mac OS, or Linux, as lrs and chmlib packages require.
SPACE: 1.65 GB available free space for the package without results files.

==================================================================================
c) INSTALLATION: 

After downloading and unzipping this package in a proper directory, you only need to 
I. open your MATLAB program
II. go to the directory of this package
III. go to ./src/

You are ready to use this package. Test the package using Example 4 in [1]: 
simSingleGeneralNetworksWdirectAccess([1 1 1 0 0 0;1 0 1 1 0 0;0 0 1 1 1 0],[0 0;0 0;0 0;0 0;0 24;40 48; 0 0],'V','V','BI');

The results are saved in ../temp/
You may change the last three parameters to ‘H’, ‘F’, ‘O' for calculating its Shannon outer bound (actually it is the exact rate region.)

If the computer complaints about lrs package, then
read the file lrs_README.txt to reinstall the lrs package. Usually you just need to
cd to the directory ./src/ and type make all, or make all64 (for 64-bit machine).

NOTE: You are recommended to install the chmlib for faster polyhedral projection. Details
on chmlib can be found here: http://www.ece.drexel.edu/walsh/aspitrg/software.html. The 
chmlib package with some required packages are in ./src/. READ the ./src/chmlib/README.txt
for installation of chmlib. After installing chmlib, make sure the path and name of the 
executable binary file matches within the function ./src/projCHM.m. Change it accordingly,
if not match.

However, this package can still work without chmlib by using Fourier-Motzkin projection
method instead. For small networks, FM works fine. For larger networks, say number of 
variables greater than 7, we recommend you to install chmlib, if the Shannon outer bound
on rate regions are desired.

==========================================================================================
d) USAGE:

0. In order to verify or regenerate results for all networks in [1], you may need to integrate this package with our GAP package on network enumeration and hierarchy, which is available at: https://goo.gl/syKfUk

1. Generate various bounds on rate region of a network instance
   which are all saved in ../temp/:

	simSingleGeneralNetworksWdirectAccess(top,dec,sim,Projmethod,IO);
   where
	% top: a coding matrix for the topology of the network. The i-th row indicate i-th hyperedge has access to which sources and hyperedges. Details are referred to Appendix B in [2]
	% dec: a coding matrix for the decoding constraints of the network. The i-th row contains configurations for the sources associated with binary indicator of i, 
          the hyperedges and sources that a decoder has access to is coded using the 
          associated integer value from {1,2,…,2^{|\mathcal{E}|}-1}. Details are referred to Appendix B in [2].
	% sim: simulation method, ‘H’ for pure hyperplane (inequality)-representations, which are typically the outer bound.  ‘V’ for vertex-representation methods, which are typically the inner bound.
	% Projmethod: projection method. If ‘H’ method is used, this can be ‘F’ for Fourier-Motzkin projection, or ‘C’ for Convex-Hull Method. If ‘V’ method is used, this projection method can be simply ‘V’.
	% IO: inner or outer bound to use: ‘O’ for Shannon outer bound, ’BI' means binary inner, ‘TI’ means ternary inner.  For more bounds, please read the comments or matlab source file.

2. Generate vector inner bounds on rate region of a network instance which will be saved in ../temp/
	simSingleGeneralNetworksVec_WdirectAccess(top,dec,N,IO,permmethod)
   where
	% top: a coding matrix for the topology of the network. The i-th row indicate i-th hyperedge has access to which sources and hyperedges. Details are referred to Appendix B in [2]
	% dec: a coding matrix for the decoding constraints of the network. The i-th row contains configurations for the sources associated with binary indicator of i, 
          the hyperedges and sources that a decoder has access to is coded using the 
          associated integer value from {1,2,…,2^{|\mathcal{E}|}-1}. Details are referred to Appendix B in [2].
	% N: number of bits to project from, for example, if N=7, the number of variables in the network is 6, then, we will use vector inner bound projected from 7 binary or ternary bits, which will be determined by IO input.
	% IO: inner bound to use: ’BI' means binary inner, ‘TI’ means ternary inner.  
	% permmethod: permutation method. ’N’ for normal permutation, ‘C’ for constrained permutation.  For networks with variables greater than 8, ‘C’ is recommended.

ex: simSingleGeneralNetworksVec_WdirectAccess(top,dec,7,’BI’,’N’) with top=[1 1 1 0 0 0;1 0 1 1 0 0;0 0 1 1 1 0]; dec=[0 0;0 0;0 0;0 0;0 24;40 48; 0 0]; will use binary vector inner bound projected from 7 bits to get the associated vector inner bound on the rate region of Example 4 in [1].

3. Regenerate results for a specific (K,E) pair, where K= # of sources, E= # of hyperedges.
	For Shannon outer bound, scalar binary/ternary inner bounds, use the following command:
	simGeneralNetworksWdirectAccess(nSrc,nEnc,sim,Projmethod,IO,casenum,topfilename,decfilename)
	For Vector inner bounds (binary/ternary), use the following command:
	simNetworksVecNew_WdirectAccess(nSrc,nEnc,N,casenum,IO,permmethod,topfilename,decfilename)
	
	The input are similar as 1,2 but you need to specify topfilename and decfilename with correct paths, if you don’t have associated network instances saved in ../table/.  Use our network enumeration package to obtain the text files for top file and dec file first and copy them into ../table/.
*********** Some other functions for interested users are listed *******************************

4. Generate Shannon outer bound on region of entropic vectors
	[b A]=genShannOuter(numVar,ifsave,format);
   where
	% numVar: number of variables
	% ifsave: 1 to save results to ./bounds/Shannon/, 0 otherwise
	% format: std for standard format which is Ax<=b; lrs for b+Ax>=0 

5. Generate matroid bounds:
	Binary Extreme-ray representation:
	[b,A]=genBinMatrInnerBoundext(numVar); % numVar <= 8, and numVar is the number of variables
	
	Binary Half-space representation:
	[b A] = genBinMatrInnerBoundSM(N); % N: number of variables

	Binary vector bounds in extreme-ray rep.:
	[output b]=genVecBinfromNonisoNew(numBits,numVar,upto); 
   where
	% numBits: number of elements to project from;
	% numVar: number of variables to project down to;
	% upto: the max rank you want to have, if empty, upto=numBits;

	Ternary Extreme-ray representation:
	[b,A]=genTerMatrInnerBoundext(numVar); % numVar <= 8, and numVar is the number of variables
	
	Ternary Half-space representation:
	[b A] = genTerMatrInnerBoundSM(N); % N: number of variables

	Ternary vector bounds in extreme-ray rep.:
	[output b]=genVecTerfromNonisoNew(numBits,numVar,upto); 
   where
	% numBits: number of elements to project from;
	% numVar: number of variables to project down to;
	% unto: the max rank you want to have, if empty, upto=numBits;


6. Test Matroid minors:
	[Rank ind] = MinorCheck(varargin);
   where
	% The first input should be the rank vector(s) to check, if multiple vectors are 
          input as a matrix, each row is a rank vector
	% The second and rest input are minors to test, it should be the rank vector of 
          the minor except U24, U25 and U35, i.e., ‘U24’, ‘U25’, and ‘U35’ are 
          recognizable minors;
	% Rank: the rank vector(s) after excluding minors in the list;
	% ind: indicator vector associated with each input minor: i-th position is 1 means 
          input ranks contain i-th minor and 0 otherwise.  

7. Test if a matroid rank is connected:
	[is separator] = isConnected(rank); 
	% rank vector is input, is=1 if it is connected, 0 otherwise. If is=0, the 
          separator will be given.

************* SOME extra features which require the user know more about the input ********************


8. Compare bounds for network instances
	NM = comp_bounds_GeneralWdirectAccess(nSrc,nEnc,casenum,bound1,bound2)
   where
	% nSrc: number of sources, nEnc: number of hyperedges
	% casenum: indices from the enumeration of network instances in our network enumeration package, 
	% bound1 and bound2, the two bounds you want to compare: BIV for binary
	% inner bound obtained from V-method applying double description, same as
	% TIV, O for outer bound, SP for superposition, from6BIRateRegion for vector
	% inner bounds from 6 variables, etc.
	% NM: indices that the input two bounds do NOT match



=======================================================================================
e) REGENERATE or VERIFY RESULTS in paper [1]:

A. Rate Regions verification: For every network instance you want
   to verify, you may figure out its configuration matrix first and use the commands
   in 1,2 above to generate the rate region; For regeneration, use 3.

B. Compare bounds on rate regions:
	Use 8 above to verify the number of non-matched instances for different network problems.
	NOTE: when check vector bounds from N’, the casenum should be the instances for which
	      vector bound from N’-1 are not tight. e.g. verify vector binary bound from 9 bits for 
	      (2,4) network, you need to load NMBIO24from8.mat, since if vector bound from 8 bits is 
		tight, off course the bound from 9 bits will be tight as well.


C. Regenerate network instances and hierarchy:
	Use our NetEnum&Hierarchy package [3] to do this.
 
=======================================================================================
f) VERSION HISTORY:

v1.0 Oct 30, 2015

=======================================================================================
g) CONTACT:

For questions or comments, please contact Congduan Li via email congduan.li@gmail.com

We also try to implement a user-friendly interface for the network rate region calculations,
if you are interested, please contact me.
=======================================================================================
h) COPYRIGHT:
Same as the integrated packages, all codes written by the author are free for learning purposes. 

=======================================================================================
i) REFERENCES:
[1] Congduan Li, Steven Weber, John MacLaren Walsh, “On Multi-source Networks: Enumeration,
Rate Region Calculation, & Hierarchy”, IEEE Transactions on Information Theory, 
2015, SUBMITTED. [Online] Available: http://arxiv.org/abs/1507.05728

[2] Congduan Li, “On Multi-source Multi-sink Networks: Enumeration,
Rate Region Calculation, & Hierarchy”, Ph.D. dissertation, Drexel University, 2015. Available: https://goo.gl/6iIs6G

[3] Congduan Li, John MacLaren Walsh, “Network Enumeration and Hierarchy package”, available: https://goo.gl/syKfUk