Get best of the week

Verificando o isomorfismo de dois gráficos e localizando subgráficos isomórficos: uma abordagem baseada na análise de caminhos NB

Olá a todos.

Existe essa tarefa - verificar se dois gráficos são isomórficos um para o outro. Ou seja, para simplificar, descobrir se esses dois gráficos são "iguais", mas com números de vértices diferentes e, se os gráficos forem especificados graficamente, com diferentes localizações espaciais. A solução para esse problema não é tão óbvia quanto parece a alguém à primeira vista: mesmo para gráficos pequenos, uma olhada em sua representação gráfica nem sempre dará uma resposta inequívoca. Veja, por exemplo, um desenho no mesmo Wiki: en.wikipedia.org/wiki/Graph_isomorphism#Example .

Bem, obviamente?

Mas há uma tarefa mais difícil: pesquisar em um gráfico “grande” todos os subgráficos isomórficos para outro gráfico “menor”. Essa é uma floresta ainda mais sombria. Obviamente, isso não é totalmente obscuro, mas a tarefa, você vê, não é a mais fácil.

O que temos então?

1. Por que tudo isso é necessário?


E embora o problema dos (sub) gráficos isomórficos, como já mencionamos, seja complicado, é bastante necessário e útil. Pelo que? E então, por exemplo, pesquisar no banco de dados por compostos químicos semelhantes a uma dada molécula por sua fórmula estrutural. Afinal, pode ser imaginado como um gráfico, certo? A quimioinformática faz isso - existe essa ciência. Mas também existem tarefas de comparação com a amostra, várias tarefas bioinformáticas e muitas outras coisas interessantes.

2. Como resolver este problema?


A abordagem clássica para resolver este problema foi estabelecida por J. Ullman em 1976 [3], mais tarde ele melhorou substancialmente seu algoritmo [4]. Além disso, essa abordagem foi desenvolvida nos trabalhos de muitos outros autores, por exemplo, Cordella et al. [2] (algoritmo VF2), Bonnitsi et al. [1] (algoritmo RI), etc.

Em suma, a essência dessa abordagem é “inteligente enumerando ”as possíveis correspondências dos vértices do gráfico de amostra B e do gráfico A nos quais ele está sendo pesquisado. Essa pesquisa torna "inteligente" inserir várias condições e restrições que permitem eliminar opções inadequadas o mais cedo possível. Também para esses fins, vários processamentos preliminares dos dados de origem podem ser realizados.

Não nos envolveremos em recontar essas obras aqui, mas convidaremos o leitor a se familiarizar com elas de forma independente. No entanto, “um programa é melhor que um pedido”, e deve-se notar que existem bons exemplos gráficos e explicações desses algoritmos na Web. Veja, por exemplo, o seguinte:
coderoad.ru/17480142/Is-or-simple-example-for-explanation-algorithm-Ulman - uma explicação muito boa e clara com um exemplo,
issue.life/questions/8176298 - etapas do algoritmo VF2 com um exemplo .

No entanto, surge a pergunta - existem outras maneiras e abordagens possíveis para resolver esse problema, embora em alguns casos especiais? E gostaria de apresentar uma das respostas possíveis para esta pergunta.

2. Isomorfismo de gráficos e caminhos NB


Vamos concordar imediatamente: em caminhos NB (e não em inglês, mas simplesmente porque é muito mais curto), chamaremos caminhos máximos sem ramificação, ou seja, caminhos não ramificados, no máximo, longos de algum gráfico.

Portanto, se tivermos dois gráficos isomórficos entre si , então para qualquer representação do primeiro gráfico como uma sequência de caminhos sem ramificação estendidos ao máximo (ou seja, esses de nossos caminhos NB), sempre existe uma representação correspondente do segundo gráfico correspondente a ele e ao mesmo tempo:

  • para gráficos direcionados, os caminhos correspondentes um ao outro serão alinhados,
  • os graus dos vértices correspondentes um ao outro para gráficos não direcionados (e para gráficos orientados, o número de arestas de entrada e saída, respectivamente) serão iguais a
  • ao "combinar" essas representações como resultado, teremos uma correspondência dos vértices do primeiro e do segundo gráficos.

Um exemplo . Gráfico A = {1-> 2, 1-> 6, 4-> 5, 5-> 1, 3-> 3}. Gráfico B = {3-> 4, 3-> 5, 1-> 2, 2-> 3, 6-> 6}
CaminhosA (caminhos máximos sem ramificação de A ): 1-> 2, 1-> 6, 4-> 5-> 1, 3-> 3
caminhosB (caminhos máximos sem ramificação de B ): 3-> 4, 3-> 5, 1-> 2-> 3, 6-> 6 Correspondência de vértices
: 1 ( A): 3 (B), 2 (A): 4 (B), 6 (A): 5 (B), 4 (A): 1 (B), 5 (A): 2 (B), 3 ( A): 6 (B).

