C++ / graphs

Bienvenidos sean a este post, hoy veremos una variante de los contenedores.

En este post hemos visto como es una busqueda binaria y en este post hablamos sobre tree y su forma para una busqueda binaria, y hemos visto que esta basado en muchas implementaciones de busqueda de indices. Tomemos como ejemplo a los sistemas de bases de datos, estas usan a un tree balanceado llamado b-tree para la indexacion de la tabla. Este no es un tree binario pero tiene una la misma logica de balanceo. En cambio, graphs representan conexiones de nodos sin un orden apropiado.

Vamos a suponer que estamos creando una red social, y como cualquier otra vamos a permitir que los usuarios se sigan entre ellos. Esto puede ser representado por un graph, vamos a suponer que el usuarrio A sigue al usuario B, B sigue al C y C sigue tanto al usuario A como el B. Un nodo en graph es llamado vertex, y el link entre los nodos es llamado edge. Actualmente no tenemos una representacion fija de graph, lo cual desencadena que tenemos varias posibilidades a la hora de elegir. Para entender el concepto, vamos a analizar el siguiente ejemplo:

#include <iostream>
#include <vector>

using namespace std;

class Graph 
{
vector<vector<int> > matrix;

public:
    Graph(int n)
    {
        matrix = vector<vector<int> >(n, vector<int>(n, 0));
    }

    void agregarEdge(int u, int v)
    {
        matrix[u][v] = 1;
        matrix[v][u] = 1;
    }

    void mostrar()
    {
        cout << "Matriz de adyacencia para el gráfico: " << endl;
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << matrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main()
{
    int n = 4;
    Graph g(n);

    g.agregarEdge(0, 1);
    g.agregarEdge(0, 2);
    g.agregarEdge(1, 3);
    g.agregarEdge(2, 3);
    g.mostrar();

    return 0;
}

Lo primero que definimos es una clase para manejar los graph. En este definimos un vector llamado matrix y en este almacenaremos todos los edge que iremos generando. En la parte publica, primero definimos al constructor donde definimos dos dimensiones para el vector y una n cantidad para almacenar los vertices. El siguiente metodo es el encargado de crear los edge entre las dos coordenadas que recibimos, la primer linea establece el edge entre u y v. La siguiente establece el edge en el sentido contrario para los graph no dirigidos. El siguiente metodo es para mostrar el vector que definimos anteriormente, como posee dos dimensiones debemos usar dos bucles para pasar en cada una. En el main, creamos un graph y agregamos una serie de edge para unir los distintos vertices. Y finalmente, mostraremos la matrix generada anteriormente. Compilemos y veamos como es la salida:

$ ./graph
Matriz de adyacencia para el gráfico:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
$

Observen como los parametros que pasamos para crear los edge tienen el valor de uno y los que no de cero. Pero como comentamos al agregar los edge, tambien agregamos el orden inverso de los que pasamos y los mostramos en la salida.

En resumen, hoy hemos visto a graph, que es, para que sirve, como se utiliza, como es la estructura de estos, asi como un ejemplo para verlo en accion. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.