Otimização de grafos com NetworkX em Python

Neste tutorial, você vai encarar um problema clássico da teoria dos grafos chamado Problema do Carteiro Chinês. Algumas partes do algoritmo, embora simples conceitualmente, são computacionalmente pesadas. Ainda assim, para acompanhar, basta ter conhecimentos prévios de Python: não é preciso fundo rigoroso em matemática, ciência da computação ou teoria dos grafos.

Primeiro, vamos revisar os blocos básicos de um grafo (nós, arestas, caminhos etc.) e resolver o problema em um grafo real (rede de trilhas de um parque estadual) usando a biblioteca NetworkX no Python. O foco é nos conceitos essenciais e na implementação. Para quem quiser ir além, deixamos leituras sobre os detalhes da otimização.

Por que otimizar grafos

O problema

Você provavelmente já ouviu falar do Problema do Caixeiro Viajante, que busca a menor rota (por exemplo, estradas) que conecta um conjunto de nós (por exemplo, cidades). Menos conhecido, o Problema do Carteiro Chinês (CPP), também chamado de inspeção de rotas ou roteamento por arcos, é parecido. O objetivo do CPP é encontrar o caminho mais curto que percorra todos os links (estradas) de um grafo pelo menos uma vez. Se isso puder ser feito sem passar duas vezes pela mesma estrada, ótimo: é o cenário ideal e o problema fica simples. Mas, se algumas estradas precisarem ser percorridas mais de uma vez, entra a matemática para descobrir a rota mais curta que atinja todas as estradas pelo menos uma vez com a menor quilometragem total.

Motivação pessoal

(Uma nota pessoal: brega, espirituosa e 100% desnecessária para aprender otimização de grafos em Python)

Eu tinha uma aplicação do mundo real para esse problema: conquistar o título de Giantmaster Marathoner.

O que é um Giantmaster? Um Giantmaster é quem (canino ou humano) percorreu todas as trilhas do Sleeping Giant State Park em Hamden, CT (vizinho da minha cidade natal, Wallingford)... ao longo da vida. Um Giantmaster Marathoner é quem percorreu todas essas trilhas em um único dia.

Graças ao registro meticuloso da Sleeping Giant Park Association, a lista completa de Giantmasters e seus níveis pode ser encontrada aqui. Admito que isso me motivou bastante a iniciar este projeto paralelo e cair na trilha. Eu mesmo atingi o status de Giantmaster no inverno de 2006, quando eu era um jovem voluntário da Sleeping Giant Trail Crew (fiquei feliz em ver isso registrado no arquivo da SG), mas novos desafios surgiram desde então. Embora as categorias de 12 meses e 4 estações sejam impressionantes e tentadoras, exigiriam mais viagens da minha casa atual (DC) para minha casa formativa (CT) do que eu poderia administrar... e não são tão interessantes para otimização de grafos. Então, vamos de Giantmaster Marathon!

Para referência, o mapa de trilhas do Sleeping Giant está abaixo:

Introdução a grafos

O legal dos grafos é que os conceitos e a terminologia são, em geral, intuitivos. Ainda assim, aqui vai um glossário básico:

Grafos são estruturas que mapeiam relações entre objetos. Neste tutorial, os objetos são chamados de nós e as conexões entre eles de arestas. Observe que arestas e nós costumam receber outros nomes, que em geral significam a mesma coisa:

node == vertex == point
edge == arc == link

O grafo inicial é não direcionado. Ou seja, suas arestas não têm orientação: são bidirecionais. Exemplo: A<--->B == B<--->A.
Já o grafo que você pode criar para especificar o caminho mais curto que percorra todas as trilhas pode ser um grafo direcionado, em que a ordem e a direção das arestas importam. Exemplo: A--->B != B--->A.

O grafo também é um grafo ponderado por arestas, em que a distância (em milhas) entre cada par de nós adjacentes representa o peso da aresta. Isso é tratado como um atributo da aresta chamado "distance".

Grau é o número de arestas incidentes (que tocam) um nó. Nós são chamados de grau ímpar quando esse número é ímpar e de grau par quando é par.

A solução deste CPP será um tour euleriano: um grafo no qual é possível formar um ciclo que passa por cada aresta exatamente uma vez, saindo de um nó e voltando a ele (sem retroceder). Um Euler Tour também é conhecido por vários nomes:

Eulerian tour == Eulerian circuit == Eulerian cycle

Um emparelhamento é um subconjunto de arestas em que nenhum nó aparece mais de uma vez. Um emparelhamento de peso mínimo encontra o emparelhamento com a menor soma possível de pesos das arestas.

NetworkX: manipulação e análise de grafos

O NetworkX é o pacote Python mais popular para manipular e analisar grafos. Há outros pacotes com nível básico semelhante, como o igraph, que também tem bindings para R e C++. Mas o NetworkX traz os algoritmos de grafos mais robustos de que precisei para resolver o CPP.

Instalação de pacotes

Se você já fez algum tipo de análise de dados em Python ou usa a distribuição Anaconda, provavelmente já tem pandas e matplotlib. Talvez falte o networkx. Estes devem ser os únicos pacotes fora da biblioteca padrão do Python de que você vai precisar para este tutorial. A instalação via pip é simples:

pip install pandas
pip install networkx
pip install matplotlib

Por ora, isso deve bastar. imageio e numpy são importados só no final para criar a animação GIF da solução do CPP. A animação está embutida neste post, então esses pacotes são opcionais.

import itertools
import copy
import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt

Carregar os dados

Lista de arestas

A lista de arestas é uma estrutura simples que vamos usar para criar o grafo. Cada linha representa uma aresta do grafo com alguns atributos.

• node1 & node2: nomes dos nós conectados.
• trail: atributo da aresta indicando a sigla da trilha de cada aresta. Exemplo: rs = red square
• distance: atributo da aresta indicando o comprimento da trilha, em milhas.
• color: cor da trilha usada no gráfico.
• estimate: atributo indicando se a distância da aresta foi estimada a partir do mapa (1=sim, 0=não), já que nem todas as distâncias são fornecidas. É apenas referência; não é usado na análise.

# Buscar a lista de arestas hospedada no Gist
edgelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/e570c38bcc72a8d102422f2af836513b/raw/89c76b2563dbc0e88384719a35cba0dfc04cd522/edgelist_sleeping_giant.csv')

# Prévia da edgelist
edgelist.head(10)

Lista de nós

Listas de nós geralmente são opcionais no networkx e em outras bibliotecas quando você já tem a lista de arestas, pois os nomes dos nós estão nas duas primeiras colunas da lista de arestas. Aqui, porém, queremos adicionar alguns atributos de nó: as coordenadas X e Y dos nós (interseções de trilhas), para que possamos plotar o grafo com o mesmo layout do mapa.