Assim, a tarefa de verificar o isomorfismo de dois gráficos pode ser resolvida encontrando esses caminhos correspondentes um ao outro e, em seguida, verificando a igualdade das matrizes de adjacência construídas com base em sua conservação da ordem dos vértices nas sequências de caminhos obtidas (cada vértice é adicionado à sequência uma vez, primeira "menção"). Em nosso exemplo, as seguintes ordens de vértices serão usadas para construir matrizes de adjacência:

A : 1, 2, 6, 4, 5, 3
B : 3, 4, 5, 1, 2, 6

Matriz de adjacência para A para uma determinada ordem de vértices:

imagem

Matriz de adjacência para B para uma determinada ordem de vértices:

imagem

As matrizes são iguais e, portanto, os gráficos A e B são isomórficos.

Além disso, essa abordagem (1) é aplicável a gráficos orientados e não orientados, (2) é aplicável a gráficos que contêm mais de um componente conectado / fortemente conectado, (3) é aplicável a gráficos que contêm múltiplas (múltiplas) arestas e loops, no entanto (4) não leva em consideração os vértices para os quais não existem arestas.

3. Bem, verifiquei o isomorfismo dos gráficos. Mas e a busca por subgráficos?


E aqui, francamente, tudo é muito mais complicado. Aqui teremos a seguinte restrição: com base na própria essência do método, você pode encontrar não nenhum, mas apenas subgráficos "inscritos" . E chamaremos o subgrafo "inscrito" do gráfico A como um subgrafo que pode ser "colado" a outras partes do gráfico A apenas devido a arestas incidentes apenas nos vértices de contorno dos seus caminhos não ramificados (subgráfico) de comprimento máximo (além disso, o gráfico A pode conter outros componentes conectados). Não se preocupe, abaixo será um exemplo e tudo ficará mais claro.

Além disso, ao resolver esse problema, além de procurar a correspondência dos caminhos NB dos gráficos A e B em comprimento (como foi o caso do teste de isomorfismo acima), também é necessário procurar separadamente as seguintes correspondências possíveis entre eles:

  • Correspondência de caminhos NB - cadeias simples do gráfico B para caminhos NB - cadeias simples / ciclos simples do gráfico A. Além disso, inicialmente esses caminhos no gráfico A podem ser mais longos - nesse caso, seus segmentos são tomados em comprimento igual ao caminho desejado de B.
  • Correspondência entre os caminhos NB- "finais" do gráfico B e quaisquer caminhos NB do gráfico A (neste caso, os caminhos do gráfico A também podem ser mais longos - nesse caso, seus segmentos são tomados em comprimento igual ao caminho desejado do gráfico B).

Vejamos um exemplo:

imagem

Ao procurar um subgrafo isomórfico "inscrito" do gráfico B na coluna A (veja a figura acima), as seguintes correspondências serão encontradas:

  • caminho interno 2-> 3-> 4 da coluna B: caminho interno 2-> 3-> 4 da coluna A,
  • caminhos finais 1-> 2 e 10-> 2 da coluna B: caminho final 0-> 2 da coluna A e um fragmento do caminho final 7-> 1-> 2 da coluna A, nomeadamente 1-> 2,
  • 7->8 B: 9->10->11 A, 9->10 10->11, 12->13->14->12 A, 12->13, 13->14, 14->12.

Assim, como os subgráficos "inscritos" do gráfico A que são isomórficos ao gráfico B, as 5 opções a seguir podem ser encontradas:

A1 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 9-> 10}
A2 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 10-> 11}
A3 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 12-> 13}
A4 = {0-> 2, 1-> 2, 2 -> 3, 3-> 4, 4-> 5, 4-> 6, 13-> 14}
A5 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 14-> 12}

No entanto, se adicionarmos uma aresta adicional 3-> 8 ao gráfico A, obtemos o gráfico A '(abaixo na mesma figura). E em A ', não haverá mais subgráficos "inscritos" isomórficos no gráfico B. De fato: a aresta 3-> 8 "divide" o caminho 2-> 3-> 4 do gráfico A em dois e, portanto, caminhos candidatos para o caminho interno 2 ->3-> 4 colunas B não serão encontradas.

