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
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
An NUS timetable generator which uses a genetic algorithm to optimise timetables to suit the needs of NUS students.

A timetable optimiser for NUS which uses an evolutionary algorithm to "breed" a timetable suited to your needs.

Nicholas Lee 3 Jan 09, 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
Robotic Path Planner for a 2D Sphere World

Robotic Path Planner for a 2D Sphere World This repository contains code implementing a robotic path planner in a 2D sphere world with obstacles. The

Matthew Miceli 1 Nov 19, 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
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
This is a demo for AAD algorithm.

Asynchronous-Anisotropic-Diffusion-Algorithm This is a demo for AAD algorithm. The subroutine of the anisotropic diffusion algorithm is modified from

3 Mar 21, 2022
Leveraging Unique CPS Properties to Design Better Privacy-Enhancing Algorithms

Differential_Privacy_CPS Python implementation of the research paper Leveraging Unique CPS Properties to Design Better Privacy-Enhancing Algorithms Re

Shubhesh Anand 2 Dec 14, 2022
A selection of a few algorithms used to sort or search an array

Sort and search algorithms This repository has some common search / sort algorithms written in python, I also included the pseudocode of each algorith

0 Apr 02, 2022
Dynamic Programming-Join Optimization Algorithm

DP-JOA Join optimization is the process of optimizing the joining, or combining, of two or more tables in a database. Here is a simple join optimizati

Haoze Zhou 3 Feb 03, 2022
A litle algorithm that i made for transform a picture in a spreadsheet.

PicsToSheets How it works? It is an algorithm designed to transform an image into a spreadsheet file. this converts image pixels to color cells of she

Guilherme de Oliveira 1 Nov 12, 2021
A Python Package for Portfolio Optimization using the Critical Line Algorithm

A Python Package for Portfolio Optimization using the Critical Line Algorithm

19 Oct 11, 2022
My own Unicode compression algorithm

Zee Code ZCode is a custom compression algorithm I originally developed for a competition held for the Spring 2019 Datastructures and Algorithms cours

Vahid Zehtab 2 Oct 20, 2021
Supplementary Data for Evolving Reinforcement Learning Algorithms

evolvingrl Supplementary Data for Evolving Reinforcement Learning Algorithms This dataset contains 1000 loss graphs from two experiments: 500 unique g

John Co-Reyes 42 Sep 21, 2022
Rover. Finding the shortest pass by Dijkstra’s shortest path algorithm

rover Rover. Finding the shortest path by Dijkstra’s shortest path algorithm Задача Вы — инженер, проектирующий роверы-беспилотники. Вам надо спроекти

1 Nov 11, 2021
Implemented page rank program

Page Rank Implemented page rank program based on fact that a website is more important if it is linked to by other important websites using recursive

Vaibhaw 6 Aug 24, 2022
Cormen-Lib - An academic tool for data structures and algorithms courses

The Cormen-lib module is an insular data structures and algorithms library based on the Thomas H. Cormen's Introduction to Algorithms Third Edition. This library was made specifically for administeri

Cormen Lib 12 Aug 18, 2022
marching rectangles algorithm in python with clean code.

Marching Rectangles marching rectangles algorithm in python with clean code. Tools Python 3 EasyDraw Creators Mohammad Dori Run the Code Installation

Mohammad Dori 3 Jul 15, 2022
8 Puzzle with A* , Greedy & BFS Search in Python

8_Puzzle 8 Puzzle with A* , Greedy & BFS Search in Python Python Install Python from here. Pip Install pip from here. How to run? 🚀 Install 8_Puzzle

I3L4CK H4CK3l2 1 Jan 30, 2022
The test data, code and detailed description of the AW t-SNE algorithm

AW-t-SNE The test data, code and result of the AW t-SNE algorithm Structure of the folder Datasets: This folder contains two datasets, the MNIST datas

1 Mar 09, 2022