Simplificação de Grafos

[Baderous]

Dado um grafo direccionado que represente uma máquina de estados, existe algum algoritmo que permita detectar e remover:

- estados isolados (que não façam parte do grafo principal onde se encontra o estado inicial, ou seja, estão num grafo à parte)

- estados/transições redundantes, isto é, transições que possam ser removidas, e eventualmente os estados a si associados, aproveitando transições já existentes

?

Já andei a pesquisar os algoritmos mais conhecidos de Grafos e não encontrei nada...

[mike2mcc]

Assim de repente, lembrei-me de duas soluções possíveis (podem é não ser muito eficientes):

1. Construir um novo grafo a partir do original, da seguinte forma:

        adicionar o estado inicial e os caminhos e estados que estão acessíveis a partir dele; de seguida fazer o mesmo para cada estado que foi previamente adicionado, excepto o estado inicial. Assim constróis um novo grafo com todos os caminhos e estados que estão acessíveis a partir do inicial.

2. Percorrer todos os estados (excepto o inicial) e verificar se existe um caminho (ex: através do algoritmo de Dijkstra) entre o estado inicial e o estado a verificar, removendo aqueles estados em o caminho não exista.

[Baderous]

Assim de repente, lembrei-me de duas soluções possíveis (podem é não ser muito eficientes):

1. Construir um novo grafo a partir do original, da seguinte forma:

        adicionar o estado inicial e os caminhos e estados que estão acessíveis a partir dele; de seguida fazer o mesmo para cada estado que foi previamente adicionado, excepto o estado inicial. Assim constróis um novo grafo com todos os caminhos e estados que estão acessíveis a partir do inicial.

Pois eu já tinha pensado numa solução destas e foi o que acabei por fazer. Construí um grafo representativo da máquina de estados através de uma lista de adjacências e, de seguida, recolhi todos os estados que eram acessíveis a partir do estado inicial. Depois removi do grafo inicial aqueles estados que não faziam parte da lista dos estados recolhidos. Isto resolve-me apenas a parte do problema relativa aos nodos isolados. Mas falta-me a outra parte: identificar transições/estados redundantes.

Tenho aqui em mão o algoritmo de Hopcroft para simplificação de máquinas de estado finitas (que é o meu caso), mas isto está um bocado complexo, tenho de ver melhor.

Entretanto, cheguei à conclusão que para resolver o outro problema tenho de aplicar o algoritmo de simplificação de máquinas de estado, semelhante àquele que se usa para transformar máquinas de estado não determinísticas em determinísticas, tendo de agrupar os estados semelhantes. Não sei se me faço entender, quem já estudou o tema dos autómatos finitos determinísticos e não determinísticos, gramáticas regulares e etc, já deve ter dado isto, tem aqui um exemplo daquilo que pretendo fazer: http://docs.google.com/viewer?a=v&q=cache%3A0vOYgSNvT90J%3Aweb.cecs.pdx.edu%2F~mperkows%2Ftemp%2F021.Introduction-state-minimization-complete.pdf+eliminate+redundant+states+finite+state+machine&hl=pt-PT&gl=pt&sig=AHIEtbSTPfJxN5sn43nDQmC-ZfK2Qv174Q&pli=1

Alguém tem sugestões para fazer isto da melhor maneira?

[mogers]

Para o 1) acho que tem de ser como já discutiram: dfs a partir do estado inicial e ficar apenas com os nós visitados.

Para o 2) acho que o melhor é a minimização do autómato, tal como referiste. Penso que não há problema em disponibilizar o código da nossa biblioteca de algoritmos que usamos em concursos pela FEUP.

Eu creio que nunca usei este código, mas penso que implementa o algoritmo clássico de minimização de automatos que aprendemos nas aulas (descrito aqui).

struct dfa
{
  int nvertex;
  int nalphabet;
  int start;

  int symbols[256];
  int next[MAXV][MAXE];
  bool final[MAXV];
  void init(int nv, int na) { start = 0; nvertex = nv; nalphabet = na; memset(final, 0, sizeof(final)); }
};

