Red-blue graph problem solver - Rust implementation

Overview

Red-blue graph problem solver - Rust implementation

The problem is the following:

In a directed graph, each node is colored either red or blue. Furthermore, vertices are also colored red or blue.

When a node is deleted, its adjacent nodes are colored the same color as the vertex which made the link with the node.

What is the maximum uninterrupted sequence we can delete, with k nodes of all the same color ? We cannot delete any node of the other color.

Example

Consider having the following flat graph:

Flat graph example

The color to delete is RED, so we get the following output: [2, 3, 5, 4, 6]

If we analyze the output:

  • We delete the node 2 -> node 1 stays blue and node 3 becomes red.
  • We delete the node 3
  • We delete the node 5 -> node 4 becomes red.
  • We delete the node 4
  • We delete the node 6

Implementation

The purpose of this program is to test which Rust or C++ is the fastest to solve the problem. So I've just translated the C++ code of the red-blue graph proglem solver 1 to Rust. The algorithm has a linear complexity, bast case O(n) and worst case O(3n) = O(n).

Thanks to Marcel for the idea of the algorithm.

Benchmark

Is Rust implementation faster than the C++ one here ?

Method

I ran the benchmark with my personal laptop. Here are the specs:

  • Lenovo Ideapad 720
  • CPU: 4 x Intel Core i5-8250U @ 1.60GHz (8 threads)
  • Cache: 256 Ko, 1 Mo, 6 Mo
  • RAM: 12 GB SO-DIMM DDR4 2400MHz
  • Operating System: Windows 10 Pro
  • Rust compiler: rustc 1.58.0
  • C++ compiler: Microsoft Visual C++ 14 with C++ 17

I also ran tests using Ubuntu 20.04 on WSL 1 using g++ 9.3. For Rust wasm implementation, I used Chrome 97 and Firefox 96 with the same laptop.

Each implementation has been launched 3 times, and I kept the fastest one.

I always compiled code with max performance, so I always used the -O3 flag (release). How much time take each implementation to generate the sequence from a secure random graph of 5 millions nodes (only sequence generation is considered, not graph creation) ?

Results

Implementation Time (ms)
Rust native (Windows) 121.421600
Rust native (WSL Ubuntu) 144.669700
Rust wasm (Chrome) 132.000
Rust wasm (Firefox) 151.000
C++ native (Windows) 442.636
C++ native (WSL Ubuntu) 338.660000

(Significant digits aren't taken into account)

You might also like...
A SIMD implementation of Keccak256 for aarch64, forked from Remco Bloeman's Goldilocks K12 implementation.

keccak256-aarch64 Warning This crate was forked from real cryptographers (Goldilocks by Remco Bloeman), by not a real cryptographer. Do not use this k

Readline Implementation in Rust

RustyLine Readline implementation in Rust that is based on Antirez' Linenoise Supported Platforms Unix (tested on FreeBSD, Linux and macOS) Windows cm

Rust implementation of the termbox library

Rustbox Rustbox is a Rust implementation of termbox. Currently, this is just a wrapper of the C library by nsf, though my plan is to convert it to be

A very fast implementation of tldr in Rust
A very fast implementation of tldr in Rust

A very fast implementation of tldr in Rust: Simplified, example based and community-driven man pages.

A compact implementation of connect four written in rust.
A compact implementation of connect four written in rust.

connect-four A compact implementation of connect four written in rust. Run the game At the moment there no pre-built binaries - but you can build it l

Baby's first Rust CLI project. Basic implementation of grep. Written in about 100 SLOC.

minigrep Coding project from Chapter 12 of the The Rust Programming Language book. Usage Compile and run as so minigrep QUERY FILENAME QUERY being the

An implementation of Verifiable Delay Functions in Rust

Verifiable Delay Function (VDF) Implementation in Rust What is a VDF? A Verifiable Delay Function (VDF) is a function that requires substantial time t

A Decimal Implementation written in pure Rust suitable for financial calculations.

Decimal   A Decimal implementation written in pure Rust suitable for financial calculations that require significant integral and fractional digits wi

Rust implementation of custom numeric base conversion.

base_custom Use any characters as your own numeric base and convert to and from decimal. This can be taken advantage of in various ways: Mathematics:

Owner
Thomas Prévost
Thomas Prévost
RustRedOps is a repository dedicated to gathering and sharing advanced techniques and malware for Red Team, with a specific focus on the Rust programming language. (In Construction)

RustRedOps In Construction.... The project is still under development Overview RustRedOps is a repository that houses various tools and projects relat

João Victor 17 Dec 14, 2023
Benchmarking C, Python, and Rust on the "sp" problem

Fast SP Various implementations of the problem in this blog post. Requirements To run this, you will need Rust Nightly and Python 3.8+ with numpy. Rus

Eddie Antonio Santos 2 Jul 13, 2023
Proof-of-concept on how to solve Bitcoin's light node sync problem with zkSNARKs

BTC Warp Prove and verify the longest Bitcoin PoW chain BTC Warp is a proof-of-concept system that aims to solve the client-syncing problem for Bitcoi

Succinct 45 May 31, 2023
Sudoku Solver using bitmasks and bit-manipulation with Rust 🦀 and egui 🎨

sudoku-solver Download This Rust application implements a very memory efficent algorithm to solve sudoku and lets the user know when a unique solution

cameron 24 Apr 10, 2023
🧮 Writing an Equation Solver

Writing an Equation Solver Writing an Equation Solver is a process that is made of: parsing, equating/unifying and rewriting. Equating: it's the step

Gabrielle Guimarães de Oliveira 16 Aug 7, 2023
An optimizing IK solver based on the Lie group of rigid transforms SE(3)

OptIK A fast inverse kinematics solver for arbitrary serial chains, providing Rust and Python programming interfaces. The implementation is similar to

Kyle Cesare 17 Oct 5, 2023
The module graph logic for Deno CLI

deno_graph The module graph/dependency logic for the Deno CLI. This repository is a Rust crate which provides the foundational code to be able to buil

Deno Land 67 Dec 14, 2022
Gping - Ping, but with a graph

gping ?? Ping, but with a graph. Table of Contents Install ?? Usage ?? Install ?? macOS Homebrew: brew install gping MacPorts: sudo port install gping

Tom Forbes 7k Dec 30, 2022
A general-purpose, transactional, relational database that uses Datalog and focuses on graph data and algorithms

cozo A general-purpose, transactional, relational database that uses Datalog for query and focuses on graph data and algorithms. Features Relational d

null 1.9k Jan 9, 2023