Optimal skincare partition finder using graph theory

Related tags

Algorithmspigment
Overview

Pigment

License: ISC CC BY-SA 4.0

The problem of partitioning up a skincare regime into parts such that each part does not interfere with itself is equivalent to the minimal clique cover problem, which can be transformed into the vertex colouring of a graph, both of which are NP-hard and thus computationally infeasible to find optimal solutions for. This project is a brute-force proof-of-concept that exhaustively solves the problem of good skincare product grouping!

Usage

  1. Modify the ingredient conflict dictionary (named conflicts in the pigment.py mainline) to reflect your skincare products. If you say A conflicts with B, you don't have to also write the rule that B conflicts with A. The script handles the reflexivity.

  2. Run the program (you need Python 3):

    python3 pigment.py

Algorithm

This algorithm takes in an adjacency list for a conflict graph where each edge between two nodes represents an instance of two ingredients conflicting.

It then exhaustively generates every possible partition using a recursive backtracking depth-first-search algorithm where for each ingredient, it explores every sub-tree consisting of adding the ingredient to every existing part before finally creating a new part. Each terminal/leaf node represents a generated partition, which we exhaustively check: for each part in the partition, we check to see if any pair exists as an edge in the conflict dictionary. If no such pairs exist among any part, the partition is valid.

partition tree

The algorithm looks for the valid partition with the least amount of parts.

The number of partitions that are brute-force generated is equivalent to the nth Bell number and it is sequence A000110 in the OEIS.

It runs in O(a fuckton of time). If you have a lot of stuff in your skincare routine, this algorithm may take forever to run. It is recommended that you do not add vanity elements (aka adding an element just for it to show up in the final result) such as:

CONFLICTS = OrderedDict((
    ("A", ["B", "C"])
    ("D", [])
))

In this case, "D" is a vanity element; it contributes nothing to conflict data but bloats the state space (which, in a brute-force algorithm like this, is not good). If an element doesn't conflict with anything, then use it as liberally as you like without restriction.

You have been warned.

Modelling

Say, for the purposes of illustration (as these opinions are still hotly debated in the skincare community today), we have the following ingredients:

  • Retinol
  • AHAs/BHAs
  • Copper peptides
  • Ferrulic acid

and the following interactions:

  • Retinol and AHAs/BHAs conflict with each other
  • Copper peptides interfere with AHAs/BHAs
  • Ferrulic acid interferes with copper peptides

We can therefore model compatible products as an undirected graph where each node represents a skincare ingredient and each edge between node a and node b represents the sentence "ingredient a is compatible with ingredient b". We can represent the relation above as such:

compatibility graph

The ideal here is that we want to take all four of these ingredients at once, however as noted by the conflicts above, that isn't possible. The next best solution, if we can't create 1 part, is to try to create 2 part. We know that in our model, retinol is compatible with copper peptides, and ferrulic acid is compatible with AHAs/BHAs, but we discard the possibility of using retinol with ferrulic acid though, as its part contains AHAs/BHAs, which are not compatible with retinol (as shown by the lack of edge).

minimum clique

This is the optimal solution. In one skincare session, we take retinol with the copper peptides, and another session we take AHAs/BHAs and ferrulic acid.

Our major goal, therefore, is to partition the ingredients list into as few parts as possible such that each parts's ingredients represents a clique, where a clique is an induced subgraph that is complete. In layperson's terms, we are looking to create subgraphs of ingredients such that each ingredient has an edge connected to every other ingredient node in the subgraph. Such complete subgraphs are known as cliques. As shown below, when two ingredients are compatible with each other, the resultant clique has a single edge between two nodes (as shown by K2: 1). For four ingredients, the resultant clique has six edges between the four nodes (as shown by K2:6). To see ten ingredients compatible with each other is somewhat uncommon.

complete graphs These images are taken from Wikipedia.org and are by koko90. See attribution for details

Minimal Clique Cover

In formal terms, a "clique cover" or "partition into cliques" of an undirected graph is a partition (or splitting of the graph into groups) into constituent cliques. Our problem is to find the "minimal" clique cover—aka—doing it in the least number of cliques—or splits—possible. As shown in the figure above, the trivial case is K1: 0 as each individual ingredient is its own clique, but that's the worst-case scenario we are trying to avoid. It would mean that no skincare ingredient is compatible with anything else e.g. you may have to take each 10 skincare ingredient on separate days, which would be a scheduling nightmare.

Graph Colouring

We can make things more readable by looking at an equivalent problem.

Given a graph G, the complement of the graph, let's call it G2, is a graph with the same nodes as G, but every edge in the original graph is missing, and every midding edge in the original graph is now an edge. In layperson's terms, a complement graph G2 for graph G contains only the edges necessary to turn G into a complete graph, as shown by this diagram:

complement of the Petersen graph Image edited by Claudio Rocchini; derived from David Eppstein. See attribution for details

We can invert the "maximal clique" problem by not mapping whether two skincare products are compatible with each other, but rather if they conflict. This makes specifications a whole lot easier to make, as now we can assume anything that isn't connected by an edge is compatible. If we change our first graph to model conflicts instead of synergies, we get the following:

conflict graph

Our problem is now to induce subgraphs such that none of the nodes have any edges between them. Each subgraph is its own group. In this example, we induce the subgraphs for the nodes {Retinol, Copper peptides} as well as for {Ferrulic acid, AHAs/BHAs}, as each graph has no nodes:

coloured conflict graph

Those with a background in CS will immediately notice that this is actually the well-studied graph colouring sub-problem known as "vertex colouring": colouring a graph such that no two colours are adjacent to each other. In this case, each colour group represents a partition, like from earlier. Again, the optimization problem is NP-hard and is intractable. Which is why the algorithm solves the colouring problem in the ugliest, most brute force way possible.