dfa minimize(dfa & target)
{
  dfa minimal;
  bool different[MAXV][MAXV];
  int conversion[MAXV];

  bool done = false;
  int nvertex = 0;

  memset(different, 0, sizeof(different));

  /* Two states, initially, are different if one is final and the other one isn't */
  for (int i = 0; i < target.nvertex; i++)
    for (int j = i+1; j < target.nvertex; j++)
      different[i][j] = different[j][i] = target.final[i] != target.final[j];

  while (!done)
  {
    done = true;
    for (int i = 0; i < target.nvertex; i++)
      for (int j = i+1; j < target.nvertex; j++)
        if (!different[i][j])
          for (int k = 0; k < target.nalphabet; k++)
            if (different[target.next[i][k]][target.next[j][k]])
            { /* Two states are different if their 'next' states are different */
              done = !(different[i][j] = different[j][i] = true);
              break;
            }
  }

  /* Calculate the sets of different states */
  for (int i = 0; i < target.nvertex; i++)
    for (int j = 0; j <= i; j++)
      if (!different[i][j])
      { conversion[i] = i == j ? nvertex++ : conversion[j]; break; }

  /* Build the minimal DFA */
  minimal.init(nvertex, target.nalphabet);
  for (int i = 0; i < target.nvertex; i++)
    for (int k = 0; k < target.nalphabet; k++)
      minimal.next[conversion[i]][k] = conversion[target.next[i][k]];

  /* Fill the "final state" information on the minimal DFA */
  for (int i = 0; i < target.nvertex; i++)
    minimal.final[conversion[i]] = target.final[i];

  memcpy(minimal.symbols, target.symbols, sizeof(minimal.symbols));
  return minimal;
}

[lesiano]

Eish que cena mais complicada. O algoritmo de Hopcroft não o tens na biblioteca? Obg.

[mogers]

Não temos (nunca usei isto num exercício, acho que este só está lá devido a ser dado numa cadeira e alguém implementou). Isto não me parece assim tão complicado...

Dei uma vista de olhos rápida no google e o algoritmo de Hopcroft é mais complexo do que este em termos teóricos. Não faço ideia se tem uma implementação mais pequena. Eu não o estudei.

[Baderous]

Obrigado pelo contributo mogers. B)

[Warrior]

Não temos (nunca usei isto num exercício, acho que este só está lá devido a ser dado numa cadeira e alguém implementou). Isto não me parece assim tão complicado...

Dei uma vista de olhos rápida no google e o algoritmo de Hopcroft é mais complexo do que este em termos teóricos. Não faço ideia se tem uma implementação mais pequena. Eu não o estudei.

*off topic*

Acho que minimização de DFAs saiu num Swerc em Lisboa, mas não tenho a certeza agora..

Pode ser que seja um exercício que dê para resolver de outra maneira também, mas acho que foi por isso que o Hugo colocou lá.

Edit:

Não vejo mais nenhuma solução para este problema além dessa:

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3981

[mogers]

Durante o SWERC 2007 também se pensou isso, depois, em casa, reparei num pormenor muito importante no enunciado:

it is known that, for every possible input, the procedures always terminate

Isto significa que não existem ciclos. Assim, basta uma simples dfs que testa todos os inputs possíveis (bits 0 e 1) e verifica se os automatos retornam sempre o mesmo valor (0 ou 1 para um determinado input).

O código (aceite em 18º na eficiência)

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <map>
using namespace std;

struct instrucao {
int ini , fim;
char label;
bool operator < ( const instrucao & i ) const {
	return ini < i.ini;
}
} v1[10200] , v2[10200];
int n1 , n2 ;

inline void ler( instrucao v[] , int & n ) {
char s[20];
int i ;
n = 0 ;
scanf("%s " , s );
while ( s[0] != 'E' ) {
	v[n].ini = atoi( s );
	scanf("%s" , s );
	if ( s[0] == 'R' ) {
		v[n].label = s[3]-'0';
		v[n].fim = v[n].ini;
	}
	else {
		v[n].label = s[0];
		scanf("%d" , & v[n].fim );
	}		
	n++;
	scanf("%s " , s );
}
sort( v , v+n );
map<int,int> m;
for (i = 0 ; i < n ; i++)
	m[ v[i].ini ] = i;
for (i = 0 ; i < n ; i++)
	v[i].fim = m[ v[i].fim ];
}
int get( instrucao v[] , int a ) {
if (v[a].label == 'J')
	return get( v , v[a].fim );
return a;
}
int next( instrucao v[] , int a , int bit ) {
if ( v[a].label == 'B' )
	return bit == 0 ? a+1 : v[a].fim ;
return a;
}
int dfs( int a , int b ) {
a = get(v1 , a);
b = get(v2 , b);
if ( v1[a].label < 2 && v2[b].label < 2 )
	return v1[a].label == v2[b].label ;
return dfs( next( v1 , a , 0 ) , next( v2 , b , 0 ) ) && dfs( next( v1 , a , 1 ) , next( v2 , b , 1 ) );
}

int main() {
int nc , P , aridade;
scanf("%d" , &nc);
while (nc--) {
	scanf("%d" , &P);
	while (P--) {
		scanf("%d" , & aridade );
		ler( v1 , n1 );
		ler( v2 , n2 );
		printf("%d\n", dfs( 0 , 0 ) );
	}
	if (nc)
		printf("\n");
}
return 0;
}

[Baderous]

Não estou a perceber como posso aplicar essa explicação para resolver o meu problema...

[mogers]

Se te referes ao meu último post, eu estava a responder ao que o Warrior referiu em off-topic. Não tem a ver com o teu problema porque a minimização dos automatos não é necessária. Sorry.