sep 13, 2010

Enviado por en Kernel Error

Teoría de grafos, boost, c++ y hongos alucinógenos.

Buenas.
Después de un tiempo sin escribir, vamos a empezar hablando un poquito de como manejar grafos en c++ particularmente usando boost, supondré que si leen esta entrada tienen nociones sobre grafos, así que pasare por alto detalles de esta naturaleza.

Resulta que boost tiene una serie de implementaciones de estructuras y algoritmos para manejar grafos, cosa que hace la vida más fácil a los programadores que deban ocupar este tema.

Empezaremos representando una matriz de adyacencia para un grafo G, la podemos definir como:

Ma (G) = [C_{ij}]_{nxn}

donde C_{ij} esta definido como la multiplicidad de los vertices Vi y Vj

Para el siguiente grafo G:

la matriz de adyacencia vendría dada por:

Ma(G)=\begin{bmatrix}0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0\end{bmatrix}

ahora pasaremos a representarla, ya boost nos da una estructura de matriz de adyacencia, la cual procederemos a cargar con los vértices.

#include "stdafx.h"
#include <iostream>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_matrix.hpp>

using namespace std;
using namespace boost;

static const int n = 6;

int main (void) {

	// Definimos el nombre de los vertices y creamos el grafo
	// diciendole cuantos vertices tiene el mismo
	// crearemo un arreglo para ayudarnos a cargar la matriz

	const char* name = "123456";
	bool matrix[n][n] = { {0, 1, 0, 0, 1, 0},
					   {1, 0, 1, 0, 1, 0},
					   {0, 1, 0, 1, 0, 0},
					   {0, 0, 1, 0, 1, 1},
					   {1, 1, 0, 1, 0, 0},
					   {0, 0, 0, 1, 0, 0} } ;

	boost::adjacency_matrix<boost::directedS> G(n);

	// Agregamos los vertices

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (matrix[i][j])
				add_edge (i, j, G);
		}
	}
}

ahora bien podemos imprimir las aristas haciendo

boost::print_edges(G, name);

y tendremos algo como esto:

(1,2) (1,5) (2,1) (2,3) (2,5) (3,2) (3,4) (4,3) (4,5) (4,6) (5,1) (5,2) (5,4) (6, 4)

y si verificamos en la figura de la matriz puesta arriba podemos chequear que son las aristas cargadas, ahora bién podemos ver una relación mejor si imprimos el grafo como tal

boost::print_graph (G, name);

y de salida obtenemos:

1 –> 2 5
2 –> 1 3 5
3 –> 2 4
4 –> 3 5 6
5 –> 1 2 4
6 –> 4

Hecho esto tocaremos ahora el tema de la lista de adyacencia que nos da boost, la forma de definirla no tiene mayor complicación.

boost::adjacency_list <>

donde si nos vamos a la definición de la estructura como tal encontramos

adjacency_list<OutEdgeList, VertexList, Directed, VertexProperties, EdgeProperties, GraphProperties, EdgeList>

aplicaremos esto con un ejemplo de árboles directamente, si tenemos un árbol como este:

podremos saber quien es padre de quien y quien es hijo de quien representando un árbol como un grafo

#include "stdafx.h"
#include <iostream>
#include <boost/config.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace std;
using namespace boost;

enum { A, B, C, D, E, F, G, H, I, J, K, N };

int main (void) {

	const char* name = "ABCDEFGHIJK";

	boost::adjacency_list <> g(N);

	// cargamos el arbol

	add_edge (A, B, g);
	add_edge (A, C, g);
	add_edge (B, D, g);
	add_edge (B, E, g);
	add_edge (D, G, g);
	add_edge (E, H, g);
	add_edge (E, I, g);
	add_edge (C, F, g);
	add_edge (F, J, g);
	add_edge (J, K, g);

	graph_traits < adjacency_list <> >::vertex_iterator i, end;
	graph_traits < adjacency_list <> >::adjacency_iterator ai, a_end;
	property_map < adjacency_list <>, vertex_index_t >::type index_map = get(vertex_index, g);

	for (boost::tie(i, end) = vertices(g); i != end; ++i) {
		cout << name[get(index_map, *i)];
		boost::tie(ai, a_end) = adjacent_vertices(*i, g);

		if (ai == a_end)
			cout << " no tiene hijos";
		else
			cout << " es el padre de ";

		for (; ai != a_end; ++ai) {
			cout << name[get(index_map, *ai)];

			if (boost::next(ai) != a_end)
				cout << ", ";
		}

		cout << std::endl;
	}
}

y tenemos de salida

A es el padre de B, C
B es el padre de D, E
C es el padre de F
D es el padre de G
E es el padre de H, I
F es el padre de J
G no tiene hijos
H no tiene hijos
I no tiene hijos
J es el padre de K
K no tiene hijos

Por ahora esto es todo en una próxima entrega hablaremos de algunos de los algoritmos de grafos que nos ofrece boost.

    Posts Relacionados

    Dejar una respuesta

    Debes ser Alojarse para enviar un comentario.