4. Agora, o próprio algoritmo


Agora, podemos avançar para uma consideração mais detalhada do algoritmo de pesquisa para os subgráficos "inscritos" na coluna A que são isomórficos para alguma coluna B.

Portanto, o algoritmo consistirá em 4 estágios:

  • Pré-processando
  • Coincidindo
  • Desbaste,
  • Conclusão

Etapa I. Pré-processamento


Nesta fase, encontramos todos os caminhos NB para cada um dos gráficos, bem como avaliamos os fatores que limitam o espaço de escolha durante a enumeração. Essa. fazemos o seguinte:

  1. Encontramos todos os caminhos NB na coluna A e os colocamos em uma matriz dinâmica (em C ++ - em um vetor)
  2. Encontramos todos os caminhos NB na coluna B e os colocamos em uma matriz dinâmica (vetor)
  3. A B. II-IV , 1. A- B B: - , B.
  4. A B ( ).
  5. A B: DA DB .
  6. – B00 – B , , .

Portanto, temos caminhos NB nos gráficos e nos parâmetros limite da p.p. 3-5.

Estágio II. Mapeamento


Nesse estágio, selecionaremos os caminhos NB candidatos (a seguir denominados simplesmente "caminhos candidatos") da coluna A para cada um dos caminhos NB da coluna B. Marcando cada caminho candidato de PathsA para cada i-ésimo caminho PathsB [i ] será gravado em uma matriz dinâmica bidimensional (em C ++ - em um vetor de vetores) NPaths - respectivamente no i-ésimo vetor (i-ésima linha) - na forma de um triplo ordenado de números: o número do caminho correspondente no PathsA - o número da posição inicial nele - o comprimento do caminho .

Por exemplo, PathsB [2] = {1, 0, 3, 3, 1, 3} significa que os caminhos dos PathsB [2] estão associados a 2 caminhos candidatos de A: from PathsA [1] - os três primeiros elementos do caminho a partir de zero ( inicial) e de PathsA [3] - também 3 elementos começando do primeiro (próximo ao inicial).

Ao mesmo tempo, procuraremos (selecionar) caminhos candidatos em 4 direções:

  1. Pesquise caminhos candidatos para todos os caminhos NB internos do gráfico B em PathsB, ou seja, aqueles cujos dois vértices de limite estão conectados no gráfico B com pelo menos 2 outros vértices (independentemente da direção de tal conexão) e, ao mesmo tempo, esse caminho não é um ciclo simples (orientado para gráficos orientados).
  2. Procure caminhos candidatos para rastrear caminhos NB a partir de PathsB.
  3. Procure caminhos candidatos para caminhos NB - loops simples do PathsB.
  4. Procure caminhos candidatos para caminhos NB - caminhos simples do PathsB.

Ao selecionar caminhos candidatos para cada i-ésimo caminho do PathsB, eles são comparados (é aqui que alguns dos parâmetros limitadores previamente calculados são úteis):

  • seu comprimento e o comprimento do caminho candidato (deve ser igual para os casos 1 e 3 e, para os casos 2 e 4, o caminho candidato do PathsA também pode ser mais longo),
  • os graus de seus vértices de limite e os vértices correspondentes do caminho candidato (para vértices do caminho candidato, esses valores devem ser pelo menos o caminho de PathsB).

Se, de acordo com os resultados do estágio II, não foi encontrado nenhum caminho candidato do PathsA para nenhum dos caminhos do PathsB, considera-se que A não contém subgráficos "inscritos" isomórficos da coluna B.

Desbaste


Agora vamos tentar "apertar" o gráfico A. Deixamos nele apenas as arestas que foram para os caminhos candidatos que encontramos. Se, ao mesmo tempo, o gráfico A perdeu pelo menos uma aresta em comparação com seu estado inicial, retornamos ao estágio I "Pré-processamento": os graus dos vértices do gráfico A e, consequentemente, a lista de caminhos candidatos pode ser reduzida e, consequentemente, o espaço de pesquisa pode ser reduzido.

Estágio III. Diluindo a lista de caminhos candidatos


O objetivo desta etapa é eliminar ainda mais o maior número possível de candidatos inapropriados. Para fazer isso, realizamos as seguintes etapas.

  1. A exclusão de caminhos candidatos obviamente inadequados com base nas distâncias mínimas entre os vértices na coluna B. O caminho candidato para cada PathsB [i] para o qual pelo menos um PathsB [j] nenhum caminho candidato foi encontrado pelo menor tempo a distância entre seus vértices limites na coluna A foi menor ou igual à menor distância entre os vértices limites correspondentes dos caminhos PathsB [i] e PathsB [j] do gráfico B.
  2. Uma exceção para todos os ciclos do PathsB para caminhos candidatos não cíclicos associados a ele e vice-versa.
  3. A exceção de caminhos candidatos semelhantes à Seção 1, mas não pelo critério da menor distância entre os vértices de contorno, mas por seus (vértices de contorno) à igualdade ou desigualdade mútua.

