<jupyter_start><jupyter_text>TSP Art[TSP art](https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html) is an algorithmic way to create line drawings from images that can be drawn without lifting the pencil.It is produced by creating a point cloud with a density depending on the brightness of the image and connecting the dots by a shortest [TSP](https://en.wikipedia.org/wiki/Travelling_salesman_problem) tour.The version in this example is leaving out some of the more compelling parts, in particular the use of proper [stippling](https://en.wikipedia.org/wiki/Stippling). Follow the link above to learn more about TSP art.<jupyter_code>import networkx as nx

from itertools import product, combinations
from math import sqrt

from gurobipy import GRB

# GraphILP API: import networkx graphs and use travelling salesman problem
from graphilp.imports import networkx as nximp
from graphilp.network import tsp
from graphilp.network.heuristics import tsp_christofides
from matplotlib import image as mpimg 
from matplotlib import pyplot as plt

import numpy as np<jupyter_output><empty_output><jupyter_text>Create graph from image<jupyter_code>image = mpimg.imread("images/example_tsp_art.png")
plt.imshow(image);<jupyter_output><empty_output><jupyter_text>Convert image to gray-scale<jupyter_code>def rgb2gray(rgb):
    return np.dot(rgb[...,:3], [0.2989, 0.5870, 0.1140])
gray = rgb2gray(image)
plt.imshow(gray, cmap='gray');<jupyter_output><empty_output><jupyter_text>Draw sample from intensity distribution<jupyter_code>flat = gray.flatten()
sample_index = np.random.choice(a=flat.size, replace=False, p=flat/flat.sum(), size=1000)
adjusted_index = np.unravel_index(sample_index, gray.shape)
plt.imshow(gray, cmap='gray')
plt.scatter(adjusted_index[1], adjusted_index[0], s=2);<jupyter_output><empty_output><jupyter_text>Create graph from samples<jupyter_code>def distance(indexes, i, j):
    return sqrt((indexes[0][i] - indexes[0][j])**2 + (indexes[1][i] - indexes[1][j])**2)
edges = [(i, j,
         {'weight':distance(adjusted_index, i, j)}) for i, j in combinations(range(len(adjusted_index[0])), 2)]
G = nx.Graph()
G.add_edges_from(edges)
optG = nximp.read(G)<jupyter_output><empty_output><jupyter_text>Create warmstart using Christofides's algorithm<jupyter_code>warmstart_tour, lower_bound = tsp_christofides.get_heuristic(optG)
plt.scatter(adjusted_index[0], adjusted_index[1], s=2)
for edge in warmstart_tour:
    plt.plot((adjusted_index[0][edge[0]], adjusted_index[0][edge[1]]),
             (adjusted_index[1][edge[0]], adjusted_index[1][edge[1]]), 'r');<jupyter_output><empty_output><jupyter_text>Setup optimisation problem<jupyter_code>m = tsp.create_model(optG, direction=GRB.MINIMIZE, warmstart=warmstart_tour)<jupyter_output><empty_output><jupyter_text>Find optimal solution<jupyter_code># this may take a while
# you can interrupt the solver at any time to inspect the intermediate solution
m.optimize()
tour = tsp.extract_solution(optG, m)<jupyter_output><empty_output><jupyter_text>Visualise solution<jupyter_code>plt.figure(figsize=(12,10))
plt.subplot(121)
plt.axis('off')
plt.imshow(image)
ax = plt.subplot(122)
plt.axis('off')
ax.set_aspect(image.shape[0]/image.shape[1])
for edge in tour:
    plt.plot((adjusted_index[1][edge[0]], adjusted_index[1][edge[1]]),
             (image.shape[0]-adjusted_index[0][edge[0]], image.shape[0]-adjusted_index[0][edge[1]]), 'k');<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12886297376093295, 'fraction_numerical': 0.019533527696793004, 'mean_word_length': 7.28743961352657, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 37, 'https://': 3, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '589465', 'license': 'MIT', 'n_tokens_mistral': 1259, 'n_tokens_neox': 1184, 'n_words': 261, 'path': 'graphilp/examples/TSPArt.ipynb', 'repo_name': 'VF-DE-CDS/GraphILP-API', 'size': '3430'}