Passei uma tarde anotando manualmente esses pontos, traçando sobre a imagem com o GIMP:

• id: nome do nó correspondente a node1 e node2 na lista de arestas.
• X: posição/coord. horizontal do nó em relação ao canto superior esquerdo.
• Y posição/coord. vertical do nó em relação ao canto superior esquerdo.

Observação sobre a geração das listas de nós e arestas

Criar os nomes dos nós também exigiu um pouco de trabalho manual. Cada nó representa a interseção de duas ou mais trilhas. Sempre que possível, o nó foi nomeado como trail1_trail2, onde trail1 vem antes de trail2 em ordem alfabética.

A coisa complica quando as mesmas trilhas se cruzam mais de uma vez. Por exemplo, as trilhas Orange e White. Nesses casos, acrescentei _2 ou _3 ao nome do nó. Assim, você tem dois nós distintos para as duas interseções de Orange e White: o_w e o_w_2.

Isso exigiu muita tentativa e erro, comparando os gráficos gerados com as coordenadas X,Y ao mapa real.

# Buscar a lista de nós hospedada no Gist
nodelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/f989e10af17fb4c85b11409fea47895b/raw/a3a8da0fa5b094f1ca9d82e1642b384889ae16e8/nodelist_sleeping_giant.csv')

# Prévia da nodelist
nodelist.head(5)

Criar o grafo

Agora, use a lista de arestas e a lista de nós para criar um objeto grafo no networkx.

# Criar grafo vazio
g = nx.Graph()

Percorra as linhas da lista de arestas e adicione cada aresta e seus atributos ao grafo g.

# Adicionar arestas e seus atributos
for i, elrow in edgelist.iterrows():
    g.add_edge(elrow[0], elrow[1], attr_dict=elrow[2:].to_dict())

Para ilustrar, vamos imprimir os valores da última linha da lista de arestas que foi adicionada ao grafo g:

# Exemplo da lista de arestas
print(elrow[0]) # node1
print(elrow[1]) # node2
print(elrow[2:].to_dict()) # dict de atributos da aresta

