Identifying Codes

In this repository, we collect scripts and (extra) experiments and results, corresponding to our paper:

Solving the Identifying Code Set Problem with Grouped Independent Support, Anna L.D. Latour, Arunabha Sen, Kuldeep S. Meel, IJCAI 2023 (paper #4051). [paper pdf, extended version]

Note: as we were doing the experiment, we had not yet settled on a name for gismo, so in this repository we refer to it as arjun-grp.

Related sources

• The gismo code: github.com/meelgroup/gismo.
• PBLib (needed for encoding cardinality constraints): github.com/master-keying/pblib

License information and attribution

The code in this repository is distributed under an MIT license: LICENSES/MIT_LICENSE. The networks in the instances/networks are obtained from:

• networkrepository.com
• github.com/kaustav-basu/IdentifyingCodes and are replicated with their corresponding license files in their directories.

All other data published in this repository is distributed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license: LICENSES/by-nc-sa.markdown.

Organisation

• binaries/ Contains the gismo binary used for our experiments.
• exp-data/ Contains the json files with information on the experiments, obtained from parsing the raw output files in the results/ subdirectories.
• instances/
  • gis/ Grouped CNF (GCNF) encodings of input problems.
  • ilp/ ILP encodings of input problems.
  • networks/ The input networks (edge lists and matrix market format).
• results/ Contains the raw output files from our experiments.
• scripts/
  • data-analysis/ Scripts for parsing the output files and organising the data into json files. Scripts for reading out json files and aggregating the data into pandas data frames.
  • data-visualisation/ iPython Notebook for visualising the results. Output files for figures and tables in paper and extended version of paper.
  • encoding/ Scripts for building an Identifying Code Set problem out of an input network. Scripts for converting that problem into ILP of GCNF.
  • helpers/ Helper scripts.
  • pbs/ Scripts for running the experiments on a cluster.
• LICENSES License information for the code in this repository and all the data in this repository (except the netoworks in the networks/ directory and its subdirectories).
• README.md This file.