WiP implementation of Nick Gravin's linear-time graph d-list colouring algorithm.

ngravin-d-list-col-impl-WiP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "13dc9391-22f2-4d8b-89d9-e27a62bdb24e",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "..\n",
      "----------------------------------------------------------------------\n",
      "Ran 2 tests in 230.201s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Graph size vs. execution time (seconds):\n",
      "n\tTime\n",
      "50\t0.0050\n",
      "100\t0.0058\n",
      "200\t0.0213\n",
      "400\t0.0766\n",
      "800\t0.2942\n",
      "1600\t1.2065\n",
      "3200\t3.0725\n",
      "6400\t10.0128\n",
      "12800\t41.1259\n",
      "25600\t173.4599\n",
      "Adjacency matrix graph: 0 vertices, 0 edges.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAdUAAAHWCAYAAAAhLRNZAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAHPUlEQVR4nO3VwQkAIRDAwPP673ktwoAgMxXklzUz8wEAx/7bAQDwClMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABAxVQCImCoAREwVACKmCgARUwWAiKkCQMRUASBiqgAQMVUAiJgqAERMFQAipgoAEVMFgIipAkDEVAEgYqoAEDFVAIiYKgBETBUAIqYKABFTBYCIqQJAxFQBIGKqABDZIdkHqD/ZctsAAAAASUVORK5CYII=",
      "text/plain": [
       "Graphics object consisting of 0 graphics primitives"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Random maximal planar graph: 100 vertices, 286 edges.\n"
     ]
    },
    {
     "data": {