o_gy2
y_gy2
{'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.12}

De forma semelhante, percorra as linhas da lista de nós e adicione esses atributos.

# Adicionar atributos de nós
for i, nlrow in nodelist.iterrows():
    g.node[nlrow['id']] = nlrow[1:].to_dict()

Exemplo da última linha da lista de nós:

# Exemplo da lista de nós
print(nlrow)

id    y_rt
X      977
Y     1666
Name: 76, dtype: object

Inspecionar o grafo

Arestas

As arestas são representadas por uma lista de tuplas de tamanho 3. Os dois primeiros elementos são os nomes dos nós ligados pela aresta. O terceiro é o dicionário de atributos da aresta.

# Prévia das 5 primeiras arestas
g.edges(data=True)[0:5]

[('rs_end_south',
  'y_rs',
  {'color': 'red', 'distance': 0.39, 'estimate': 0, 'trail': 'rs'}),
 ('w_gy2',
  'park_east',
  {'color': 'gray', 'distance': 0.12, 'estimate': 0, 'trail': 'w'}),
 ('w_gy2',
  'g_gy2',
  {'color': 'yellowgreen', 'distance': 0.05, 'estimate': 0, 'trail': 'gy2'}),
 ('w_gy2',
  'b_w',
  {'color': 'gray', 'distance': 0.42, 'estimate': 0, 'trail': 'w'}),
 ('w_gy2',
  'b_gy2',
  {'color': 'yellowgreen', 'distance': 0.03, 'estimate': 1, 'trail': 'gy2'})]

Nós

Os nós são representados por uma lista de tuplas de tamanho 2. O primeiro elemento é o ID do nó, seguido do dicionário de atributos.

# Prévia dos 10 primeiros nós
g.nodes(data=True)[0:10]

[('rs_end_south', {'X': 1865, 'Y': 1598}),
 ('w_gy2', {'X': 2000, 'Y': 954}),
 ('rd_end_south_dupe', {'X': 273, 'Y': 1869}),
 ('w_gy1', {'X': 1184, 'Y': 1445}),
 ('g_rt', {'X': 908, 'Y': 1378}),
 ('v_rd', {'X': 258, 'Y': 1684}),
 ('g_rs', {'X': 1676, 'Y': 775}),
 ('rc_end_north', {'X': 867, 'Y': 618}),
 ('v_end_east', {'X': 2131, 'Y': 921}),
 ('rh_end_south', {'X': 721, 'Y': 1925})]

Estatísticas resumidas

Imprima algumas estatísticas antes de visualizar o grafo.

print('# of edges: {}'.format(g.number_of_edges()))
print('# of nodes: {}'.format(g.number_of_nodes()))

# of edges: 123
# of nodes: 77

Visualizar o grafo

Cores e layout

Posições: Primeiro, extraia as posições dos nós do grafo para um dicionário. Assim, você recria o grafo com o mesmo layout do mapa de trilhas. Y é negado para transformar a origem do eixo Y do canto superior esquerdo para o inferior esquerdo.

# Dicionário de posições dos nós para plotar
node_positions = {node[0]: (node[1]['X'], -node[1]['Y']) for node in g.nodes(data=True)}

# Prévia de node_positions (hack, já que dicionários não têm head/slice).
dict(list(node_positions.items())[0:5])

{'b_rd': (268, -1744),
 'g_rt': (908, -1378),
 'o_gy1': (1130, -1297),
 'rh_end_tt_2': (550, -1608),
 'rs_end_south': (1865, -1598)}

Cores: Agora, extraia as cores das arestas para uma lista simples, para visualizar as trilhas por cor.

# Lista de cores de arestas para o plot
edge_colors = [e[2]['color'] for e in g.edges(data=True)]

# Prévia das 10 primeiras
edge_colors[0:10]

['red',
 'gray',
 'yellowgreen',
 'gray',
 'yellowgreen',
 'blue',
 'black',
 'yellowgreen',
 'gray',
 'gray']

Plot

Agora você pode criar um gráfico que se alinha bem ao mapa de trilhas do Sleeping Giant:

plt.figure(figsize=(8, 6))
nx.draw(g, pos=node_positions, edge_color=edge_colors, node_size=10, node_color='black')
plt.title('Graph Representation of Sleeping Giant Trail Map', size=15)
plt.show()

Essa representação obviamente não captura todas as curvas e sinuosos das trilhas, mas sem estresse: isso está refletido com precisão no atributo distance das arestas, que é usado no cálculo. O visual captura a distância entre nós (interseções) em linha reta, o que parece ser uma aproximação razoável.

Visão geral do algoritmo do CPP

Beleza, agora que definimos os termos e criamos o grafo, como encontrar o caminho mais curto?

Resolver o Problema do Carteiro Chinês é conceitualmente simples:

1. Encontrar todos os nós de grau ímpar (muito fácil).
   (Todas as interseções onde o número de trilhas que tocam é ímpar)
   
   

2. Adicionar arestas ao grafo de modo que todos os nós de grau ímpar se tornem pares. Essas arestas adicionadas devem existir no grafo original (vamos assumir que não há atalhos fora das trilhas). O conjunto de arestas adicionadas deve somar a menor distância possível (difícil... np-difícil, para ser preciso).
   (Em miúdos: minimizar o quanto você vai ter que voltar pelo mesmo caminho em uma rota que passa por todas as trilhas)
   
   

3. Dado um ponto de partida, encontrar o tour euleriano no conjunto aumentado (moderadamente fácil).
   (Depois de saber onde vamos ter que voltar, calcular a rota do início ao fim)

Pressupostos e simplificações

Um caminho mais curto e preciso poderia surgir relaxando os pontos abaixo, mas isso adicionaria complexidade além do escopo deste tutorial, que foca no CPP.

Pressuposto 1: apenas trilhas obrigatórias

Como dá para ver no mapa, há estradas nas bordas do parque que poderiam conectar trilhas, especialmente as vermelhas. Também há trilhas (Horseshoe e marcações sem nome) que não são obrigatórias pelo registro Giantmaster, mas ajudariam a evitar voltas longas. Incluir trilhas opcionais é um variante estabelecida do CPP chamada Rural Postman Problem. Aqui, ignoramos trilhas opcionais e focamos nas obrigatórias.

Pressuposto 2: subir == descer

O CPP assume que o custo de caminhar uma trilha equivale à sua distância, independentemente do sentido. Mas algumas trilhas são bem íngremes e exigem mais energia para subir do que descer. Uma métrica que combine distância e variação de elevação em um grafo direcionado poderia ser incorporada na extensão chamada Windy Postman Problem.

Pressuposto 3: sem arestas paralelas (trilhas)

Embora possível, incluir arestas paralelas (múltiplas trilhas ligando o mesmo par de nós) complica o cálculo. Felizmente, isso só ocorre duas vezes aqui (Blue <=> Red Diamond e Blue <=> Tower Trail). Lidamos com isso com um pequeno hack na lista de arestas: nós duplicados com sufixo _dupe para capturar todas as trilhas mantendo a unicidade das arestas. A implementação do CPP no pacote postman_problems que escrevi lida de forma mais elegante com arestas paralelas, caso você queira resolver o CPP no seu grafo com muitas paralelas.

CPP passo 1: encontrar nós de grau ímpar

É uma contagem bem direta. Vemos que 36 dos 76 nós têm grau ímpar. São, em sua maioria, trilhas sem saída (grau 1) e interseções de 3 trilhas. Há alguns nós de grau 5.

# Calcular a lista de nós de grau ímpar
nodes_odd_degree = [v for v, d in g.degree_iter() if d % 2 == 1]

# Prévia
nodes_odd_degree[0:5]

['rs_end_south', 'rc_end_north', 'v_end_east', 'rh_end_south', 'b_end_east']

# Contagens
print('Number of nodes of odd degree: {}'.format(len(nodes_odd_degree)))
print('Number of total nodes: {}'.format(len(g.nodes())))

Number of nodes of odd degree: 36
Number of total nodes: 77

CPP passo 2: encontrar pares com distância mínima

Aqui está o coração do problema. Vamos quebrar em 5 partes:

1. Calcular todos os pares possíveis de nós de grau ímpar.
2. Calcular o caminho mais curto entre cada par do item 1.
3. Criar um grafo completo conectando todos os pares do 1. com a distância de caminho mais curto do 2.
4. Calcular um emparelhamento de peso mínimo do grafo do 3.
   (Basicamente, como parear os nós ímpares de modo que a soma das distâncias entre os pares seja a menor possível.)
5. Augmentar o grafo original com os caminhos mais curtos entre os pares do 4.

Passo 2.1: computar os pares de nós

Use a função itertools combination para computar todos os pares possíveis de nós ímpares. O grafo é não direcionado, então a ordem não importa: por exemplo, (a,b) == (b,a).

# Computar todos os pares de nós ímpares em uma lista de tuplas
odd_node_pairs = list(itertools.combinations(nodes_odd_degree, 2))

# Prévia
odd_node_pairs[0:10]

[('rs_end_south', 'rc_end_north'),
 ('rs_end_south', 'v_end_east'),
 ('rs_end_south', 'rh_end_south'),
 ('rs_end_south', 'b_end_east'),
 ('rs_end_south', 'b_bv'),
 ('rs_end_south', 'rt_end_south'),
 ('rs_end_south', 'o_rt'),
 ('rs_end_south', 'y_rt'),
 ('rs_end_south', 'g_gy2'),
 ('rs_end_south', 'b_tt_3')]

# Contagem
print('Number of pairs: {}'.format(len(odd_node_pairs)))

Number of pairs: 630

Vamos confirmar que esse número de pares está correto com a combinatória abaixo. Felizmente, só temos 630 pares para lidar. O tempo de computação aqui é trivial (alguns segundos).

Mas, se fossem 3.600 nós ímpares, teríamos ~6,5 milhões de pares para otimizar. A saída cresce ~10.000x para uma entrada 100x maior.

Passo 2.2: caminhos mais curtos entre pares de nós

Aqui entra computação de verdade. Felizmente, o networkx tem uma implementação prática do algoritmo de Dijkstra para o caminho mais curto entre dois nós. Aplicamos a função a cada par (todos os 630) de odd_node_pairs.

def get_shortest_paths_distances(graph, pairs, edge_weight_name):
    """Compute shortest distance between each pair of nodes in a graph.  Return a dictionary keyed on node pairs (tuples)."""
    distances = {}
    for pair in pairs:
        distances[pair] = nx.dijkstra_path_length(graph, pair[0], pair[1], weight=edge_weight_name)
    return distances

# Computar os caminhos mais curtos. Retorna um dicionário com pares de nós como chave e a distância mínima como valor.
odd_node_pairs_shortest_paths = get_shortest_paths_distances(g, odd_node_pairs, 'distance')

# Prévia (hack para dicionários não terem head/slice)
dict(list(odd_node_pairs_shortest_paths.items())[0:10])

{('b_bv', 'y_gy1'): 1.22,
 ('b_bw', 'rc_end_south'): 1.35,
 ('b_end_east', 'b_bw'): 3.0400000000000005,
 ('b_end_east', 'rd_end_north'): 3.83,
 ('g_gy1', 'nature_end_west'): 0.9900000000000001,
 ('o_rt', 'y_gy1'): 0.53,
 ('rc_end_north', 'rd_end_south'): 2.21,
 ('rc_end_north', 'rs_end_north'): 1.79,
 ('rs_end_north', 'o_tt'): 2.0999999999999996,
 ('w_bw', 'rd_end_north'): 1.02}

Passo 2.3: criar grafo completo

Um grafo completo é simplesmente um grafo em que todo nó está conectado a todos os outros por uma aresta única.

Aqui está um exemplo básico da Wikipedia de um grafo completo com 7 nós e 21 arestas (7 escolhe 2):

O grafo que você cria abaixo tem 36 nós e 630 arestas com seus respectivos pesos (distâncias).

Definimos create_complete_graph para calculá-lo. O parâmetro flip_weights transforma distance no atributo weight, onde números menores viram valores grandes e números maiores viram valores pequenos. Parece contraintuitivo, mas é necessário para o passo 2.4, onde calculamos o emparelhamento de peso mínimo no grafo completo.

Idealmente, calcularíamos diretamente o emparelhamento de peso mínimo, mas o NetworkX só implementa max_weight_matching, que maximiza, em vez de minimizar, o peso da aresta. Contornamos isso negando (multiplicando por -1) o atributo distance para obter weight. Assim, a ordem e a escala por distância são preservadas, mas invertidas.

def create_complete_graph(pair_weights, flip_weights=True):
    """
    Create a completely connected graph using a list of vertex pairs and the shortest path distances between them
    Parameters:
        pair_weights: list[tuple] from the output of get_shortest_paths_distances
        flip_weights: Boolean. Should we negate the edge attribute in pair_weights?
    """
    g = nx.Graph()
    for k, v in pair_weights.items():
        wt_i = - v if flip_weights else v
        g.add_edge(k[0], k[1], attr_dict={'distance': v, 'weight': wt_i})
    return g

# Gerar o grafo completo
g_odd_complete = create_complete_graph(odd_node_pairs_shortest_paths, flip_weights=True)

# Contagens
print('Number of nodes: {}'.format(len(g_odd_complete.nodes())))
print('Number of edges: {}'.format(len(g_odd_complete.edges())))

Number of nodes: 36
Number of edges: 630

Para ajudar a visualizar, o grafo totalmente conectado dos nós de grau ímpar está abaixo. Note que preservamos as coordenadas X,Y de cada nó, mas as arestas não representam necessariamente trilhas reais. Por exemplo, dois nós podem estar conectados por uma única aresta aqui, mas o caminho mais curto entre eles pode ter 5 etapas passando por nós de grau par (não mostrados).

# Plotar o grafo completo dos nós de grau ímpar
plt.figure(figsize=(8, 6))
pos_random = nx.random_layout(g_odd_complete)
nx.draw_networkx_nodes(g_odd_complete, node_positions, node_size=20, node_color="red")
nx.draw_networkx_edges(g_odd_complete, node_positions, alpha=0.1)
plt.axis('off')
plt.title('Complete Graph of Odd-degree Nodes')
plt.show()

Passo 2.4: emparelhamento de peso mínimo

Este é o passo mais complexo do CPP. Precisamos encontrar os pares de nós ímpares cuja soma (da distância entre eles) seja a menor possível. No nosso caso, isso se resume a selecionar as 18 arestas ideais (36 nós ímpares / 2) do emaranhado gerado no 2.3.

Tanto a implementação quanto a intuição dessa otimização estão além do escopo deste tutorial... são 800+ linhas de código e um corpo de literatura acadêmica.

Mas, um parêntese para quem se interessa:

Um agradecimento enorme ao Joris van Rantwijk por escrever a implementação original em seu blog lá em 2008. Esbarrei no problema de forma parecida e com a mesma intenção do Joris. Do post de 2008 do Joris:

Como não encontrei implementações em Perl de maximum weighted matching, resolvi escrever eu mesmo. Subestimei o problema, e quando percebi, já estava tão obcecado que me recusei a desistir.

Eu desisti. Felizmente, o Joris não.

Esse Maximum Weight Matching foi incorporado e é mantido no NetworkX. Outro obrigado aos 10+ contribuidores no GitHub que mantêm esse código robusto.

É uma computação difícil e intensiva. O primeiro avanço, em 1965, provou que o problema de Maximum Matching podia ser resolvido em tempo polinomial. Foi publicado por Jack Edmonds com talvez um dos títulos de artigo mais bonitos: "Paths, trees, and flowers" [1]. Uma literatura foi construída desde então, aprimorando o procedimento. O código implementado na função max_weight_matching do NetworkX é baseado em Galil, Zvi (1986) [2], que emprega algoritmo de tempo O(n³).

# Calcular o emparelhamento de peso mínimo.
# Observação: max_weight_matching usa o atributo 'weight' por padrão para maximizar.
odd_matching_dupes = nx.algorithms.max_weight_matching(g_odd_complete, True)

print('Number of edges in matching: {}'.format(len(odd_matching_dupes)))

Number of edges in matching: 36

A saída (odd_matching_dupes) é um dicionário. Embora haja 36 arestas neste emparelhamento, queremos apenas 18. Cada par aparece duas vezes (uma com o nó 1 como chave e outra com o nó 2 como chave).

# Prévia do emparelhamento com duplicatas
odd_matching_dupes

{'b_bv': 'v_bv',
 'b_bw': 'rh_end_tt_1',
 'b_end_east': 'g_gy2',
 'b_end_west': 'rd_end_south',
 'b_tt_3': 'rt_end_north',
 'b_v': 'v_end_west',
 'g_gy1': 'rc_end_north',
 'g_gy2': 'b_end_east',
 'g_w': 'w_bw',
 'nature_end_west': 'o_y_tt_end_west',
 'o_rt': 'o_w_1',
 'o_tt': 'rh_end_tt_2',
 'o_w_1': 'o_rt',
 'o_y_tt_end_west': 'nature_end_west',
 'rc_end_north': 'g_gy1',
 'rc_end_south': 'y_gy1',
 'rd_end_north': 'rh_end_north',
 'rd_end_south': 'b_end_west',
 'rh_end_north': 'rd_end_north',
 'rh_end_south': 'y_rh',
 'rh_end_tt_1': 'b_bw',
 'rh_end_tt_2': 'o_tt',
 'rh_end_tt_3': 'rh_end_tt_4',
 'rh_end_tt_4': 'rh_end_tt_3',
 'rs_end_north': 'v_end_east',
 'rs_end_south': 'y_gy2',
 'rt_end_north': 'b_tt_3',
 'rt_end_south': 'y_rt',
 'v_bv': 'b_bv',
 'v_end_east': 'rs_end_north',
 'v_end_west': 'b_v',
 'w_bw': 'g_w',
 'y_gy1': 'rc_end_south',
 'y_gy2': 'rs_end_south',
 'y_rh': 'rh_end_south',
 'y_rt': 'rt_end_south'}

Converta esse dicionário em uma lista de tuplas, já que o grafo é não direcionado e a ordem não importa. Remover duplicatas gera os 18 pares únicos de arestas que somam a menor distância possível.

# Converter o emparelhamento para lista de tuplas sem duplicatas
odd_matching = list(pd.unique([tuple(sorted([k, v])) for k, v in odd_matching_dupes.items()]))

# Contagem
print('Number of edges in matching (deduped): {}'.format(len(odd_matching)))

Number of edges in matching (deduped): 18

# Prévia dos pares sem duplicatas
odd_matching

[('rs_end_south', 'y_gy2'),
 ('b_end_west', 'rd_end_south'),
 ('b_bv', 'v_bv'),
 ('rh_end_tt_3', 'rh_end_tt_4'),
 ('b_bw', 'rh_end_tt_1'),
 ('o_tt', 'rh_end_tt_2'),
 ('g_w', 'w_bw'),
 ('b_end_east', 'g_gy2'),
 ('nature_end_west', 'o_y_tt_end_west'),
 ('g_gy1', 'rc_end_north'),
 ('o_rt', 'o_w_1'),
 ('rs_end_north', 'v_end_east'),
 ('rc_end_south', 'y_gy1'),
 ('rh_end_south', 'y_rh'),
 ('rt_end_south', 'y_rt'),
 ('b_tt_3', 'rt_end_north'),
 ('rd_end_north', 'rh_end_north'),
 ('b_v', 'v_end_west')]

Vamos visualizar esses pares no grafo completo do passo 2.3. Como antes, as posições dos nós refletem o grafo real (mapa de trilhas), mas as distâncias mostradas (linhas azuis) são em linha reta. O caminho real mais curto entre dois nós pode ter várias arestas que contornam curvas e são bem mais longas.

plt.figure(figsize=(8, 6))

# Plot do grafo completo dos nós de grau ímpar
nx.draw(g_odd_complete, pos=node_positions, node_size=20, alpha=0.05)

# Novo grafo apenas com as arestas do emparelhamento de peso mínimo
g_odd_complete_min_edges = nx.Graph(odd_matching)
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, edge_color='blue', node_color='red')

