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. This is achieved using the generateRandomGraph function in Graph.cpp.

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 RegularExpressionGeneration function in graph.cpp is used to generate 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 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

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  --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 --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 --input-file <filename.dot> --output-folder <foldername>

where:

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

Example:

./optlp --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:

/**************************************************************/
/********************         help         ********************/
/ -To generate a random graph: use the options --nb-nodes <n> --nb-edges <m> --nb-labels <l>
 -To extract the optimal solution of a .dot file: use the option -d <filename.dot>
/**************************************************************/