Prime Path Generator is a prime path generator used to generate prime paths.

Overview

Prime Path Generator

GitHub license GitHub last commit Code style: black Total alerts Language grade: Python CodeFactor

Prime Path Generator is a prime path generator used to generate prime paths.

It is aimed to be faster than brute-force method.

What is prime path

A path p is prime if p is a maximal simple path, i.e. p cannot be extended without losing simplicity.

How does this tool work faster

The brute-force method

The brute-force method is:

  1. generate all simple paths
  2. check every simple path to get prime paths

It contains a lot of unnecessary steps. For example:

0 → 1
↓   ↓
2 → 3

There are only two prime paths 013 023. But the brute-force method will check 0 1 2 3 01 02 13 23 013 023.

We can do better

This tool will not check all simple paths. It focuses on the vertices with 0 indegree or 0 outdegree:

0 → 1{3}
↓
2{3}
0{13, 23}
{013, 023}

What about cycles

0 → 1
↑   ↓
3 ← 2

The brute-force method will check 0 1 2 3 01 ...

But this tool knows that there are 4 prime paths in a 4-length cycle:

[01230]123
0[12301]23
01[23012]3
012[30123]

What about mixed paths

0 → 1 → 4
↑   ↓
3 ← 2

step 1

0 → 1{4}
↑   ↓
3 ← 2

step2

As a cycle:

0 → 1
↑   ↓
3 ← 2
[01230]123
0[12301]23
01[23012]3
012[30123]

step3

As not a cycle:

0 → 1{4}
↑
3 ← 2
23014

The full algorithm is a bit more complicated. See the source code if you are curious.

Why is the result right

There is no formal proof yet.

The unit tests show that this tool generates the same result as the brute-force method, at least for test data.

Alternatives

'ToolBurnt' A Set Of Tools In One Place =}

'ToolBurnt' A Set Of Tools In One Place =}

MasterBurnt 5 Sep 10, 2022
ticktock is a minimalist library to view Python time performance of Python code.

ticktock is a minimalist library to view Python time performance of Python code.

Victor Benichoux 30 Sep 28, 2022
tade is a discussion/forum/link aggregator application. It provides three interfaces: a regular web page, a mailing list bridge and an NNTP server

tade is a discussion/forum/link aggregator application. It provides three interfaces: a regular web page, a mailing list bridge and an NNTP server

Manos Pitsidianakis 23 Nov 04, 2022
A small utility that sorts your files.

FileSorter A small utility that sorts your files. TODO: Scan directory to find files(thanks @corruptmemry for this!) Split extensions to determine fil

2 Jun 16, 2022
An OData v4 query parser and transpiler for Python

odata-query is a library that parses OData v4 filter strings, and can convert them to other forms such as Django Queries, SQLAlchemy Queries, or just plain SQL.

Gorilla 39 Jan 05, 2023
Networkx with neo4j back-end

Dump networkx graph into nodes/relations TSV from neo4jnx.tsv import graph_to_tsv g = pklload('indranet_dir_graph.pkl') graph_to_tsv(g, 'docker/nodes.

Benjamin M. Gyori 1 Oct 27, 2021
Experimental python optimistic rollup fraud-proof generation

Macula Experimental python optimistic rollup fraud-proof generation tech by @protolambda. Working on a python version for brevity and simplicity. See

Diederik Loerakker 30 Sep 01, 2022
Just some scripts to export vector tiles to geojson.

Vector tiles to GeoJSON Nowadays modern web maps are usually based on vector tiles. The great thing about vector tiles is, that they are not just imag

Lilith Wittmann 77 Jul 26, 2022
A tool written in python to generate basic repo files from github

A tool written in python to generate basic repo files from github

Riley 7 Dec 02, 2021
A toolkit for writing and executing automation scripts for Final Fantasy XIV

XIV Scripter This is a tool for scripting out series of actions in FFXIV. It allows for custom actions to be defined in config.yaml as well as custom

Jacob Beel 1 Dec 09, 2021
Fuzzy box is a quick program I wrote to fuzz a URL that is in the format https:// url 20characterstring.

What is this? Fuzzy box is a quick program I wrote to fuzz a URL that is in the format https://url/20characterstring.extension. I have redacted th

Graham Helton 1 Oct 19, 2021
Display your calendar on the wallpaper.

wallCal Have your calendar appear as the wallpaper. disclaimer Use at your own risk. Don't blame me if you miss a meeting :-) Some parts of the script

7 Jun 14, 2022
Monte Carlo simulation of 3G rules

mc3g Monte Carlo simulation of 3G rules This project contains the Python code to do simulations of events according to the 3G rule (in German: "Geimpf

Jan Christoph Terasa 4 Nov 01, 2021
Stubmaker is an easy-to-use tool for generating python stubs.

Stubmaker is an easy-to-use tool for generating python stubs. Requirements Stubmaker is to be run under Python 3.7.4+ No side effects during

Toloka 24 Aug 28, 2022
A quick random name generator

Random Profile Generator USAGE & CREDITS Any public or priavte demonstrative usage of this project is strictly prohibited, UNLESS WhineyMonkey10 (http

2 May 05, 2022
✨ Un générateur de lien raccourcis en fonction d'un lien totalement fait en Python par moi, et en français.

Shorter Link ❗ Un générateur de lien raccourcis en fonction d'un lien totalement fait en Python par moi, et en français. Dépendences : pip install pys

MrGabin 3 Jun 06, 2021
Conveniently measures the time of your loops, contexts and functions.

Conveniently measures the time of your loops, contexts and functions.

Maciej J Mikulski 79 Nov 15, 2022
Airspy-Utils is a small software collection to help with firmware related operations on Airspy HF+ devices.

Airspy-Utils Airspy-Utils is a small software collection to help with firmware related operations on Airspy HF+ devices on Linux (and other free syste

Dhiru Kholia 11 Oct 04, 2022
Basic loader is a small tool that will help you generating Cloudflare cookies

Basic Loader Cloudflare cookies loader This tool may help some people getting valide cloudflare cookies Installation 🔌 : pip install -r requirements.

IHateTomLrge 8 Mar 30, 2022
A program will generate a eth key pair that has the public key that starts with a defined amount of 0

ETHAdressGenerator This short program will generate a eth key pair that has the public key that starts with a defined amount of 0 Requirements Python

3 Nov 19, 2021