plt.title('Min Weight Matching on Complete Graph')
plt.show()

Para mostrar como isso se encaixa no grafo original, plote os mesmos pares mínimos (linhas azuis), mas sobre o mapa de trilhas (esmaecido) em vez do grafo completo. Novamente, as linhas azuis são o caminho em linha reta (não trilhas reais). Ainda falta um pouco de trabalho para encontrar as arestas que compõem o menor caminho entre cada par no passo 3.

plt.figure(figsize=(8, 6))

# Plot do grafo original (mapa de trilhas)
nx.draw(g, pos=node_positions, node_size=20, alpha=0.1, node_color='black')

# Sobrepor as arestas do emparelhamento mínimo
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, alpha=1, node_color='red', edge_color='blue')

plt.title('Min Weight Matching on Orginal Graph')
plt.show()

Passo 2.5: aumentar o grafo original

Agora, aumente o grafo original com as arestas do emparelhamento calculado no 2.4. Abaixo, definimos uma função simples que também marca que essas novas arestas vieram do grafo aumentado. Você vai precisar disso no 3. quando criar o circuito euleriano.

def add_augmenting_path_to_graph(graph, min_weight_pairs):
    """
    Add the min weight matching edges to the original graph
    Parameters:
        graph: NetworkX graph (original graph from trailmap)
        min_weight_pairs: list[tuples] of node pairs from min weight matching
    Returns:
        augmented NetworkX graph
    """

    # Precisamos transformar em MultiGraph para permitir arestas paralelas
    graph_aug = nx.MultiGraph(graph.copy())
    for pair in min_weight_pairs:
        graph_aug.add_edge(pair[0],
                           pair[1],
                           attr_dict={'distance': nx.dijkstra_path_length(graph, pair[0], pair[1]),
                                      'trail': 'augmented'}
                          )
    return graph_aug