Por exemplo, se:

  • o elemento inicial do PathsB [i] não é igual ao elemento inicial do PathsB [j], e
  • o elemento final do PathsB [i] não é igual ao elemento final do PathsB [j], e
  • o elemento inicial do PathsB [i] é igual ao elemento final do PathsB [j], e
  • o elemento inicial do PathsB [j] não é igual ao elemento final do PathsB [i],

o caminho candidato ao longo do caminho PathsB [i] para o qual pelo menos um PathsB [j] não possui caminhos candidatos que satisfaçam a condição acima em relação à igualdade / desigualdade de seus (caminhos candidatos) inicial e final, respectivamente, está sujeito a exclusão picos.

Em outras palavras, descartamos os caminhos candidatos que obviamente não serão incluídos nos subgráficos desejados - com base na distância de todos os outros caminhos candidatos (esses caminhos estão muito longe de todos os outros), com base em sua ciclicidade / não ciclicidade e também com base na devida igualdade / desigualdade de seus vértices de limite com os vértices de outros caminhos candidatos.

Se, de acordo com os resultados do estágio III, pelo menos 1 caminho candidato foi excluído do PathsA, então - novamente - a coluna A é atualizada - apenas as arestas incluídas nos caminhos candidatos restantes permanecem nele. E, novamente, se ao mesmo tempo, o gráfico A “perder peso” em pelo menos uma aresta, voltaremos ao estágio I “Pré-processamento”: os graus dos vértices do gráfico A e, consequentemente, a lista de caminhos candidatos podem ser reduzidos e, consequentemente, reduzidos espaço de pesquisa.

Estágio IV. Conclusão


Cada combinação possível de todos os caminhos candidatos restantes define um subgráfico da coluna A. Para cada um desses subgráficos, uma matriz de adjacência é construída levando em consideração a ordem dos caminhos candidatos da mesma maneira que a matriz de adjacência B00 foi construída para o gráfico B e, em seguida, essas matrizes de adjacência são comparadas.

Se forem iguais, as multiplicidades das arestas são comparadas (consulte a Seção 3 do pré-processamento do estágio I). Se todas essas condições forem cumpridas, o subgrafo encontrado é considerado isomórfico no gráfico B e é adicionado ao conjunto de resultados encontrados.

Durante o estágio IV “Conclusão”, várias verificações adicionais podem ser usadas para acelerar a identificação e rejeição de um subgráfico inapropriado.

5. Como tudo está confuso ... Considere um exemplo do algoritmo


Eu não sei sobre você, mas seria incompreensível para mim sem um exemplo. Vejamos um exemplo.

Na fig. os gráficos abaixo são A = {1-> 2, 2-> 5, 5-> 15, 16-> 15, 5-> 5, 5-> 5, 5-> 4, 5-> 6, 7-> 6 , 6-> 8, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 0-> 12, 4-> 13, 13-> 14, 14-> 4 } e B = {1-> 1, 4-> 5, 5-> 1, 1-> 3, 3-> 3, 3-> 2, 2-> 7, 2-> 8, 9-> 10, 10-> 9, 1-> 6, 6-> 11, 11-> 12, 12-> 6}. Nossa tarefa é encontrar no gráfico A todos os subgráficos "inscritos" isomórficos ao gráfico B. O resultado também é mostrado na figura: os vértices e arestas encontrados do gráfico A são destacados por uma linha espessa e os números dos vértices correspondentes do gráfico B são indicados entre colchetes (se houver várias opções, eles serão indicados por fração).

imagem

Ao resolver o problema de pesquisa na coluna A dos subgráficos "inscritos" isomórficos à coluna B,nós temos os seguintes resultados do algoritmo.

Estágio I: Todas as ações e cálculos foram realizados de acordo com a p.p. 1-5 desta etapa, a seguir estão os PathsA e PathsB resultantes.

CaminhosA:

1-> 2-> 5
4-> 13-> 14 4
5-> 4
5-> 5
5-> 6
5-> 15
6-> 6
6-> 8
6-> 9
7-> 6
9 -> 10
9-> 11
16-> 15
0-> 12-> 0

