Merge branch 'main' of https://github.com/jreeves3/BiPartGen-Artifact

jreeves3 · Mar 19, 2021 · cceb5e0 · cceb5e0
2 parents 220679a + cd7a873
commit cceb5e0
Show file tree

Hide file tree

Showing 19 changed files with 484 additions and 130 deletions.
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,63 @@
+# Latex
+*.pdf
+
+# Mac and dev
+*.swp
+*.swo
+*.DS_Store
+
+# Compiled files
+bipartgen
+
+# Prerequisites
+*.d
+
+# Object files
+*.o
+*.ko
+*.obj
+*.elf
+
+# Linker output
+*.ilk
+*.map
+*.exp
+
+# Precompiled Headers
+*.gch
+*.pch
+
+# Libraries
+*.lib
+*.a
+*.la
+*.lo
+
+# Shared objects (inc. Windows DLLs)
+*.dll
+*.so
+*.so.*
+*.dylib
+
+# Executables
+*.exe
+*.out
+*.app
+*.i*86
+*.x86_64
+*.hex
+
+# Debug files
+*.dSYM/
+*.su
+*.idb
+*.pdb
+
+# Kernel Module Compile Results
+*.mod*
+*.cmd
+.tmp_versions/
+modules.order
+Module.symvers
+Mkfile.old
+dkms.conf
diff --git a/README.md b/README.md
@@ -5,13 +5,14 @@ Generate bipartite graphs and the associated CNF formulas
 ```bash
 General Options
 -g [chess|pigeon|random]       Type of graph to generate.
--n [Int]                       Size of chess NxN, number of holes in PHP N, or number of nodes in random graph.
--e [direct|split|sinz|mixed]   At Most 1 encoding, mixed uses random encoding for each node independently.
+-n [Int]                       Size of smaller partition in graph, or nxn board for chess?.
+-e [direct|linear|sinz|mixed]  At-Most-One encoding, mixed randomly selects encoding for each node.
 -f [FNAME]                     Filename to write cnf formula in dimacs format.
 -s [Int]                       Seed for random number generator.
--M                             At Most 1 encoding applied also to both partitions.
--L                             At Least 1 encoding applied also to both partitions.
+-M                             At-Most-One encoding applied also to both partitions.
+-L                             At-Least-One encoding applied also to both partitions.
 -E [Int]                       Number of edges in random graph.
+-v                             Verbose (display density of generated bipartite graph).
 
 Mchess Additional Options
 -C [NORMAL|TORUS|CYLINDER]  Type of mutilated chessboard.
@@ -21,30 +22,40 @@ Random Graph Additional Options
 -c [Int]           Difference in number of nodes between partitions.
 
 PGBDD Variants
--p                 Bucket and variable ordering for Sinz encoding
--o                 Variable ordering for either Sinz or split encoding
+-p                 Bucket and variable ordering for Sinz encoding (FNAME_bucket.order, FNAME_variable.order).
+-o                 Variable ordering for either Sinz or linear encoding (FNAME_variable.order).
 
 Symmetry-Breaking Clauses
 -b ...
 
 ```
 
-scripts: scripts to generate formulas.
+## scripts
+Scripts to generate a subset of benchmark formulas.
+* random - random graphs with 130 edges, n from [11,20], encodings from [direct,sinz,linear,mixed], -A (default) and -B (Exactly-One) constraints
+* randomPGBDD - random graphs with 130 edges, n from [11,20], encodings from [sinz,linear], -A (default) constraints, bucket permutation (-Sched) and variable ordering (-Ord) options. (Note: this outputs .._variable.order, .._bucket.order files with usecase shown in the example section below)
+* symmetry-breaking - 
 
 
-data: Excel spreadsheet with data labeled by Figure in the paper.
+## data 
+Excel spreadsheets (Random Experiments, Symmetry-Breaking Experiments) with sheets labeled by Figure #.
 