Vamos confirmar que o grafo aumentado adiciona o número esperado (18) de arestas:

# Criar o grafo aumentado: adicionar as arestas do emparelhamento mínimo a g
g_aug = add_augmenting_path_to_graph(g, odd_matching)

# Contagens
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of edges in augmented graph: {}'.format(len(g_aug.edges())))

Number of edges in original graph: 123
Number of edges in augmented graph: 141

E confirmar que agora todo nó tem grau par:

pd.value_counts(g_aug.degree())

4    54
2    18
6     5
dtype: int64

CPP passo 3: calcular o circuito euleriano

Agora que você tem um grafo com todos os graus pares, o trabalho pesado de otimização acabou. Como Euler postulou em 1736 no problema das Sete Pontes de Königsberg, existe um caminho que visita cada aresta exatamente uma vez se todos os nós têm grau par. Carl Hierholzer provou formalmente isso na década de 1870.

Há muitos circuitos eulerianos com a mesma distância. Você resolve 90% com a função eulerian_circuit do NetworkX. Mas há limitações.

Limitações que vamos contornar:

1. O grafo aumentado pode (e provavelmente vai) conter arestas que não existiam no grafo original. Para obter o circuito (sem atalhos pelo mato), é preciso decompor essas arestas aumentadas no caminho mais curto usando apenas arestas reais.

2. eulerian_circuit retorna apenas a ordem em que passamos pelos nós. Não retorna os atributos das arestas necessários para completar o circuito. Isso é necessário para controlar quais arestas já foram percorridas quando há múltiplas arestas entre dois nós.

Limitação que não vamos resolver:

3. Para poupar as pernas, você poderia relaxar a exigência do circuito euleriano de começar e terminar no mesmo nó. Um caminho euleriano (caso geral do circuito) também pode ser encontrado se houver exatamente dois nós de grau ímpar. Isso economizaria um pouco de volta... presumindo que você consiga carona de volta do outro lado do parque. Porém, no momento desta escrita, o NetworkX não fornece um algoritmo de Euler Path. O código do eulerian_circuit não é tão complicado e poderia ser adaptado, mas vamos manter simples aqui.

Circuito ingênuo

Vamos começar pela solução simples, porém incompleta:

naive_euler_circuit = list(nx.eulerian_circuit(g_aug, source='b_end_east'))

