SOC Observation Code

Description

SOC stands for SOC Observation Code, and is composed of three C programs and a python script:

• One, SOCgen, to generate SOC graphs (here, SOC stands for Siblings-on-Cycles),
• and another, SOCadmissible, to verify the admissibility of these graphs as quantum causal structures,
• and the last, SOCgraphviz, to translate adjacency matrices into the Graphviz language.
• The python script /tools/removeiso.py removes isomorphic graphs.

The first two programs are used in support of Conjecture 1 in the article Admissible Causal Structures and Correlations, PRX Quantum 4, 040307 (2023) (arXiv:2210.12796 [quant-ph]).

Installation

First, clone this repository, and then simply run

$ cd soc-observation-code/
$ make

This compiles the programs SOCgen, SOCadmissible, and SOCgraphviz.

Usage

To display help and exit, run the respective program without command-line arguments.

SOCgen

$ ./SOCgen 
Usage: ./SOCgen -n <order> [-r <num>] [--graphviz] [FILTER ...]
       -n <order>     Generate SOCs with `order' connected nodes
       -r <num>       Pick directed graphs at random, and exit after having found `num' SOCs
       --graphviz     Output SOCs in Graphviz format, arcs of common parents are highlighted
       --vector       Output SOCs adjacency vectors in the order (0<-1, 0<-2, ..., 1<-0, 1<-2, ...)
       --all          Allow for disconnected SOCs and disable the degree-order filter (see below)

[FILTER]              Consider only simple directed graphs ...
       -c             ... that are cyclic (i.e., not DAGs)
       --no-sink      ... without sink nodes (this logically implies -c)
       --no-source    ... without source nodes (also this logically implies -c)

This program prints the found SOCs as adjacency matrices to stdout, unless --graphviz has been specified.
To exclude (some) of the isomorphic SOCs, it uses a degree-order filter, unless --all is specified.

SOCadmissible

$ ./SOCadmissible 
Usage: ./SOCadmissible <filename> [<startline> [<endline> | +<count>]]
       <filename>     File name with adjacency matrices of simple directed graphs
       <startline>    Verify graphs starting from line `startline'
       <endline>      Verify graphs up to and including line `endline'
       +<count>       Verify `count' number of graphs

[FILE FORMAT]
       Each line in `filename' must contain the adjacency matrix of a simple directed graph in the format
         {{a00,a01,...},{a10,a11,...},...}  where aij=1 if and only if the graph has the edge i -> j
       The file `filename' may contain graphs with different order (number of vertices)

This program verifies the admissibility of simple directed graphs.

SOCgraphviz

$ ./SOCgraphviz
Usage: ./SOCgraphviz <filename> [night]
       <filename>     File name with adjacency matrices of simple directed graphs

[FILE FORMAT]
       Each line in `filename' must contain the adjacency matrix of a simple directed graph in the format
         {{a00,a01,...},{a10,a11,...},...}  where aij=1 if and only if the graph has the edge i -> j
       The file `filename' may contain graphs with different order (number of vertices)

This program translates to adjacency matrices into the Graphviz format, and prints them to stdout.
Try the optional argument ``night'' for star-constallation-like output.

removeiso.py

$ ./tools/removeiso.py  
Usage: ./tools/removeiso.py -f <filename>

Filters out the isomorphic graphs in `filename'.

This script requires NumPy and NetworkX.

Examples

To generate all SOCs with three nodes, and save them in the file 3.soc, you may run:

$ ./SOCgen -n 3 > 3.soc
Generating SOCs with 3 nodes
100.00%    64/64 (6 SOCs found, 0 seconds, 64.00 graphs/s,  6.00 SOCs/s, 0.00h estimated time left)
Found 6 SOCs in 0 seconds

The admissibility of these graphs can then be checked by running:

$ ./SOCadmissible 3.soc 
Verifying the admissibility of 6 graphs in the file `3.soc' (line 1 to line 6)
100.00%    6/6 (6.00 graphs/s in 0 seconds; current line 6)
These graphs are admissible

The SOCs generated can easily be displayed with the Graphviz tools:

$ ./SOCgraphviz 3.soc | dot | gvpack | circo -Nshape=point -Tx11

also with the --graphviz option:

$ ./SOCgen -n 3 --graphviz | dot | gvpack | neato -Tx11

or in Wolfram Mathematica using:

SOCs = AdjacencyGraph[#] & /@ ToExpression[Import["./3.soc", "List"]];
SOCs = DeleteDuplicatesBy[SOCs, CanonicalGraph];
SOCs

To generate all SOCs with four nodes, save them in the file 4.soc, remove isomorphic ones (as stated below, SOCgen only rudimentary checks for isomorphic graphs), and to display them using Graphviz, you may run:

$ ./SOCgen -n 4 | tee 4.soc | ./tools/removeiso.py -f 4.soc | ./SOCgraphviz /dev/stdin | dot | gvpack | circo -Nshape=point -Tx11

Limitations

In SOCgen, each simple directed graph is represented by a 64bit unsigned integer: This integer is interpreted as a vector of bits, where each bit specifies the absence or presence of a directed edge from one node to another. Since we consider simple directed graphs only (no self-loops), there are n(n-1) possible directed edges, where n is the number of nodes. This means that the largest number of nodes possible is limited by n=8.

While the SOCs generated by SOCgen satisfy some degree-order (see function isdegreeordered(...) in SOCgen.c), SOCgen does not perform graph-isomorphism tests, and may output multiple isomorphic graphs.

License

GPL-3.0-or-later