A length limited path counter.
A simple make in the main directory should suffice to build TL;DC and (most) of its dependencies.
Running make will provide a binary a.out in the root directory of this repository and a binary (the same) tldc in the build directory.
The only dependencies that this does not provide are GMP and boost. You need to install them by hand.
On Ubuntu this works via sudo apt install libgmp-dev libboost-dev.
TL;DC accepts path counting instances in DIMACS format from ICGCA:
Each line begins with a letter that defines the rest of the line. The legal lines are:
c Comment:the remainder of the line is ignored.
p Problem: must be of form p edge n m where n is the number of nodes (to be numbered 1..n) and m the number of edges.
e Edge (for undirected graphs): must be of form e v1 v2 where v1 and v2 are the endpoints of the edge.
a Arc (for directed graphs): must be of form a v1 v2 where v1 and v2 are the stand and endpoint of the arc.
l Length: must be of form l len where len is the maximum path length (the number of edges on the path).
t Terminals: must be of form t v1 v2 where v1 and v2 are the path terminals.
Instances must be given to TL;DC via stdin.
TLDC "Too long; Didn't Count" A length limited path counter.
Copyright (C) 2023-2024 Rafael Kiesel, Markus Hecher
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
Usage: tldc [-s .] [-t .] [-m .] [-d] [-h]
-s --strategy STRATEGY use STRATEGY.
Must be one of:
* auto: choose automatically (default)
* pathfbs: frontier-based search along a path decomposition
* nautyfbs: frontier-based search along a path decomposition with modulo automorphisms
* treefbs: frontier-based search along a tree decomposition
* branchfbs: frontier-based search along a branch decomposition
* nautydfs: depth first search with modulo automorphisms
* dfs: depth first search
* mitm: meet in the middle search
-t --threads NUM use NUM threads.
-m --memory_limit LIMIT set a hardlimit of LIMIT MB memory.
-d --directed expect a directed instance
-h --help print this help.
Typical calls to TL;DC might look something like this:
./tldc -m 10000 < instances/one_pair/000.col
calls tldc with a memory limit of 10000 MB, all available threads, and an automatically chosen strategy on the instance in file instances/one_pair/000.col.
./tldc -t 1 -s nautydfs < instances/one_pair/002.col
calls tldc without a memory limit, one thread, and strategy nautydfs on the instance in file instances/one_pair/000.col.
Especially the strategy option is worth varying, although the portfolio of the 2024 version should generalize rather well.
The 2023 version has support for the all pairs path counting problem. For the 2024 version this was not explicitly maintained and might have broken. If you need this feature please either contact us or use the 2023 version.
For a description of the solver and the techniques that were used see the short abstract (2024,2023) or the slides (2024,2023) of the presentation.
TL;DC makes multiple assumptions about limits on graphs:
- When using path/treewidth: there is a decomposition of width less than 2^8 - 2 = 254.
- When using path/treewidth in the directed case: there is a decomposition of width less than 2^7 - 2 = 126
Should these assumptions not be given the corresponding datatypes need to be changed.