Como esperado, o tamanho do circuito euleriano ingênuo é igual ao número de arestas do grafo aumentado.

print('Length of eulerian circuit: {}'.format(len(naive_euler_circuit)))

Length of eulerian circuit: 141

A saída é uma lista de tuplas que representam pares de nós. Note que o primeiro nó de cada par é o mesmo que o segundo do par anterior.

# Prévia do circuito euleriano ingênuo
naive_euler_circuit[0:10]

[('b_end_east', 'g_gy2'),
 ('g_gy2', 'b_g'),
 ('b_g', 'b_w'),
 ('b_w', 'b_gy2'),
 ('b_gy2', 'w_gy2'),
 ('w_gy2', 'b_w'),
 ('b_w', 'w_rs'),
 ('w_rs', 'g_rs'),
 ('g_rs', 'b_g'),
 ('b_g', 'b_rs')]

Circuito correto

Agora vamos definir uma função que usa o grafo original para dizer quais trilhas usar de A até B. Embora o código seja um pouco verboso, a lógica é simples. Transformamos o circuito ingênuo, que incluía arestas inexistentes no grafo original, em um circuito euleriano usando apenas arestas que existem no grafo original.

Percorra cada aresta do circuito ingênuo (naive_euler_circuit). Sempre que encontrar uma aresta que não exista no grafo original, substitua pela sequência de arestas que compõem o caminho mais curto entre seus nós no grafo original.

def create_eulerian_circuit(graph_augmented, graph_original, starting_node=None):
    """Create the eulerian path using only edges from the original graph."""
    euler_circuit = []
    naive_circuit = list(nx.eulerian_circuit(graph_augmented, source=starting_node))

    for edge in naive_circuit:
        edge_data = graph_augmented.get_edge_data(edge[0], edge[1])    

        if edge_data[0]['trail'] != 'augmented':
            # Se `edge` existe no grafo original, pegue os atributos e adicione ao circuito euleriano.
            edge_att = graph_original[edge[0]][edge[1]]
            euler_circuit.append((edge[0], edge[1], edge_att))
        else:
            aug_path = nx.shortest_path(graph_original, edge[0], edge[1], weight='distance')
            aug_path_pairs = list(zip(aug_path[:-1], aug_path[1:]))

            print('Filling in edges for augmented edge: {}'.format(edge))
            print('Augmenting path: {}'.format(' => '.join(aug_path)))
            print('Augmenting path pairs: {}\n'.format(aug_path_pairs))

            # Se `edge` não existe no grafo original, encontre o caminho mais curto entre seus nós e
            #  adicione os atributos de cada aresta do caminho.
            for edge_aug in aug_path_pairs:
                edge_aug_att = graph_original[edge_aug[0]][edge_aug[1]]
                euler_circuit.append((edge_aug[0], edge_aug[1], edge_aug_att))

    return euler_circuit

Contornamos a limitação 3 começando o circuito euleriano no extremo leste do parque, na trilha azul (nó "b_end_east"). Ao executar de verdade, você pode simplesmente ignorar a última direção, que volta ao início.

Mensagens verbosas foram adicionadas para mostrar o que acontece quando você substitui arestas inexistentes no grafo aumentado pelo caminho mais curto usando arestas reais.

# Criar o circuito euleriano
euler_circuit = create_eulerian_circuit(g_aug, g, 'b_end_east')

Filling in edges for augmented edge: ('b_end_east', 'g_gy2')
Augmenting path: b_end_east => b_y => b_o => b_gy2 => w_gy2 => g_gy2
Augmenting path pairs: [('b_end_east', 'b_y'), ('b_y', 'b_o'), ('b_o', 'b_gy2'), ('b_gy2', 'w_gy2'), ('w_gy2', 'g_gy2')]

Filling in edges for augmented edge: ('b_bw', 'rh_end_tt_1')
Augmenting path: b_bw => b_tt_1 => rh_end_tt_1
Augmenting path pairs: [('b_bw', 'b_tt_1'), ('b_tt_1', 'rh_end_tt_1')]

Filling in edges for augmented edge: ('b_tt_3', 'rt_end_north')
Augmenting path: b_tt_3 => b_tt_2 => tt_rt => v_rt => rt_end_north
Augmenting path pairs: [('b_tt_3', 'b_tt_2'), ('b_tt_2', 'tt_rt'), ('tt_rt', 'v_rt'), ('v_rt', 'rt_end_north')]

Filling in edges for augmented edge: ('rc_end_north', 'g_gy1')
Augmenting path: rc_end_north => v_rc => b_rc => g_rc => g_gy1
Augmenting path pairs: [('rc_end_north', 'v_rc'), ('v_rc', 'b_rc'), ('b_rc', 'g_rc'), ('g_rc', 'g_gy1')]

Filling in edges for augmented edge: ('y_gy1', 'rc_end_south')
Augmenting path: y_gy1 => y_rc => rc_end_south
Augmenting path pairs: [('y_gy1', 'y_rc'), ('y_rc', 'rc_end_south')]

Filling in edges for augmented edge: ('b_end_west', 'rd_end_south')
Augmenting path: b_end_west => b_v => rd_end_south
Augmenting path pairs: [('b_end_west', 'b_v'), ('b_v', 'rd_end_south')]

Filling in edges for augmented edge: ('rh_end_north', 'rd_end_north')
Augmenting path: rh_end_north => v_rh => v_rd => rd_end_north
Augmenting path pairs: [('rh_end_north', 'v_rh'), ('v_rh', 'v_rd'), ('v_rd', 'rd_end_north')]

Filling in edges for augmented edge: ('v_end_east', 'rs_end_north')
Augmenting path: v_end_east => v_rs => rs_end_north
Augmenting path pairs: [('v_end_east', 'v_rs'), ('v_rs', 'rs_end_north')]

Filling in edges for augmented edge: ('y_gy2', 'rs_end_south')
Augmenting path: y_gy2 => y_rs => rs_end_south
Augmenting path pairs: [('y_gy2', 'y_rs'), ('y_rs', 'rs_end_south')]

Veja que o comprimento do circuito euleriano é maior que o do circuito ingênuo, o que faz sentido.

print('Length of Eulerian circuit: {}'.format(len(euler_circuit)))

Length of Eulerian circuit: 158

Calcular a solução do CPP

Texto

Aqui está a impressão da solução em texto:

# Prévia das primeiras 20 direções da solução do CPP
for i, edge in enumerate(euler_circuit[0:20]):
    print(i, edge)

