Demo entry 2599646

PruebaGrafos

   

Submitted by Mateo on Sep 01, 2015 at 22:29
Language: C++. Code size: 10.9 kB.

#ifndef PRUEBA_GRAFOS_H
#define PRUEBA_GRAFOS_H

#include "GrafoImp.h"
#include "ColaImp.h"
#include "Tupla.h"
#include "ColaPrioridadImp.h"
#include "ComparadorArista.h"
#include "FuncionHashArista.h"

int FuncionCosto(const int& x){
	return x;
}

template <class V, class A>
Puntero<Lista<V> > OrdenTopologico(Puntero<Grafo<V,A> > g){
	//Lista con el orden (izq a der)
	Puntero<Lista<V> > ret = new ListaImp<V>();

	nat cantV = g -> CantVertices();
	Iterador<V> itv = g -> Vertices();
	Puntero<Grafo<V,A> > gC = g -> Clonar();

	while(itv.HayElemento()){
		//Se agregan los de grado de entrada 0 y se deshabilitan (generando nuevos con grado de entrada 0)
		if(gC -> GradoDeEntrada(itv.ElementoActual()) == 0){
			ret -> AgregarFin(itv.ElementoActual());
			gC -> Deshabilitar(itv.ElementoActual());
			//Reset de los vertices habilitados
			itv = gC -> Vertices();
		} else {
			//Si no tiene grado de entrada 0 se sigue buscando
			itv.Avanzar();
		}
	}

	//No hay un orden topológico (de todos los vértices)
	if(ret -> Largo() < cantV)
		ret -> Vaciar();

	return ret;
}

template <class A>
int BuscarMinimoDijkstra(Array<A>& costo, Array<bool>& conocido){
	int min = infinito;
	int pos = -1;
	for(nat i = 0; i < costo.ObtenerLargo(); i++)
		if(!conocido[i] && costo[i] < min){
			min = costo[i];
			pos = i;
		}
	return pos;
}

template <class V, class A>
void Dijkstra(Puntero<Grafo<V,A> > g, V inicio, Array<V>& vengo, Array<A>& costo, Array<bool>& conocido, int (*valor) (const A&)){
	int pos = g -> NumeroInterno(inicio);
	costo[pos] = 0;
	vengo[pos] = pos;

	while(pos != -1){
		conocido[pos] = true;
		V v = g -> ObtenerVertice(pos);
		Iterador<V> itAdy = g -> Adyacentes(v);
		while(itAdy.HayElemento()){
			if(!conocido[g -> NumeroInterno(itAdy.ElementoActual())]){
				int valorArista = valor(g -> ObtenerArista(v, itAdy.ElementoActual()));
				int valorActual = valor(costo[g -> NumeroInterno(itAdy.ElementoActual())]);
				int valorTentativo = valorArista + valor(costo[pos]);

				if(valorActual > valorTentativo){
					costo[g -> NumeroInterno(itAdy.ElementoActual())] = valorTentativo;
					vengo[g -> NumeroInterno(itAdy.ElementoActual())] = pos;
				}
			}
			itAdy.Avanzar();
		}
		pos = BuscarMinimoDijkstra(costo,conocido);
	}
}

template <class V, class A>
void CaminoMasCortoCola(Puntero<Grafo<V,A> > g, V inicio, Array<V>& vengo, Array<A>& costo, int (*valor) (const A&)){
	Puntero<Cola<V> > cp = new ColaImp<V>();
	cp -> Encolar(inicio);
	int pos = g -> NumeroInterno(inicio);
	costo[pos] = 0;
	vengo[pos] = pos;

	while(!cp -> EsVacia()){
		V v = cp -> Desencolar();
		pos = g -> NumeroInterno(v);
		Iterador<V> itAdy = g -> Adyacentes(v);
		while(itAdy.HayElemento()){	
			int valorArista = valor(g -> ObtenerArista(v, itAdy.ElementoActual()));
			int valorActual = valor(costo[g -> NumeroInterno(itAdy.ElementoActual())]);
			int valorTentativo = valorArista + valor(costo[pos]);

			if(valorActual > valorTentativo){
				costo[g -> NumeroInterno(itAdy.ElementoActual())] = valorTentativo;
				vengo[g -> NumeroInterno(itAdy.ElementoActual())] = pos;
				cp -> Encolar(itAdy.ElementoActual());
			}

			itAdy.Avanzar();
		}
	}
}