Bibliography

Attribution

  • Graphs made by me using Dreampuf's Dot Grapher and they are licensed as CC BY-SA 4.0 as the project is
  • Complete graphs K1, K2, and K3 are simple geometry and thus are in the public domain (author is David Benbennick).
  • Simplex graphs 4, 5, 6, 7, 8, 9, 10, 11, were released by Koko90 under GFDL and CC BY-SA 3.0 and will be coalesced into the license of this project, thus making them CC BY-SA 4.0
  • The Petersen graph complement image was edited by Claudio Rocchini whose original author was David Eppstein, also released under GFDL and CC BY-SA 3.0. CC BY-SA 4.0 as per the project.
Owner
Jason Nguyen
CS @ University of Guelph
Jason Nguyen
A simple python implementation of A* and bfs algorithm solving Eight-Puzzle

A simple python implementation of A* and bfs algorithm solving Eight-Puzzle

2 May 22, 2022
Path tracing obj - (taichi course final project) a path tracing renderer that can import and render obj files

Path tracing obj - (taichi course final project) a path tracing renderer that can import and render obj files

5 Sep 10, 2022
iAWE is a wonderful dataset for those of us who work on Non-Intrusive Load Monitoring (NILM) algorithms.

iAWE is a wonderful dataset for those of us who work on Non-Intrusive Load Monitoring (NILM) algorithms. You can find its main page and description via this link. If you are familiar with NILM-TK API

Mozaffar Etezadifar 3 Mar 19, 2022
Sorting Algorithm Visualiser using pygame

SortingVisualiser Sorting Algorithm Visualiser using pygame Features Visualisation of some traditional sorting algorithms like quicksort and bubblesor

4 Sep 05, 2021
Repository for data structure and algorithms in Python for coding interviews

Python Data Structures and Algorithms This repository contains questions requiring implementation of data structures and algorithms concepts. It is us

Prabhu Pant 1.9k Jan 01, 2023
Code for generating alloy / disordered structures through the special quasirandom structure (SQS) algorithm

Code for generating alloy / disordered structures through the special quasirandom structure (SQS) algorithm

Bruno Focassio 1 Nov 10, 2021
Algorithmic trading backtest and optimization examples using order book imbalances. (bitcoin, cryptocurrency, bitmex)

Algorithmic trading backtest and optimization examples using order book imbalances. (bitcoin, cryptocurrency, bitmex)

172 Dec 21, 2022
Minimal pure Python library for working with little-endian list representation of bit strings.

bitlist Minimal Python library for working with bit vectors natively. Purpose This library allows programmers to work with a native representation of

Andrei Lapets 0 Jul 25, 2022
FingerPy is a algorithm to measure, analyse and monitor heart-beat using only a video of the user's finger on a mobile cellphone camera.

FingerPy is a algorithm using python, scipy and fft to measure, analyse and monitor heart-beat using only a video of the user's finger on a m

Thiago S. Brasil 37 Oct 21, 2022
Pathfinding algorithm based on A*

Pathfinding V1 What is pathfindingV1 ? This program is my very first path finding program, using python and turtle for graphic rendering. How is it wo

Yan'D 6 May 26, 2022
PickMush - A mini study/project on boosting algorithm

PickMush A mini project implementing Boosting Author Shashwat Vaibhav What does it do? Classifies whether Mushroom is edible or is non-edible (binary

Shashwat Vaibahav 3 Nov 08, 2022
This repository is not maintained

This repository is no longer maintained, but is being kept around for educational purposes. If you want a more complete algorithms repo check out: htt

Nic Young 2.8k Dec 30, 2022
Machine Learning algorithms implementation.

Machine Learning Algorithms Machine Learning algorithms implementation. What can I find here? ML Algorithms KNN K-Means-Clustering SVM (MultiClass) Pe

David Levin 1 Dec 10, 2021
RRT algorithm and its optimization

RRT-Algorithm-Visualisation This is a project that aims to develop upon the RRT

Sarannya Bhattacharya 7 Mar 06, 2022
A Python project for optimizing the 8 Queens Puzzle using the Genetic Algorithm implemented in PyGAD.

8QueensGenetic A Python project for optimizing the 8 Queens Puzzle using the Genetic Algorithm implemented in PyGAD. The project uses the Kivy cross-p

Ahmed Gad 16 Nov 13, 2022
Visualisation for sorting algorithms. Version 2.0

Visualisation for sorting algorithms v2. Upped a notch from version 1. This program provides animates simple, common and popular sorting algorithms, t

Ben Woo 7 Nov 08, 2022
Algorithmic virtual trading using the neostox platform

Documentation Neostox doesnt have an API Support, so this is a little selenium code to automate strategies How to use Clone this repository and then m

Abhishek Mittal 3 Jul 20, 2022
A genetic algorithm written in Python for educational purposes.

Genea: A Genetic Algorithm in Python Genea is a Genetic Algorithm written in Python, for educational purposes. I started writing it for fun, while lea

Dom De Felice 20 Jul 06, 2022
8-puzzle-solver with UCS, ILS, IDA* algorithm

Eight Puzzle 8-puzzle-solver with UCS, ILS, IDA* algorithm pre-usage requirements python3 python3-pip virtualenv prepare enviroment virtualenv -p pyth

Mohsen Arzani 4 Sep 22, 2021
Distributed algorithms, reimplemented for fun and practice

Distributed Algorithms Playground for reimplementing and experimenting with algorithms for distributed computing. Usage Running the code for Ring-AllR

Mahan Tourkaman 1 Oct 16, 2022