0 ('b_end_east', 'b_y', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 1.32})
1 ('b_y', 'b_o', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.08})
2 ('b_o', 'b_gy2', {'color': 'blue', 'estimate': 1, 'trail': 'b', 'distance': 0.05})
3 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
4 ('w_gy2', 'g_gy2', {'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.05})
5 ('g_gy2', 'b_g', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
6 ('b_g', 'b_w', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.16})
7 ('b_w', 'b_gy2', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.41})
8 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
9 ('w_gy2', 'b_w', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.42})
10 ('b_w', 'w_rs', {'color': 'gray', 'estimate': 1, 'trail': 'w', 'distance': 0.06})
11 ('w_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.18})
12 ('g_rs', 'b_g', {'color': 'green', 'estimate': 1, 'trail': 'g', 'distance': 0.05})
13 ('b_g', 'b_rs', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.07})
14 ('b_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.11})
15 ('g_rs', 'g_rc', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
16 ('g_rc', 'g_gy1', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.37})
17 ('g_gy1', 'g_rt', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.26})
18 ('g_rt', 'g_w', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.31})
19 ('g_w', 'o_w_1', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.18})

Dá para notar rapidamente que o algoritmo não é fiel a uma trilha específica, pulando de uma para outra. Uma extensão dessa abordagem poderia incorporar algum tipo de "fidelidade à trilha" na função objetivo para tornar a corrida mais amigável.

Estatísticas

Vamos dar uma olhada na sua solução para ver se está razoável.
(Não precisa se prender ao código verboso; foque na saída)

# Computando algumas estatísticas
total_mileage_of_circuit = sum([edge[2]['distance'] for edge in euler_circuit])
total_mileage_on_orig_trail_map = sum(nx.get_edge_attributes(g, 'distance').values())
_vcn = pd.value_counts(pd.value_counts([(e[0]) for e in euler_circuit]), sort=False)
node_visits = pd.DataFrame({'n_visits': _vcn.index, 'n_nodes': _vcn.values})
_vce = pd.value_counts(pd.value_counts([sorted(e)[0] + sorted(e)[1] for e in nx.MultiDiGraph(euler_circuit).edges()]))
edge_visits = pd.DataFrame({'n_visits': _vce.index, 'n_edges': _vce.values})

# Impressão das estatísticas
print('Mileage of circuit: {0:.2f}'.format(total_mileage_of_circuit))
print('Mileage on original trail map: {0:.2f}'.format(total_mileage_on_orig_trail_map))
print('Mileage retracing edges: {0:.2f}'.format(total_mileage_of_circuit-total_mileage_on_orig_trail_map))
print('Percent of mileage retraced: {0:.2f}%\n'.format((1-total_mileage_of_circuit/total_mileage_on_orig_trail_map)*-100))

print('Number of edges in circuit: {}'.format(len(euler_circuit)))
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of nodes in original graph: {}\n'.format(len(g.nodes())))

print('Number of edges traversed more than once: {}\n'.format(len(euler_circuit)-len(g.edges())))  

print('Number of times visiting each node:')
print(node_visits.to_string(index=False))

print('\nNumber of times visiting each edge:')
print(edge_visits.to_string(index=False))

Mileage of circuit: 33.59
Mileage on original trail map: 25.76
Mileage retracing edges: 7.83
Percent of mileage retraced: 30.40%

Number of edges in circuit: 158
Number of edges in original graph: 123
Number of nodes in original graph: 77

Number of edges traversed more than once: 35

Number of times visiting each node:
n_nodes  n_visits
     18         1
     38         2
     20         3
      1         4

Number of times visiting each edge:
n_edges  n_visits
     88         1
     35         2

Visualizar a solução do CPP

Embora o NetworkX também ofereça funcionalidades para visualizar grafos, eles são humildes nesse quesito:

O NetworkX fornece funcionalidades básicas para visualização de grafos, mas seu principal objetivo é permitir a análise, não a visualização. No futuro, a visualização pode ser removida do NetworkX ou oferecida apenas como add-on.

Visualizar grafos direito é difícil, e recomendamos o uso de ferramentas dedicadas. Exemplos notáveis: Cytoscape, Gephi, Graphviz e, para LaTeX, PGF/TikZ.

Dito isso, a função de desenho do NetworkX com matplotlib é poderosa o suficiente para uma inspeção visual básica, então vamos com draw neste tutorial.

Eu usei o graphviz e a linguagem dot para visualizar a solução no meu pacote Python postman_problems. Embora tenha dado trabalho converter a estrutura do NetworkX para dot, isso libera mais qualidade e controle nos gráficos.

Criar o grafo do CPP

O primeiro passo é converter a lista de arestas a percorrer no circuito euleriano em uma lista de arestas com atributos amigáveis para plot.

create_cpp_edgelist cria uma lista de arestas com atributos extras que vamos usar no plot:

• sequence: registra a ordem em que cada aresta é percorrida.
• visits: número de vezes que percorremos uma determinada aresta.

def create_cpp_edgelist(euler_circuit):
    """
    Create the edgelist without parallel edge for the visualization
    Combine duplicate edges and keep track of their sequence and # of walks
    Parameters:
        euler_circuit: list[tuple] from create_eulerian_circuit
    """
    cpp_edgelist = {}

    for i, e in enumerate(euler_circuit):
        edge = frozenset([e[0], e[1]])

        if edge in cpp_edgelist:
            cpp_edgelist[edge][2]['sequence'] += ', ' + str(i)
            cpp_edgelist[edge][2]['visits'] += 1

        else:
            cpp_edgelist[edge] = e
            cpp_edgelist[edge][2]['sequence'] = str(i)
            cpp_edgelist[edge][2]['visits'] = 1

    return list(cpp_edgelist.values())

Vamos criar a lista de arestas do CPP:

cpp_edgelist = create_cpp_edgelist(euler_circuit)

Como esperado, sua lista de arestas tem o mesmo número de arestas do grafo original.

print('Number of edges in CPP edge list: {}'.format(len(cpp_edgelist)))

Number of edges in CPP edge list: 123

A lista do CPP é semelhante a euler_circuit, só que com alguns atributos adicionais.

# Prévia da lista de arestas para plot
cpp_edgelist[0:3]

[('rh_end_tt_4',
  'nature_end_west',
  {'color': 'black',
   'distance': 0.2,
   'estimate': 0,
   'sequence': '73',
   'trail': 'tt',
   'visits': 1}),
 ('rd_end_south',
  'b_rd',
  {'color': 'red',
   'distance': 0.13,
   'estimate': 0,
   'sequence': '95',
   'trail': 'rd',
   'visits': 1}),
 ('w_gy1',
  'w_rc',
  {'color': 'gray',
   'distance': 0.33,
   'estimate': 0,
   'sequence': '151',
   'trail': 'w',
   'visits': 1})]

Agora, vamos criar o grafo:

# Criar grafo da solução do CPP
g_cpp = nx.Graph(cpp_edgelist)

