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

Dill_tils is a package that has my commonly used functions inside it for ease of use.

DilllonB07 Utilities Dill_tils is a package that has my commonly used functions inside it for ease of use. Installation Anyone can use this package by

Dillon Barnes 2 Dec 05, 2021
A script copies movie and TV files to your GD drive, or create Hard Link in a seperate dir, in Emby-happy struct.

torcp A script copies movie and TV files to your GD drive, or create Hard Link in a seperate dir, in Emby-happy struct. Usage: python3 torcp.py -h Exa

ccf2012 105 Dec 22, 2022
🦩 A Python tool to create comment-free Jupyter notebooks.

Pelikan Pelikan lets you convert notebooks to comment-free notebooks. In other words, It removes Python block and inline comments from source cells in

Hakan Özler 7 Nov 20, 2021
A simple tool to extract python code from a Jupyter notebook, and then run pylint on it for static analysis.

Jupyter Pylinter A simple tool to extract python code from a Jupyter notebook, and then run pylint on it for static analysis. If you find this tool us

Edmund Goodman 10 Oct 13, 2022
Generates a random prnt.sc link and display image.

Generates a random prnt.sc link and display image.

Emirhan 3 Oct 08, 2021
A fancy and practical functional tools

Funcy A collection of fancy functional tools focused on practicality. Inspired by clojure, underscore and my own abstractions. Keep reading to get an

Alexander Schepanovski 2.9k Jan 07, 2023
A Random Password Generator made from Python

Things you need Python Step 1 Download the python file from Releases Step 2 Go to the directory where the python file is and run it Step 3 Type the le

Kavindu Nimsara 3 May 30, 2022
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
A pythonic dependency injection library.

Pinject Pinject is a dependency injection library for python. The primary goal of Pinject is to help you assemble objects into graphs in an easy, main

Google 1.3k Dec 30, 2022
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
Extract the download URL from OneDrive or SharePoint share link and push it to aria2

OneDriveShareLinkPushAria2 Extract the download URL from OneDrive or SharePoint share link and push it to aria2 从OneDrive或SharePoint共享链接提取下载URL并将其推送到a

高玩梁 262 Jan 08, 2023
Python bytecode manipulation and import process customization to do evil stuff with format strings. Nasty!

formathack Python bytecode manipulation and import process customization to do evil stuff with format strings. Nasty! This is an answer to a StackOver

Michiel Van den Berghe 5 Jan 18, 2022
Retrying library for Python

Tenacity Tenacity is an Apache 2.0 licensed general-purpose retrying library, written in Python, to simplify the task of adding retry behavior to just

Julien Danjou 4.3k Jan 05, 2023
Pyfunctools is a module that provides functions, methods and classes that help in the creation of projects in python

Pyfunctools Pyfunctools is a module that provides functions, methods and classes that help in the creation of projects in python, bringing functional

Natanael dos Santos Feitosa 5 Dec 22, 2022
The producer-consumer problem implemented with threads in Python

This was developed using a Python virtual environment, I would strongly recommend to do the same if you want to clone this repository. How to run this

Omar Beltran 1 Oct 30, 2021
Greenery - tools for parsing and manipulating regular expressions

Greenery - tools for parsing and manipulating regular expressions

qntm 242 Dec 15, 2022
Create a Web Component (a Custom Element) from a python file

wyc Create a Web Component (a Custom Element) from a python file (transpile python code to javascript (es2015)). Features Use python to define your cu

7 Oct 09, 2022
A python module for extract domains

A python module for extract domains

Fayas Noushad 4 Aug 10, 2022
Control-Alt-Delete - Help Tux Escape Beastie's Jail!

Control-Alt-Delete Help Tux escape Beastie's jail by completing the following challenges! Challenges Challenge 00: Drinks: Tux needs to drink less. Ch

NDLUG 8 Oct 31, 2021
Find version automatically based on git tags and commit messages.

GIT-CONVENTIONAL-VERSION Find version automatically based on git tags and commit messages. The tool is very specific in its function, so it is very fl

0 Nov 07, 2021