README file for the NetEnum&Hierarchy package; Oct 30, 2015
update on Apr 19, 2016: add an introduction on how to read the results
The purposes of this package include i) enumerate all multi-source multi-sink hyperedge networks for a given (K,E) pair, where K is the number of sources and E is the number of hyperedges [1]. ii), it investigates the hierarchy property of networks with different sizes using the operations defined in [1]. iii), it investigates the partial closure of a seed list of tiny networks, as stated in [1]. This package relies on installation of GAP: http://www.gap-system.org/Packages/packages.html
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 "networkEnumeration-05-13-2015": GAP source files, and data files
2. folder "InsufficientCases": data files saved for scalar binary insufficient cases of networks in [1];
3. files "embeddingResults*.txt": source files to get forbidden minors for different sizes;
6. README.txt: this file
==================================================================================
b) SYSTEM REQUIREMENTS:
Mac OS, or Linux, as lrs and chmlib packages require.
SPACE: 2.14 GB available free space for the package with results files.
==================================================================================
c) INSTALLATION:
First step is to install GAP. Please refer to http://www.gap-system.org/Packages/packages.html for how to install and use GAP.
After downloading and unzipping this package in a proper directory, you only need to
I. open your GAP program in the directory of this package
II. use Read("filename") command in gap to use the functions in this package.
You are ready to use this package. Test the package using Read("/yourpath/NetEnum\&Hierarchy/networkEnumeration-05-13-2015/congduanStyleNetEnum.g");
==========================================================================================
d) USAGE:
0. This part is to verify or regenerate enumerate and hierarchy results for all networks in [1]. For rate region calculations, you may need to integrate this package with our rate region calculation package, which is available at [3]: https://goo.gl/v98ij4
1. Enumeration of all network instances
To get list of non-isomorphic networks only: Read("/yourpath/NetEnum\&Hierarchy/networkEnumeration-05-13-2015/congduanStyleNetEnum.g") with change the parameters nSources and nEdges to the numbers you want.
To get list of networks handleable by rate region calculation package, Read("/yourpath/NetEnum\&Hierarchy/networkEnumeration-05-13-2015/congduanStyleNetEnumWMatrices.g") with change the parameters nSources and nEdges to the numbers you want. After you get the top-*.txt and dec-*.txt files, simply specify them as topfilename and decfilename while regenerating rate regions in the rate region calculation package.
To get list of isomorphic networks: Read("/yourpath/NetEnum\&Hierarchy/networkEnumeration-05-13-2015/congduanStyleNetEnumWMatricesAndIsos.g") with change the parameters nSources and nEdges to the numbers you want.
2. Regenerate forbidden minor results:
To get forbidden minors for (2,3) networks, Read("/yourpath/NetEnum\&Hierarchy/embeddingResults_23.g").
To get forbidden minors for (3,2) networks, Read("/yourpath/NetEnum\&Hierarchy/embeddingResults_32.g").
For other networks sizes, change the files in ./InsufficientCases/ accordingly.
Note that the NM*.txt files can be obtained from the rate region calculation package following these steps: compare the bounds on rate regions, using compare_bounds_GeneralWdirectAccess.m, to get non-match instances and save them in a *.mat file, then use writeIndices.m to convert the matlab file to NM*.txt file and save them in ./InsufficientCases/.
3. Regenerate results for partial closure of a seed list: Read("/yourpath/NetEnum\&Hierarchy/networkEnumeration-05-13-2015/dataset-v1/organize2112closure.g") with change of parameters nSourcesMax and nEdgesMax to the numbers as you want, say (3,4) as the cap.
Similarly, other source files can get the closure with tracking the origins and no embedding, etc, as the file names indicate.
4. How to read and configure the network: after the networkList is generated, use
index such as networkList[x]; to get the x-th network configuration. To get the
(Q,W) representation (see reference [1]) you only need to look the 3rd and 4th
element in it. For example, a 2-source 2-edge network configuration is
[ [ [ 1, [ 3, 4 ] ], [ 2, [ 4, 5 ] ], [ 3, [ 5, 6 ] ], [ 4, [ 6 ] ] ],
[ [ 5, [ 1 ] ], [ 6, [ 2 ] ] ], [ [ 3, [ 1 ] ], [ 4, [ 1, 2 ] ] ],
[ [ 1, [ 2, 3 ] ], [ 2, [ 3, 4 ] ] ], Group( () ) ],
with 3rd and 4th elements
[ [ 3, [ 1 ] ], [ 4, [ 1, 2 ] ] ],
[ [ 1, [ 2, 3 ] ], [ 2, [ 3, 4 ] ] ],
which indicate in this network, one edge (3) is a function of source 1, and another
edge (4) is a function of sources 1 and 2;
at the decoder side, source 1 can be recovered by accessing source 2 and edge 3,
while source 2 can be recovered by accessing edges 3 and 4.
=======================================================================================
e) REGENERATE or VERIFY RESULTS in paper [1]: refer to d)
=======================================================================================
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, "Rate Region Calculation package", available: https://goo.gl/v98ij4