This Markdown file contains usage and build information. For evaluation results, including the required plots, see EVALUATION.md.
- Java 17 or higher (tested with Java 17.0.7)
java -jar treewidth.jar --help
java -jar treewidth.jar gen --help
java -jar treewidth.jar order --help
java -jar treewidth.jar decomp --help
java -jar treewidth.jar eval --help
Generates a series of
The output graphs will be in the prescribed CSV format and be named graph_n<n>_p<p>_<i>.csv
where <n>
is the <p>
is the <i>
is the ascending instance number.
java -jar treewidth.jar gen <outputDir> -n <n> [<n> ...] -p <p> [<p> ...] -c <count> [--help]
-
<outputDir>
- A path to a directory where the generated graphs will be stored. Must be either non-existent or empty. -
<n>
- Values ofto use. Can be repeated to specify multiple values. -
<p>
- Values ofto use. Can be repeated to specify multiple values. Use the English format, e.g., 0.123
. -
<count>
- The number of graphs to generate for eachcombination.
Example:
java -jar treewidth.jar gen graphs -n 10 100 1000 -p 0.25 0.5 0.75 -c 100
Generates an elimination ordering for a given graph.
The input graph must be in the prescribed CSV format. The output ordering is printed to STDOUT as a space-separated list of vertex labels.
java -jar treewidth.jar order <graphPath> -r <heuristic> [--help]
<graphPath>
- A path to an input graph.<heuristic>
- The heuristic to use. Must be one of the following:mindeg
- Minimum-Degree heuristicminfill
- Minimum-Fill-In-Edges heuristicmaxcard
- Maximum Cardinality Search heuristic
Example:
java -jar treewidth.jar order graphs/graph_n0100_p750_001.csv -r mindeg
Generates a tree decomposition for a given graph and an elimination ordering of its vertices.
The input graph must be in the prescribed CSV format and the elimination ordering must be a valid ordering for the input graph and in space-separated list format. The output decomposition will be in the prescribed CSV bag-based format and printed to STDOUT.
java -jar treewidth.jar decomp <graphPath> <orderingPath> [-y] [--help]
<graphPath>
- A path to an input graph.<orderingPath>
- A path to an input elimination ordering. You can use-
to read from STDIN instead.-y
- Enable verification. The produced tree decomposition will be tested for validity (tree, vertices covered, edges covered, connected subtrees) and no decomposition will be output if it is not valid (an error message will be printed to STDERR instead).
This command can be chained with the order
command if an elimination ordering has not been computed yet:
java -jar treewidth.jar order <graphPath> -r <heuristic> | java -jar treewidth.jar decomp <graphPath> -
Example:
java -jar treewidth.jar order graphs/graph_n0100_p750_001.csv -r mindeg | java -jar treewidth.jar decomp graphs/graph_n0100_p750_001.csv -
Generates a list of treewidths as computed by the three treewidth heuristics (min-degree, min-fill, max-cardinality) for a given set of graphs.
The input graphs must be in the prescribed CSV format and have filenames similar to the one generated by the gen
command, i.e., graph_n<n>_p<p>_<i>.csv
. The output consists of a CSV-format treewidth report for each input graph as well as the mean and median treewidth for each heuristic on the given graph set and will be printed to STDOUT.
java -jar treewidth.jar eval <inputDir> -p <prefix> [--help]
<inputDir>
- A path to a directory to retrieve the graph instances from.<prefix>
- The prefix for the graph instances to use. Will be stripped from filenames to determine the instance names. Required, so use a string like"graph_n0100_p750_"
.
Example:
java -jar treewidth.jar eval graphs -p graph_n0100_p750_ | tee results/graph_n0100_p750.csv
- Java 17 or higher
- Maven 3.2.5 or higher
Tested with:
$ mvn --version
Apache Maven 3.6.0
Maven home: /usr/share/maven
Java version: 17.0.7, vendor: Private Build, runtime: /usr/lib/jvm/java-17-openjdk-amd64
Default locale: en, platform encoding: UTF-8
OS name: "linux", version: "4.4.0-22621-microsoft", arch: "amd64", family: "unix"
mvn clean package
The resulting JAR can be found as:
target/treewidth-heuristics-1.0-SNAPSHOT.jar
You can then proceed to use this JAR as with the pre-packaged version as outlined under Usage.