template <class V, class A>
void GenerarMatrizDeAdyacencia(Puntero<Grafo<V,A> > g, Matriz<int>& matriz, int (*valor) (const A&)){
	Iterador<V> it1 = g -> Vertices();
	while(it1.HayElemento()){
		V v1 = it1.ElementoActual();
		Iterador<V> it2 = g -> Vertices();
		while(it2.HayElemento()){
			V v2 = it2.ElementoActual();
			if(g -> ExisteArista(v1,v2)){
				A a = g -> ObtenerArista(v1,v2);
				int c = valor(a);
				int o = g -> NumeroInterno(v1);
				int d = g -> NumeroInterno(v2);
				matriz[o][d] = c;
			} else if(v1 == v2){
				int o = g -> NumeroInterno(v1);
				int d = g -> NumeroInterno(v2);
				matriz[o][d] = 0;
			}
			it2.Avanzar();
		}
		it1.Avanzar();
	}
}

void Floyd(Matriz<int>& A, Matriz<int>& B){
	nat dim = A.ObtenerLargo();
	for(nat k = 0; k < dim; k++){
		for(nat i = 0; i < dim; i++){
			for(nat j = 0; j < dim; j++){
				if(A[i][j] > A[i][k] + A[k][j]){
					A[i][j] = A[i][k] + A[k][j];
					B[i][j] = k;
				}
			}
		}
	}
}

template <class V, class A>
void MostrarCaminoAux(Puntero<Grafo<V,A> > g, Matriz<int>& B, int i, int j){
	int k = B[i][j];
	if(k != -1){
		MostrarCaminoAux(g,B,i,k);
		cout << g -> ObtenerVertice(k) << " -> ";
		MostrarCaminoAux(g,B,k,j);
	}
}

template <class V, class A>
void MostrarCaminoFloyd(Puntero<Grafo<V,A> > g, Matriz<int>& A, Matriz<int>& B, V o, V d){
	int i = g -> NumeroInterno(o);
	int j = g -> NumeroInterno(d);
	if(A[i][j] != infinito){
		cout << o << " -> ";
		MostrarCaminoAux(g,B,i,j);
		cout << d << endl;
	} else
		cout << "No hay camino del " << o << " al " << d << endl;
}

template <class V, class A>
Puntero<Grafo<V,A> > Prim(Puntero<Grafo<V,A> > g, int (*valor) (const A&)){
	Puntero<Grafo<V,A> > ret = g -> CrearVacio();

	Array<int> costo(g -> CantVertices(), infinito);
	Array<int> vengo(g -> CantVertices(), -1);

	Iterador<V> it = g -> Vertices();
	V inicio = it.ElementoActual();

	Puntero<Cola<V> > c = new ColaImp<V>();
	c -> Encolar(inicio);
	int pos = g -> NumeroInterno(inicio);
	costo[pos] = 0;
	vengo[pos] = pos;

	while(!c -> EsVacia()){
		V v = c -> Desencolar();
		pos = g -> NumeroInterno(v);
		Iterador<V> itAdy = g -> Adyacentes(v);
		while(itAdy.HayElemento()){	
			//Es igual al CaminoMasCortoCola (Dijkstra con cola) pero sin importar el costo de llegada (valorTentativo)
			int valorArista = valor(g -> ObtenerArista(v, itAdy.ElementoActual()));
			int valorActual = valor(costo[g -> NumeroInterno(itAdy.ElementoActual())]);

			if(valorActual > valorArista){
				costo[g -> NumeroInterno(itAdy.ElementoActual())] = valorArista;
				vengo[g -> NumeroInterno(itAdy.ElementoActual())] = pos;
				c -> Encolar(itAdy.ElementoActual());
			}

			itAdy.Avanzar();
		}
	}

	//Agrega los vertices al grafo de retorno
	while(it.HayElemento()){
		ret -> AgregarVertice(it.ElementoActual());
		it.Avanzar();
	}

	//Agrega las aristas al grafo de retorno
	it.Reiniciar();
	while(it.HayElemento()){
		nat numInt = g -> NumeroInterno(it.ElementoActual());
		if(costo[numInt] != infinito && costo[numInt] != 0){
			A a = g -> ObtenerArista(g -> ObtenerVertice(vengo[numInt]), it.ElementoActual());
			ret -> AgregarArista(g -> ObtenerVertice(vengo[numInt]), it.ElementoActual(), a);
		}
		it.Avanzar();
	}
	
	//Para las aristas en el main.cpp
	Matriz<int> final = Matriz<int>(g -> CantVertices());
	nat dim = g -> CantVertices();
	for(nat i = 0; i < dim; i++){
		for(nat j = 0; j < dim; j++){
			final[i][j] = 0;
		}
	}

	GenerarMatrizDeAdyacencia(ret, final, FuncionCosto);
	cout << "Aristas:" << endl;
	for(nat i = 0; i < dim; i++){
		for(nat j = 0; j < dim; j++){
			if(final[i][j] != 0){
				cout << ret -> ObtenerVertice(i) << " -> " << ret -> ObtenerVertice(j) << endl;
			}
		}
	}

	return ret;
}

