Author: Thibaut de Saivre
A solver for the One-sided crossing minimization problem.
See the PDF report here.
See some python benchmarks here.
The challenge outputs are in the output folder.
Run the CLI solver with the following command:
cargo run --bin ocm-cli -- -a median -v datasets/tiny/complete_4_5.gr
A GTK GUI is available. However, it requires GTK4. Installation instructions are available here. The Rust book of GTK4.
You can then check the gtk version on your machine:
pkg-config --modversion gtk4
Then run the GUI with:
cargo run --release --bin ocm-gtk -- -a median datasets/tiny/complete_4_5.gr
Run the CLI solver for large graphs and time it with:
cargo run --release --bin ocm-cli -- -a median -v datasets/large/25.gr
This project uses cargo workspaces
.
├── datasets # Graph datasets for testing
│ ├── large
│ ├── medium
│ └── tiny
├── ocm-cli # CLI program for solving the OCM problem
├── ocm-gtk # GTK GUI for solving the OCM problem
├── ocm-parser # Graph dataset parser
├── ocm-plotter # Plotting functions
├── ocm-solver # Implementation logic
├── output # Challenge outputs
└── report # LateX report
Various benchmarks are available using tests.
line_sweep_crossings
benchmarked over all datasets, in thecrossings.rs
file.
ISSUE: the benchmarks run very long for 2 of the large dataset files. You can interrupt the benchmark early, as the results are progressively written to the crossings_benchmark.csv
file.
Run them with the following command:
cargo test -- --nocapture # Do not capture stdout so that we can see progress indicators in stdout