Skip to main content

Visualizing Dynamic Programming on Tree Decompositions.

Project description


Maintenance PyPI license Tests codecov

GitHub release (latest SemVer including pre-releases) PyPI version PyPI status PyPI pyversions PyPI - Wheel GitHub repo size GitHub code size in bytes GitHub commits since latest release (by SemVer)

Visualization for dynamic programming on tree decompositions.

Create a graph object for each given graph that is of interest for the dynamic programming.

The visualization generates highlights and adds solution-tables for user defined time steps.

These snapshot of the graphs will be written in a graphviz-supported file-format to a folder of your choosing.

For the portable and light weight '.svg' format, all graphs for a timestep can be joined together to provide a thoroughly view on the process of dynamic programming.

With the '.svg' format the images are highly customizable, and even combining several timesteps together using svg animate would be an option in the future.


Alubbock:Graphviz (or Graphviz (>=2.38))


for dpdb: psycopg2 (2.8.5)

To register the graphviz plugins

dot.exe -c

To install

In a command prompt with pip (to get pip see: installed: Just run

pip install -h (for more information on install options)
pip install tdvisu

To download the latest version from the default branch:

git clone --depth 1 --single

To isolate the dependencies

With virtualenv on the system installed you can isolate the environment, for example

virtualenv tdvisu_dir -p 3.8
cd tdvisu_dir/bin/
source activate

With Conda on the system installed the dependencies for this project can be automatically installed in a new environment:

Go to the projects base directory.

Open a conda-command-prompt with admin privileges and run the commands from the project folder

  • to create a new environment with basic dependencies:
conda env create -f .\environment.yml
  • to activate the environment:
conda activate tdvisu

Install from source

To clone the complete repository:

git clone

To download only the latest version from the default branch:

git clone --depth 1 --single

To install the project from the source folder:

pip install -h (for more information on install options)
pip install .

to confirm that the visualization finds all dependencies:

python .\tdvisu\ -h

to run all tests:

pip install .[test] 
pytest .\test\

How to use

The visualization needs input in the form of the Json API. The creation of this file is exemplary implemented in or the fork GPUSAT and --visufile filename (optionally disabling preprocessing with -p).

Run the python file with the above dependencies installed: takes two parameters, the json-infile to read from, and optionally one outputfolder. With both arguments a call from IPython might look like this:

args='visugpusat.json examplefolder')

For #SAT it produces for example three different graphs suffixed with a running integer to represent timesteps:

  • TDStep the tree decomposition with solved nodes
  • PrimalGraphStep the primal graph with currently active variables highlighted
  • IncidenceGraphStep the bipartite incidence graph with active clauses/variables highlighted

