optlp

git clone --recursive https://depot.lipn.univ-paris13.fr/PMC-SOG/optlp

Description

This program allows users to either generate a random graph or extract the optimal solution of a graph from a .dot file. It provides the following functionalities:

1. Generate a Random Graph: Users can specify the number of nodes, edges, and labels to generate a random, deterministic, and connected graph.

2. Extract Optimal Solution from a .dot File: Users can provide a .dot file to extract and optimize the graph.

After generating the graph or loading it from a file, the program performs the following steps:

1. Generate Regular Expression of the Graph: The tool generates the regular expression of the graph.

2. Extract All Paths from the Regular Expression: All the paths of the graph are extracted from the regular expression.

3. Pass to the Integer Linear Program:

   • Variables: Paths of the graph.
   • Constraints: Labels representing transitions in the graph.

Constraints

Each constraint represents a transition in the graph, so the number of constraints equals the number of transitions. Each constraint must be greater than or equal to 1, ensuring that each transition belongs to at least one path.

Variables

• x: A path in the graph.
• a: Coefficient indicating the number of occurrences of the transition in the path.

Objective Function

The coefficients of profit represent the lengths of the paths. The objective function minimizes the cost of coverage by reducing the sum of the lengths of the selected paths.

Requirements

Make sure to install the necessary dependencies before running the program:

• gcc >= 9.3.0
• cmake >= 3.18
• ninja

Build

The tool can be compiled as follows:

mkdir build
cmake -S . -B build -G Ninja         # configures the project
cmake --build build --target all -j  # builds the project using all available CPU cores
cmake --install build                # installs the project: ./assets/optlp

Run

Once installed, the binary optlp will be in the assets folder.

cd assets
./optlp

Usage

Generating a Random Graph

To generate a random graph, use the following options:

./optlp  random --nb-nodes <n> \
                --nb-edges <m> \
                --nb-labels <l>

where:

• --nb-nodes <n>: Specifies the number of nodes in the graph.
• --nb-edges <m>: Specifies the number of edges in the graph.
• --nb-labels <l>: Specifies the number of labels in the graph.

Example:

./optlp random --nb-nodes 200 --nb-edges 100 --nb-labels 20

Extracting the Optimal Solution from a .dot File

To extract the optimal solution of a graph from a .dot file, use the following option:

./optlp from-file --input-file <filename.dot> --output-folder <folder name>

where:

• --input-file <filename.dot>: Specifies the .dot file containing the graph.
• --output-folder <folder name>: Specifies the folder containing the result.

Example:

./optlp from-file --input-file ./toys_examples/graph3.dot --output-folder ./result/

Help

If no options are provided or the help option is specified, the program will display a help message with usage instructions.

./optlp --help

The help message will display the following:

❯ ./assets/optlp --help
OptLP: A tool to find the minimum number of shortest paths that cover all system actions
Usage: ./assets/optlp [OPTIONS] [SUBCOMMAND]

Options:
  -h,--help                   Print this help message and exit

Subcommands:
  random                      Generate a random LTS
  from-file                   Load an LTS from a dot file