CaminhosB:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4- > 5-> 1
6-> 11-> 12-> 6
9-> 10-> 9

Fases II-III. A comparação mostrou que para cada caminho do PathsA existe pelo menos um caminho candidato do PathsB, e o PathsA foi reduzido pelos resultados do desbaste preliminar. Na fase de desbaste principal (III), não ocorreu mais redução de PathsA. Como resultado, os CaminhosA e os CaminhosB assumiram a forma:

CaminhosA:

1-> 2-> 5
4-> 13-> 14-> 4
5-> 4
5-> 5
5-> 6
6-> 6
6-> 9
9-> 10
9-> 11
0-> 12-> 0

CaminhosB:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4-> 5-> 1
6 -> 11-> 12-> 6
9-> 10->9

A comparação final dos NPaths é:
NPaths:

i = 0: 3 0 2
i = 1: 4 0 2
i = 2: 2 0 2
i = 3: 7 0 2 8 0 2
i = 4: 7 0 2 8 0 2
i = 5: 6 0 2
i = 6: 5 0 2
i = 7: 0 0 3
i = 8: 1 0 4
i = 9: 9 0 3

Aqui é o momento de lembrar que cada trigêmeo ordenado de números nos NPaths [i] define o caminho candidato correspondente PathsB [i] de A no formato: o número do caminho correspondente de PathsA - a posição inicial do segmento desse caminho - o comprimento do segmento. Assim, é fácil verificar se os caminhosB [0] = {1-> 1} (i = 0: 3 0 2) correspondem ao único caminho de A, a saber, o segmento de PathsA [3], começando desde o início e com um comprimento de 2.

Estágio IV. Como resultado, o único subgrafo A1 foi encontrado na coluna A isomórfica à coluna B. A1 = {0-> 12, 1-> 2, 2-> 5, 4-> 13, 5-> 4, 5-> 5, 5- > 6, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 13-> 14, 14-> 4}.

5. O que vem depois?


E então, em princípio, é tudo. Embora não exatamente: o autor deve admitir que o algoritmo ainda pode ser finalizado e finalizado. O que há para adicionar?

  1. Quando características adicionais dos vértices das colunas A e B são introduzidas (por exemplo, quando os compostos são dados pelos gráficos de compostos químicos, um código numérico correspondente a um e apenas um átomo (isótopo) pode ser associado a cada vértice), o processo de busca pode ser acelerado devido à maior precisão das comparações de acordo com o Estágio II: adicional a condição para selecionar caminhos candidatos será a correspondência dos rótulos dos vértices.
  2. . , «», «» - B.
  3. , , , «» :
    (1) «» , ,
    (2) .
    «» « - », , , .
  4. , - , .


Geral sobre os problemas:
1. Bonnici, V., Giugno, R., Pulvirenti, A. et al. Um algoritmo de isomorfismo de subgráfico e sua aplicação a dados bioquímicos. BMC Bioinformatics 14, S13 (2013). doi.org/10.1186/1471-2105-14-S7-S13 .
2. Cordella L, Foggia P, Sansone C, Vento M: A (Sub) Algoritmo de Isomorfismo de Gráfico para Correspondência de Gráficos Grandes. Transações IEEE em Análise de Padrões e Inteligência de Máquina. 2004, 26 (10): 1367-1372. 10.1109 / TPAMI.2004.75.
3. Ullmann Julian R.: Um algoritmo para Isomorfismo Subgráfico. Jornal da Associação de Máquinas de Computação. 1976, 23: 31-42. 10.1145 / 321921.321925.
4. Ullmann Julian R.: algoritmos de vetor de bits para satisfação de restrições binárias e isomorfismo de subgráficos. J Exp Algorithmics. 2011, 15 (1.6): 1.1-1.6. 1,64

A pré-impressão do autor escrita em uma linguagem mais oficial sobre esse é o "algoritmo baseado em caminhos NB", que também contém informações sobre uma tentativa de implementá-lo em C ++:
5. Chernoukhov SA 2020. Preprints.RU. Verificando o isomorfismo de dois gráficos e procurando subgráficos isomórficos "inscritos": uma abordagem baseada na análise de caminhos sem ramificação máxima estendida para solucionar o problema de isomorfismo (sub) gráfico. DOI: dx.doi.org/10.24108/preprints-3111977 Fontes

úteis da Internet sobre o tópico:
6. coderoad.ru/17480142/Is-li- exemplo simples de explicação de algoritmo-Ulman
7. issue.life/questions / 8176298 .

More articles:


All Articles