int Find(int pos, Array<int>& sets){
	if(sets[pos] == 0)
		return pos;
	else {
		sets[pos] = Find(sets[pos], sets);
		return sets[pos];
	}
}

void Merge(int s1, int s2, Array<int>& sets){
	sets[Find(s1, sets)] = Find(s2, sets);
}

template <class V, class A>
Puntero<Grafo<V,A> > Kruskal(Puntero<Grafo<V,A> > g, Puntero<Comparador<A> > compA){
	Matriz<int> mAdy = Matriz<int>(g -> CantVertices());
	nat dim = mAdy.ObtenerLargo();
	for(nat i = 0; i < dim; i++){
		for(nat j = 0; j < dim; j++){
			mAdy[i][j] = 0;
		}
	}

	Puntero<Grafo<V,A> > ret = g -> CrearVacio();
	Iterador<V> itv = g -> Vertices();

	while(itv.HayElemento()){
		ret -> AgregarVertice(itv.ElementoActual());
		itv.Avanzar();
	}


	GenerarMatrizDeAdyacencia(g, mAdy, FuncionCosto);

	//Creo cola de prioridad
	Puntero<ComparadorArista<A> > c = new ComparadorArista<A>();
	Puntero<FuncionHashArista<A> > f = new FuncionHashArista<A>();
	int largoCP = g -> CantAristas();
	Puntero<ColaPrioridadImp<Tupla<int,int,A>, A> > cp = new ColaPrioridadImp<Tupla<int,int,A>, A>(largoCP, compA, c, f);

	//Agrego las aristas a la cola de prioridad según el costo para ordenarlas de menor a mayor
	for(nat i = 0; i < dim; i++){
		for(nat j = 0; j < dim; j++){
			if(mAdy[i][j] != 0){
				V vo = g -> ObtenerVertice(i);
				V vd = g -> ObtenerVertice(j);
				Tupla<int,int,A> t = Tupla<int,int,A>(i,j,g -> ObtenerArista(vo,vd));
				cp -> encolar(t,t.ObtenerDato3());
			}
		}
	}

	//Array para el MFset
	Array<int> sets = Array<int>(g -> CantVertices(), 0);

	//Kruskal con MFset
	while(!cp -> estaVacia()){
		Tupla<int,int,A> t = cp -> desencolar();
		int co = Find(t.ObtenerDato1(), sets);
		int cd = Find(t.ObtenerDato2(), sets);
		if(co != cd){
			V vo = g -> ObtenerVertice(t.ObtenerDato1());
			V vd = g -> ObtenerVertice(t.ObtenerDato2());
			A a = t.ObtenerDato3();
			ret -> AgregarArista(vo,vd,a);
			Merge(co,cd,sets);
		}
	}

	//Para mostrar en el main.cpp
	Matriz<int> final = Matriz<int>(g -> CantVertices());
	for(nat i = 0; i < dim; i++){
		for(nat j = 0; j < dim; j++){
			final[i][j] = 0;
		}
	}

	GenerarMatrizDeAdyacencia(ret, final, FuncionCosto);
	cout << "Aristas:" << endl;
	for(nat i = 0; i < dim; i++){
		for(nat j = 0; j < dim; j++){
			if(final[i][j] != 0){
				cout << ret -> ObtenerVertice(i) << " -> " << ret -> ObtenerVertice(j) << endl;
			}
		}
	}

	return ret;
}

int BuscoPrimero(Array<int>& pase){
	nat dim = pase.ObtenerLargo();
	for(nat i = 0; i < dim; i++)
		if(pase[i] == 0)
			return i;
	return dim;
}

template <class V, class A>
void RecorroProfundidad(Puntero<Grafo<V,A> > g, V v, Array<int>& pase, int marca){
	int numInt = g -> NumeroInterno(v);
	if(pase[numInt] == 0){
		pase[numInt] = marca;
		Iterador<V> ady = g -> Adyacentes(v);
		while(ady.HayElemento()){
			V w = ady.ElementoActual();
			ady.Avanzar();
			RecorroProfundidad(g, w, pase, marca);
		}
	}
}

/*
En la Teoría de grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v 
existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo 
dirigido son sus subgrafos máximos fuertemente conexos. Estos subgrafos forman una partición del grafo.

Fuente: http://es.wikipedia.org/wiki/Componente_fuertemente_conexo
*/
template <class V, class A>
int ComponentesFuertementeConexas(Puntero<Grafo<V,A> > g){
	int cantVertices = g -> CantVertices();
	Array<int> pase = Array<int>(cantVertices, 0);
	int cont = 0;
	int posPrimero = BuscoPrimero(pase);
	while(posPrimero < cantVertices){
		cont++;
		RecorroProfundidad(g, g -> ObtenerVertice(posPrimero), pase, cont);
		posPrimero = BuscoPrimero(pase);
	}
	return cont;
}

#endif

This snippet took 0.04 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).