+## Solvers
+* [Kissat](https://github.com/arminbiere/kissat)
+* [Lingeling](https://github.com/arminbiere/lingeling)
+* [SaDiCaL](http://fmv.jku.at/sadical)
+* [PGBDD](https://github.com/rebryant/pgbdd)
 
 ## Example
 ```bash
-# Mutilated chessboard with 
+# Mutilated chessboard nxn with direct encoding
 > ./bipartgen -g chess -f chess4 -n 4 -e direct
 
 # Pigeonhole with 8 holes, 9 pigeons, with exactly one constraints for each node using sinz
 > ./bipartgen -g pigeon -f pigeon8 -n 8 -e sinz -M -L
 
-# Random graph with 15 edges using split encoding
-> ./bipartgen -g random -f random -n 6 -e split -E 15
+# Random graph with 15 edges using linear encoding
+> ./bipartgen -g random -f random -n 6 -e linear -E 15
 
 ```
 ## Running PGBDD Variants

diff --git a/experiment-data/experimentCSV.zip b/experiment-data/experimentCSV.zip
diff --git a/experiment-data/experimentSpreedSheet.zip b/experiment-data/experimentSpreedSheet.zip
diff --git a/experiment-data/random-experiments.xlsx b/experiment-data/random-experiments.xlsx
diff --git a/scripts/random.sh b/scripts/random.sh
@@ -0,0 +1,24 @@
+#!/bin/sh
+
+dir=`dirname $0`
+mkdir -p $dir"/random130"
+
+edgeCount=130
+
+for encoding in "direct" "sinz" "linear" "mixed"
+do
+    mkdir -p $dir"/random130/"$encoding
+
+    for n in {11..20}
+    do
+      out="random130/"$encoding"/A"$n
+      echo $out
+      ./../bipartgen -g random -n $n -f $out -e $encoding -E $edgeCount -v
+
+      out="random130/"$encoding"/B"$n
+      echo $out
+      ./../bipartgen -g random -n $n -f $out -e $encoding -E $edgeCount -M -L -v
+
+    done
+done
+
diff --git a/scripts/randomPGBDD.sh b/scripts/randomPGBDD.sh
@@ -0,0 +1,28 @@
+#!/bin/sh
+
+dir=`dirname $0`
+mkdir -p $dir"/randomPGBDD130Ord"
+
+edgeCount=130
+
+for encoding in "sinz" "linear"
+do
+    mkdir -p $dir"/randomPGBDD130Ord/"$encoding
+
+    for n in {11..20}
+    do
+      out="randomPGBDD130Ord/"$encoding"/A"$n
+      echo $out
+      ./../bipartgen -g random -n $n -f $out -e $encoding -E $edgeCount -v -o
+
+    done
+done
+
+mkdir -p $dir"/randomPGBDD130Sched/"
+
+for n in {11..20}
+  do
+    out="randomPGBDD130Sched/A"$n
+    echo $out
+    ./../bipartgen -g random -n $n -f $out -e sinz -E $edgeCount -v -p
+done
diff --git a/src/additionalgraphs.c b/src/additionalgraphs.c
@@ -1,3 +1,21 @@
+/**********************************************************************************
+ Copyright (c) 2021 Joseph Reeves and Cayden Codel, Carnegie Mellon University
+ 
+ Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+ associated documentation files (the "Software"), to deal in the Software without restriction,
+ including without limitation the rights to use, copy, modify, merge, publish, distribute,
+ sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+ The above copyright notice and this permission notice shall be included in all copies or
+ substantial portions of the Software.
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+ NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+ OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ **************************************************************************************************/
+
+
 /** @file additionalgraphs.c
  *  @brief Instance generator for additional graphs.
  *

diff --git a/src/additionalgraphs.h b/src/additionalgraphs.h
@@ -1,3 +1,21 @@
+/**********************************************************************************
+ Copyright (c) 2021 Joseph Reeves and Cayden Codel, Carnegie Mellon University
+ 
+ Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+ associated documentation files (the "Software"), to deal in the Software without restriction,
+ including without limitation the rights to use, copy, modify, merge, publish, distribute,
+ sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+ The above copyright notice and this permission notice shall be included in all copies or
+ substantial portions of the Software.
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+ NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+ OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ **************************************************************************************************/
+
+
 /** @file additionalgraphs.h
  *  @brief Instance generator for additional graphs.
  *