The graphs are images encoded in resolution independent .svg files (see

How to use

After installing the project dp_on_dbs with the there listed requirements, we need to

  • edit the database.ini with our password to postgresql
    • for the problem VertexCover
      • with flag --gr-file to store the htd Input (if the input was in a different format)
    • for the problem SharpSat
      • with flag --store-formula to store the formula in the database
  • Run
    • Sat / SharpSat: python [PROBLEMNUMBER]
    • VertexCover: python [PROBLEMNUMBER] --twfile [TWFILE] with the file in DIMACS tw-format containing the edges of the graph.

Installation of the psycopg2 package


For example on linux today this might need sudo apt install libpq-dev before completion.

New Release


  • Bump / according to the changes made
  • Change date to the release day, keep format


In case dependencies have changed, or just to update some, check

  • requirements.txt
  • stable-requirements.txt (using pip freeze)


  • Add tag with link (see bottom for linking examples)
  • Add changes, maybe some are already in Unreleased
  • Update Unreleased with (No) unreleased changes

Review code

  • Run tests (pytest)
  • Check codestyle (pylint)


  • Push changes to master
  • Wait for all automated checks! (All checks have passed...)

Create Release

  • On the GitHub page go to: Release, Draft a new release
  • Enter v'YOUR VERSION NUMBER' as the tag.
  • Add a Release Title (could be just the version)
  • Add some description (like in the
  • Click on Publish release on the bottom

Should automatically release to PyPI

Now you are set for the new release :tada:


All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.


  • No unreleased changes yet.

1.1.8 - 2021-05-04


  • Updated pyyaml from 5.3.1 to 5.4 #33
  • Updated py from 1.9.0 to 1.10.0 #35
  • Fixed python-app.yml #34

1.1.7 - 2020-09-13


  • Better tests around the (Dimacs) Reader


  • Improved the SQL queries with explicit formats #32
  • Improved Readme sections for install and usage

1.1.6 - 2020-08-01


  • Added better property based testing with hypothesis #29
  • Added jobs and setups to test on macos and windows #31


  • do_sort_nodes now sorts in correct numeric order. commit cdfcf6
  • Fixed some import orders

1.1.5 - 2020-07-17


  • Added many new tests.
  • Hints for not covered code lines.


  • Simplified code to parse commandline flags while removing duplications in code.
  • Entrypoint for modules visualization and construct_dpdb_visu is now in init().
  • Some improvements in utilities.solution_node

1.1.4 - 2020-07-14


  • Added the possibility to specify and create multiple graph-visualizations in one file #25
  • Added test case test_vc_multiple_and_join in commit aa31901
  • Added test cases for construct_dpdb_visu
  • Add pytest-mock to tests_require


  • Simplified and refactored TDVisu.schema.json
  • Schema now includes possibility to specify multiple instances of generalGraph and incidenceGraph
  • Revisited doc/ to now include all parameters available
  • Renamed test folder expected_images to expected_files
  • Updated stable-requirements.txt
  • Several minor improvements

1.1.3 - 2020-07-09


  • Added TDVisu.schema.json to validate the Json-API for TDVisu #24
  • Added 'col' to allowed formats in tw reader (default string in Mathematica)


  • Fixed error where database configuration was not found in the directory
  • Fixed missing double quotation marks in
  • Moved → doc/


  • Removed generalGraph and incidenceGraph from required arguments in API

1.1.2 - 2020-06-26


  • Tests for using graphviz in the Github Action too
  • Tests for


  • Fixed typo that prevented joining SVG in visualization
  • Fixed cases where logging.yml was not found in the working directory
  • Now using pathlib.Path for most file-related operations
  • Unified logging configuration in utilities and made it easier to work with #22
  • Added more type hints and improved existing ones

1.1.1 - 2020-06-25


  • Added problem type Sat to tdvisu/
  • Added testcases in file test/


  • is now updated with snake_case names and consistent with
  • Fixed default value for svg-join v_top to None from 'top'
  • Improved flexibility in several function parameters
  • Improved documentation and comments in several places
  • Fixed passing parameters to method setup_tree_dec_graph


  • Removed old dependency from tdvisu/ on utilities

1.1.0 - 2020-06-07


  • Added file with several static or shared things like

    • Methods:
      • flatten
      • read_yml_or_cfg combining yaml, json, cfg reader in one
      • logging_cfg configure logging with file or DEFAULT_LOGGING_CFG
      • helper convert_to_adj from
      • add_edge_to (edges and adj list)
      • gen_arg infinite Generator
    • Styles:
      • base_style, emphasise_node, style_hide_node, style_hide_edge
    • Graph manipulation:
      • bag_node
      • solution_node
  • Added file logging.yml (and .ini) with logging configuration for the module #20

  • Added half the tests for


  • Changed path of image SharpSatExample to the absolute URL for PyPI.
  • Changed names of loggers to absolute name. Should be easy to adjust if needed.
  • Changed logging defaults and config in tdvisu/ and
  • Updated ArgumentParser help
  • Some fixes of code-style or variable names.

1.0.1 - 2020-06-04



  • Changed path of image SharpSatExample to the absolute URL for PyPI.

1.0.0 - 2020-06-04


  • Added svgjoin parameters to JsonAPI #6
  • Added call to svgjoin from
  • Added workflow to display the sourcecode-files in DIRECTORY


  • Moved JsonAPI and conda_packages to /doc
  • Updated arguments in svgjoin to be more flexible for multiple joins #11
  • Fixed scaling mechanism in svgjoin #13
  • Changed tests from unittest to pytest #12


  • Changelog in

0.5.1 - 2020-06-01


  • Added publishing Action to PyPI #4


  • Changed with more documentation and simpler functionality.
  • Updated Readme with a guide on how to use construct_dpdb_visu #2


  • Removed publishing Action to testpypi #4

0.5.0-dev1 - 2020-06-01


  • Development version; beginning of the repository #1
  • Added
  • Added module-name to imports
  • Added README to tdvisu directly


  • Fixed usage of __version__ in tdvisu/


  • Removed individual versioning

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

tdvisu-1.1.8.tar.gz (49.7 kB view hashes)

Uploaded source

Built Distribution

tdvisu-1.1.8-py3-none-any.whl (63.1 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page