An implementation for the persistent phylogeny polynomial-time algorithm described the article Solving the Persistent Phylogeny Problem in polynomial time.
- gcc 5.0 and above
- Boost libraries
N.B. Skip this block if you already have Boost on your system
Popular Linux and Unix distributions such as Fedora, Debian, and NetBSD include pre-built Boost packages.
Debian example:
# apt install libboost-all-dev
Download Boost.
N.B. Skip this step if you already built Boost on your system
This implementation uses Boost.ProgramOptions to parse command line arguments and options, which means it needs separately-compiled library binaries to work.
NB. Skip this step if you already updated your platform's environment variable
Moreover, on Unix systems, you may need to prepare plaform-specific settings (since Boost.ProgramOptions is a shared library).
- Follow the steps at boost.org
$ git clone https://github.com/dcasella/persistent-phylogeny.git
$ cd persistent-phylogeny
$ make
ppp [OPTION...] FILE...
ppp corresponds to the executable binary.
OPTION is a list of options - can be omitted.
FILE is a list of file paths (1 or more).
-h or --help
Display this message.
-v or --verbose
Display the operations performed by the program.
-t or --testpy
Test the output of the algorithm with check_reduction.py. This can be used to make sure the output of the program is correct. Don't use this option when benchmarking; the Python script takes time to complete.
-x or --exponential
Exponential version of the algorithm.
This option can be used to test every possible combination of safe sources.
It is also mutually exclusive with --interactive and --nthsource.
-i or --interactive
User input driven execution.
This option can be used to manually select which safe source to realize.
It is also mutually exclusive with --exponential and --nthsource.
-m or --maximal
Run the algorithm on the maximal subgraph instead of the full graph.
This is done by calculating a maximal reducible graph before running the algorithm.
-n N or --nthsource N
Select the nth safe source when possible (default 0 - the option can be omitted).
This option can be used to automatically select the nth safe source to realize (instead of manually selecting it each time with --interactive).
It is also mutually exclusive with --exponential and --interactive.
$ ./bin/ppp FILE...
The program will call the reduce function on each graph read from the files.
Examples:
Listing the single files
$ ./bin/ppp file1 dir1/file2 dir1/file3
Or with globs (if your shell supports it)
$ ./bin/ppp dir1/*
Or with options (order doesn't matter - still supports globs)
$ ./bin/ppp -m -v file1
The first line must contain the size of the matrix.
Empty lines (after the first) are ignored.
Subsequent lines represent the matrix itself.
N M
Matrix made up of space-separated boolean values
Example:
6 3
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0