Para deixar claro do que se trata, darei o exemplo mais simples.
O gráfico é muito simples e, para esse tipo de gráfico, é fácil criar um algoritmo que selecione ciclos sem cordas (ou seja, ciclos que não têm autointerseções e não podem ser divididos em outros menores). O problema é que os gráficos podem ser muito mais complicados e todos os casos devem ser considerados. Por meio de deliberação, codificação, tentativa e erro, no final nasceu o algoritmo, que agora funciona em benefício dos garimpeiros de engenharia.
Descrição do texto:
- Para cada vértice do gráfico, encontramos todos os vértices adjacentes e começamos a formar um ciclo nos movendo em direção a cada vértice adjacente por vez.
- Se o número de vértices adjacentes (excluindo aquele com o qual você inseriu) = 0, então voltamos, formando um ciclo ---> item 5
- Se o número de vértices adjacentes (excluindo aquele com o qual você inseriu) for igual a 1, então iremos ao longo dele, formando um ciclo ---> item 5
- ( , ) >=2, ( ), , ---> .5
- — ? , ---> .2
- , .
- , , , .
- , , ---> .1 ( )
- Mais uma vez, percorremos o ciclo e olhamos para os ramos à esquerda dele. Tendo encontrado tais ramos, para cada um organizamos uma busca em largura (ou profundidade em primeiro lugar, não importa). Se ao mesmo tempo chegarmos ao topo do ciclo formado (exceto para o atual), então interrompemos a formação do ciclo e vamos para ---> item 1
- Anotamos o ciclo e vamos procurar um novo ---> item 1
Pseudocódigo maior:
No início, gráficos cada vez mais sofisticados foram construídos para testar o algoritmo.
ou
, no final, foi testado em todos os gráficos de exploração reais como este:
Não acho que seja o ideal, mas no momento (cerca de 3 anos já) funciona sem falhas e reclamações.
Não cito o código, é improvável que alguém se interesse, e será difícil extrair um pedaço, pois esta é apenas uma pequena parte do trabalho.