Jump to content
Sign in to follow this  
Baderous

Simplificação de Grafos

Recommended Posts

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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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;
}


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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;
}


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Baderous

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

Share this post


Link to post
Share on other sites
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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.