Visualização 1: voltando pelo mesmo caminho

Aqui, mostramos quais arestas são percorridas uma vez (cinza) e mais de uma vez (azul). Esta é a versão "correta" da visualização do 2.4, que mostrava as conexões ingênuas (em linha reta) entre os pares de nós ímpares (vermelho). Agora, corrigimos traçando o caminho mais curto pelas arestas que realmente existem para cada par de nós ímpares.

Se a otimização estiver boa, as linhas azuis devem representar a menor distância possível — especificamente, a distância mínima necessária para gerar um emparelhamento dos nós de grau ímpar.

plt.figure(figsize=(14, 10))

visit_colors = {1:'lightgray', 2:'blue'}
edge_colors = [visit_colors[e[2]['visits']] for e in g_cpp.edges(data=True)]
node_colors = ['red'  if node in nodes_odd_degree else 'lightgray' for node in g_cpp.nodes()]

nx.draw_networkx(g_cpp, pos=node_positions, node_size=20, node_color=node_colors, edge_color=edge_colors, with_labels=False)
plt.axis('off')
plt.show()

Visualização 2: sequência da solução do CPP

Aqui, plote o grafo original (mapa de trilhas) anotado com os números da sequência em que percorremos as trilhas segundo a solução. Números repetidos indicam trilhas em que precisamos voltar.

Você começa na trilha azul, no canto inferior direito (0ª e 157ª direções).

plt.figure(figsize=(14, 10))

edge_colors = [e[2]['color'] for e in g_cpp.edges(data=True)]
nx.draw_networkx(g_cpp, pos=node_positions, node_size=10, node_color='black', edge_color=edge_colors, with_labels=False, alpha=0.5)

bbox = {'ec':[1,1,1,0], 'fc':[1,1,1,0]}  # hack para rotular sobre a linha
edge_labels = nx.get_edge_attributes(g_cpp, 'sequence')
nx.draw_networkx_edge_labels(g_cpp, pos=node_positions, edge_labels=edge_labels, bbox=bbox, font_size=6)

plt.axis('off')
plt.show()

Visualização 3: animação

A animação abaixo traça o circuito euleriano do começo ao fim. As arestas ficam pretas na primeira passagem e vermelhas na segunda.

Note que o gif não faz justiça visual a arestas que se sobrepõem a outras ou são pequenas demais para visualizar bem. Uma lib mais robusta, como o graphviz, poderia traçar splines em vez de linhas retas entre nós.

O código que a cria está abaixo como referência.

Primeiro, é gerada uma imagem PNG para cada direção (aresta percorrida) da solução do CPP.

visit_colors = {1:'black', 2:'red'}
edge_cnter = {}
g_i_edge_colors = []
for i, e in enumerate(euler_circuit, start=1):

    edge = frozenset([e[0], e[1]])
    if edge in edge_cnter:
        edge_cnter[edge] += 1
    else:
        edge_cnter[edge] = 1

    # Grafo completo (fundo esmaecido)
    nx.draw_networkx(g_cpp, pos=node_positions, node_size=6, node_color='gray', with_labels=False, alpha=0.07)

    # Arestas percorridas até a iteração i
    euler_circuit_i = copy.deepcopy(euler_circuit[0:i])
    for i in range(len(euler_circuit_i)):
        edge_i = frozenset([euler_circuit_i[i][0], euler_circuit_i[i][1]])
        euler_circuit_i[i][2]['visits_i'] = edge_cnter[edge_i]
    g_i = nx.Graph(euler_circuit_i)
    g_i_edge_colors = [visit_colors[e[2]['visits_i']] for e in g_i.edges(data=True)]

    nx.draw_networkx_nodes(g_i, pos=node_positions, node_size=6, alpha=0.6, node_color='lightgray', with_labels=False, linewidths=0.1)
    nx.draw_networkx_edges(g_i, pos=node_positions, edge_color=g_i_edge_colors, alpha=0.8)

    plt.axis('off')
    plt.savefig('fig/png/img{}.png'.format(i), dpi=120, bbox_inches='tight')
    plt.close()

Depois, as PNGs são unidas para formar o gif.

Primeiro, as PNGs são ordenadas de 0 a 157. Em seguida, são combinadas usando imageio a 3 quadros por segundo para criar o gif.

import glob
import numpy as np
import imageio
import os

def make_circuit_video(image_path, movie_filename, fps=5):
    # ordenando arquivos
    filenames = glob.glob(image_path + 'img*.png')
    filenames_sort_indices = np.argsort([int(os.path.basename(filename).split('.')[0][3:]) for filename in filenames])
    filenames = [filenames[i] for i in filenames_sort_indices]

    # criar o vídeo
    with imageio.get_writer(movie_filename, mode='I', fps=fps) as writer:
        for filename in filenames:
            image = imageio.imread(filename)
            writer.append_data(image)

make_circuit_video('fig/png/', 'fig/gif/cpp_route_animation.gif', fps=3)

Próximos passos

Parabéns, você concluiu este tutorial resolvendo o Problema do Carteiro Chinês em Python. Percorremos bastante chão aqui (33,6 milhas de trilhas, para ser exato). Para se aprofundar em fundamentos de redes, vale conferir o curso da Datacamp Network Analysis in Python, que traz um tratamento mais completo dos conceitos centrais.

Não deixe de consultar a documentação do NetworkX para aprender mais sobre como criar, manipular e percorrer essas redes complexas. A doc é completa, com vários exemplos e uma série de tutoriais.

Se quiser resolver o CPP no seu próprio grafo, empacotei as funcionalidades deste tutorial no pacote Python postman_problems no Github. Você também pode juntar os blocos de código deste tutorial com outra lista de arestas e nós, mas o postman_problems provavelmente vai te levar lá de forma mais rápida e limpa.

Um dia pretendo implementar aqui as extensões do CPP (Rural e Windy Postman Problem). Também tenho ambições de escrever sobre essas extensões e sobre a experiência de testar as rotas nas trilhas no meu blog aqui. Outra aplicação que quero explorar é incorporar coordenadas lat/long para desenvolver (ou usar) um mecanismo de enviar direções passo a passo para meu relógio Garmin.

E, claro, um último próximo passo: sair e correr a rota!

Se você quer aprender mais sobre redes em Python, confira estes cursos da DataCamp:

Introduction to Network Analysis in Python

Intermediate Network Analysis in Python

Referências

1: Edmonds, Jack (1965). "Paths, trees, and flowers". Canad. J. Math. 17: 449–467.
2: Galil, Z. (1986). "Efficient algorithms for finding maximum matching in graphs". ACM Computing Surveys. Vol. 18, No. 1: 23-38.