Gráficos en Java: representación de gráficos en código

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática. Debido a...

Introducción

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática.

Debido al hecho de que muchas cosas se pueden representar como gráficos, el recorrido de gráficos se ha convertido en una tarea común, especialmente utilizada en ciencia de datos y aprendizaje automático. El recorrido de gráficos se refiere al proceso de visitar nodos (también conocidos como vértices) en un gráfico a través de los bordes de conexión. Esto se usa comúnmente para encontrar un nodo particular en el gráfico o para trazar un gráfico.

En esta serie, veremos cómo se usan y representan los gráficos en informática, así como algunos algoritmos transversales populares:

Representación de gráficos en código

Ahora que nos hemos familiarizado con lo que son los gráficos y cuándo son útiles, debemos saber cómo implementarlos en el código.

Los dos enfoques principales para este problema son matrices de adyacencia y listas de adyacencia.

Matriz de adyacencia

Comencemos con la suposición de que tenemos n nodos y están convenientemente llamados 0,1,...n-1 y que contienen el mismo valor cuyo nombre tienen. Por supuesto, esto rara vez sucede, pero facilita la explicación de la matriz de adyacencia.

La situación en la que nuestros nodos/vértices son objetos (como probablemente lo serían) es muy complicada y requiere muchos métodos de mantenimiento que hacen que las matrices de adyacencia sean más problemáticas de lo que valen la mayor parte del tiempo, por lo que solo proporcionar la implementación del caso "simple".

Digamos que tenemos el siguiente gráfico:

En este gráfico, hay 5 nodos - (0,1,2,3,4) con los bordes {1,2}, {1,3}, {2,4}, {3,0}. Por definición, cuando observamos un gráfico no dirigido no ponderado, la posición (i,j) en nuestra matriz de adyacencia es 1 si existe un borde entre los nodos i y j; de lo contrario, es 0. En el En el caso de un grafo no dirigido, la matriz de adyacencia es simétrica.

La matriz de adyacencia del ejemplo anterior se vería así:

También podríamos invertir el proceso, dibujar un gráfico a partir de una matriz de adyacencia dada.

Daremos un ejemplo del proceso inverso pero con una matriz de adyacencia de un gráfico ponderado. En este caso, la posición (i,j) en nuestra matriz es igual al peso de la arista entre los nodos i y j si existe, de lo contrario es igual a infinito.

Nota: Usar el infinito como peso se considera una forma "segura" de mostrar que no existe un borde. Pero, por ejemplo, si supiéramos que solo tendríamos pesos positivos, podríamos usar -1 en su lugar, o cualquier valor adecuado que decidiéramos.

Construyamos un gráfico ponderado a partir de la siguiente matriz de adyacencia:

Como último ejemplo, mostraremos cómo se representa un gráfico ponderado dirigido con una matriz de adyacencia:

Observe cómo con los gráficos dirigidos, la matriz de adyacencia no es simétrica, p. tenemos un valor en (0,3) pero no en (3,0). Además, no hay ninguna razón por la que un nodo no pueda ser el nodo inicial y final de un borde, y podemos tener nodos completamente desconectados.

Implementación de matrices de adyacencia

Ahora que hemos visto cómo funcionan las matrices de adyacencia en papel, debemos considerar su implementación. Si nuestros "nodos" fueran simplemente valores enteros 0,1,...n-1, la implementación sería bastante sencilla.

Sin embargo, dado que este no suele ser el caso, debemos descubrir cómo podemos usar la conveniencia de usar índices de matriz como nodos cuando nuestros nodos son objetos.

En nuestra implementación, haremos que nuestra clase sea lo más versátil posible. Esto se refleja en algunos métodos más y en algunos casos extremos que se toman en consideración.

También proporcionaremos la opción entre un gráfico dirigido y no dirigido, así como uno ponderado/no ponderado.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Graph {

    private int numOfNodes;
    private boolean directed;
    private boolean weighted;
    private float[][] matrix;

    /*
     This will allow us to safely add weighted graphs in our class since
     we will be able to check whether an edge exists without relying
     on specific special values (like 0)
    */
    private boolean[][] isSetMatrix;

    // ...
}

Entonces, tendremos un constructor simple:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public Graph(int numOfNodes, boolean directed, boolean weighted) {

    this.directed = directed;
    this.weighted = weighted;
    this.numOfNodes = numOfNodes;

    // Simply initializes our adjacency matrix to the appropriate size
    matrix = new float[numOfNodes][numOfNodes];
    isSetMatrix = new boolean[numOfNodes][numOfNodes];
}

Ahora, escribamos un método que nos permita agregar bordes. Queremos asegurarnos de que en caso de que el gráfico esté ponderado y no se proporcione un peso, establezcamos el valor del borde en 0, y si no está ponderado, simplemente agregue 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/*
 Since matrices for directed graphs are symmetrical, we have to add
 [destination][source] at the same time as [source][destination]
*/
public void addEdge(int source, int destination) {

    int valueToAdd = 1;

    if (weighted) {
        valueToAdd = 0;
    }

    matrix[source][destination] = valueToAdd;
    isSetMatrix[source][destination] = true;

    if (!directed) {
        matrix[destination][source] = valueToAdd;
        isSetMatrix[destination][source] = true;
    }
}

En caso de que el gráfico no esté ponderado y se proporcione un peso, simplemente lo ignoramos y establecemos el valor [origen, destino] en 1, lo que indica que existe un borde:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public void addEdge(int source, int destination, float weight) {

    float valueToAdd = weight;

    if (!weighted) {
        valueToAdd = 1;
    }

    matrix[source][destination] = valueToAdd;
    isSetMatrix[source][destination] = true;

    if (!directed) {
        matrix[destination][source] = valueToAdd;
        isSetMatrix[destination][source] = true;
    }
}

En este punto, agreguemos un método que nos permita imprimir fácilmente la matriz de adyacencia:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public void printMatrix() {
    for (int i = 0; i < numOfNodes; i++) {
        for (int j = 0; j < numOfNodes; j++) {
            // We only want to print the values of those positions that have been marked as set
            if (isSetMatrix[i][j])
                System.out.format("%8s", String.valueOf(matrix[i][j]));
            else System.out.format("%8s", "/  ");
        }
        System.out.println();
    }
}

Y después de eso, un método de conveniencia que imprime los bordes de una manera más comprensible:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/*
 We look at each row, one by one.
 When we're at row i, every column j that has a set value represents that an edge exists from
 i to j, so we print it
*/
public void printEdges() {
    for (int i = 0; i < numOfNodes; i++) {
        System.out.print("Node " + i + " is connected to: ");
        for (int j = 0; j < numOfNodes; j++) {
            if (isSetMatrix[i][j]) {
                System.out.print(j + " ");
            }
        }
        System.out.println();
    }
}

Finalmente, escribamos dos métodos auxiliares que se utilizarán más adelante:

1
2
3
4
5
6
7
8
9
public boolean hasEdge(int source, int destination) {
    return isSetMatrix[source][destination];
}

public Float getEdgeValue(int source, int destination) {
    if (!weighted || !isSetMatrix[source][destination])
        return null;
    return matrix[source][destination];
}

Para mostrar cómo funciona una matriz de adyacencia, usemos nuestra clase para hacer un gráfico, llenarlo con relaciones e imprimirlas:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class GraphShow {
    public static void main(String[] args) {

        // Graph(numOfNodes, directed, weighted)
        Graph graph = new Graph(5, false, true);

        graph.addEdge(0, 2, 19);
        graph.addEdge(0, 3, -2);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3); // The default weight is 0 if weighted == true
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printMatrix();

        System.out.println();
        System.out.println();

        graph.printEdges();

        System.out.println();
        System.out.println("Does an edge from 1 to 0 exist?");
        if (graph.hasEdge(0,1)) {
            System.out.println("Yes");
        }
        else System.out.println("No");
    }
}

Lo que nos da la salida:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
     /       /      19.0    -2.0     /
     /       /       3.0     0.0     0.0
    19.0     3.0     /       0.0     /
    -2.0     0.0     0.0     /       0.0
     /       0.0     /       0.0     /


Node 0 is connected to: 2 3
Node 1 is connected to: 2 3 4
Node 2 is connected to: 0 1 3
Node 3 is connected to: 0 1 2 4
Node 4 is connected to: 1 3

Does an edge from 1 to 0 exist?
No
null

Si construyéramos un gráfico basado en esta matriz, se vería así:

Listas de adyacencia

Las listas de adyacencia son mucho más intuitivas de implementar y se usan con mucha más frecuencia que las matrices de adyacencia.

Como su nombre lo indica, usamos listas para representar todos los nodos a los que nuestro nodo tiene un borde. La mayoría de las veces esto se implementa con HashMaps y LinkedLists.

Las listas de adyacencia favorecen los gráficos dirigidos, ya que ahí es donde son más sencillos, mientras que los gráficos no dirigidos requieren solo un poco más de mantenimiento.

En este ejemplo podemos ver que:

1
2
3
4
5
Node 0 is connected with node 3
Node 1 is connected with nodes 3, 2
Node 2 is connected with nodes 1, 4
Node 3 is connected with nodes 1, 0
Node 4 is connected with node 2

Es obvio que para el nodo 0 crearíamos una LinkedList que contenga el nodo 3. Para el nodo 1 crearíamos una LinkedList que contenga los nodos 3 y 2, y así sucesivamente.

Para gráficos ponderados, como el que se muestra a continuación, necesitaríamos listas de matrices en lugar de listas de nodos. Las matrices contendrían el nodo en el otro extremo del borde como el primer parámetro y el peso asociado como el segundo.

1
2
3
4
5
0: [1,-50] -> [3,3]
1: [0,-50]
2: [3, 10]
3: [0,3] -> [2,10] -> 4,7
4: [3,7]

1
2
3
4
5
0: [2,10]
1: null
2: [2,5] -> [3,5] -> [4,3]
3: [0,-2]
4: [3,5]

Una gran ventaja de las listas de adyacencia es que trabajar con objetos es mucho más fácil que con una matriz de adyacencia.

Implementaremos listas de adyacencia con objetos como nodos, en lugar de índices. Esto se favorece cuando se explican las listas de adyacencia y es más útil saberlo, ya que probablemente trabajará con objetos en un proyecto.

Implementación de listas de adyacencia

El código puede parecer complejo a primera vista, pero es bastante sencillo cuando lo miras de cerca. Primero, comencemos con una clase Nodo simple:

1
2
3
4
5
6
7
8
9
public class Node {
    int n;
    String name;

    Node(int n, String name){
        this.n = n;
        this.name = name;
    }
}

Ahora, definamos un Gráfico:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class Graph {

// Each node maps to a list of all his neighbors
private HashMap<Node, LinkedList<Node>> adjacencyMap;
private boolean directed;

public Graph(boolean directed) {
    this.directed = directed;
    adjacencyMap = new HashMap<>();
}

Ahora, agreguemos el método addEdge(). Aunque esta vez usaremos dos métodos, un método auxiliar y el método real.

En el método auxiliar, también haremos una verificación de posibles bordes duplicados. Antes de agregar un borde entre A y B, primero lo eliminaremos y solo luego lo agregaremos. Si existía (estamos agregando un borde duplicado), se eliminó y después de agregarlo nuevamente, solo hay uno.

Sin embargo, si no existiera, eliminar un borde inexistente resultará en una NullPointerException, por lo que estamos introduciendo una copia temporal de la lista:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void addEdgeHelper(Node a, Node b) {
    LinkedList<Node> tmp = adjacencyMap.get(a);

    if (tmp != null) {
        tmp.remove(b);
    }
    else tmp = new LinkedList<>();
    tmp.add(b);
    adjacencyMap.put(a,tmp);
}

public void addEdge(Node source, Node destination) {

    // We make sure that every used node shows up in our .keySet()
    if (!adjacencyMap.keySet().contains(source))
        adjacencyMap.put(source, null);

    if (!adjacencyMap.keySet().contains(destination))
        adjacencyMap.put(destination, null);

    addEdgeHelper(source, destination);

    // If a graph is undirected, we want to add an edge from destination to source as well
    if (!directed) {
        addEdgeHelper(destination, source);
    }
}

Finalmente, tendremos los métodos auxiliares printEdges() y hasEdge(), que son bastante sencillos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public void printEdges() {
        for (Node node : adjacencyMap.keySet()) {
            System.out.print("The " + node.name + " has an edge towards: ");
            if (adjacencyMap.get(node) != null) {
                for (Node neighbor : adjacencyMap.get(node)) {
                    System.out.print(neighbor.name + " ");
                }
                System.out.println();
            }
            else {
                System.out.println("none");
            }
        }
    }

    public boolean hasEdge(Node source, Node destination) {
        return adjacencyMap.containsKey(source) && adjacencyMap.get(source) != null && adjacencyMap.get(source).contains(destination);
    }

Para mostrar cómo funcionan las listas de adyacencia, instanciamos varios nodos y completamos un gráfico con ellos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(true);
        Node a = new Node(0, "A");
        Node b = new Node(1, "B");
        Node c = new Node(2, "C");
        Node d = new Node(3, "D");
        Node e = new Node(4, "E");

        graph.addEdge(a,b);
        graph.addEdge(b,c);
        graph.addEdge(b,d);
        graph.addEdge(c,e);
        graph.addEdge(b,a);

        graph.printEdges();

        System.out.println(graph.hasEdge(a,b));
        System.out.println(graph.hasEdge(d,a));
    }
}

Obtenemos la salida:

1
2
3
4
5
The A has an edge towards: B
The B has an edge towards: C D A
The C has an edge towards: E
true
false

Nota: Esto, por supuesto, depende en gran medida de cómo Java trata los objetos en la memoria. ¡Tenemos que asegurarnos de que los cambios adicionales en nuestro nodo a en main, después de haberlo agregado a nuestro gráfico, se reflejarán en nuestro gráfico! A veces esto es lo que buscamos, pero a veces no lo es. De cualquier manera, debemos tener en cuenta que, en este caso, el nodo a en nuestro gráfico es el mismo que el nodo a en main.

Podríamos haber implementado esto de manera diferente, por supuesto. Otro enfoque popular es agregar la lista de bordes salientes al propio objeto Node y cambiar la clase Graph apropiadamente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Node {
    int n;
    String name;
    LinkedList<Node> adjacentNodes;

    Node(int n, String name) {
        this.n = n;
        this.name = name;
        adjacentNodes = new LinkedList<>();
    }

    public void addEdge(Node node) {
        if (!adjacentNodes.contains(node))
            adjacentNodes.add(node);
    }
}

Ambos enfoques están en el espíritu del concepto de encapsulación orientada a objetos a su manera, por lo que cualquiera está bien.

Matrices de adyacencia frente a listas de adyacencia

Las matrices de adyacencia tienen un tiempo de búsqueda mucho más rápido que las listas de adyacencia. Por ejemplo, si quisiéramos verificar si el nodo ‘0’ tiene un borde que conduce al nodo ‘4’, podríamos simplemente verificar la matriz en los índices ‘[0,4]’, lo que nos brinda un tiempo de ejecución constante.

Por otro lado, potencialmente necesitaríamos verificar la lista completa de vecinos 0 en su lista de adyacencia para encontrar si hay un borde que conduzca al nodo 4, lo que nos da lineal (O (n)) tiempo de búsqueda.

Agregar bordes también es mucho más rápido en matrices de adyacencia: simplemente cambie el valor en la posición [i,j] para agregar un borde del nodo i al nodo j, mientras que con listas (si no tenemos acceso al puntero al último elemento) también puede tomar O(n) tiempo, especialmente si necesitamos verificar si ese borde ya existe en la lista o no.

En lo que respecta al espacio, las listas de adyacencia son mucho más eficientes, por una razón muy simple. La mayoría de los gráficos de la vida real son lo que llamamos escasos, lo que significa que hay muchos menos bordes que el número máximo de bordes posible.

¿Porque es esto importante? Bien, en una matriz de adyacencia siempre tenemos una matriz de tamaño n x n (donde n es el número de nodos), sin importar si tenemos solo unas pocas aristas o casi el número máximo (donde cada nodo es conectados entre sí).

En realidad, esto ocupa mucho espacio que no es necesario, ya que, como dijimos, la mayoría de los gráficos de la vida real son escasos y la mayoría de esos bordes a los que les hemos asignado espacio no existen. Las listas de adyacencia, por otro lado, solo realizan un seguimiento de los bordes existentes.

En términos más concretos, si tuviéramos un grafo con N nodos y E aristas, la complejidad espacial de estos dos enfoques sería:

¿Cuál debo elegir implementar?

Respuesta corta: listas de adyacencia. Son más sencillos cuando se trabaja con objetos, y la mayoría de las veces no nos importa el tiempo de búsqueda ligeramente mejor que proporcionan las matrices de adyacencia en comparación con el mantenimiento y la legibilidad del código.

Sin embargo, si estamos tratando con un gráfico altamente denso (opuesto a escaso), podría valer la pena invertir la memoria necesaria para implementar nuestro gráfico a través de una matriz de adyacencia.

Entonces, por ejemplo, si la operación que probablemente usará es:

  • Comprobar si una arista forma parte de un gráfico: matriz de adyacencia, ya que comprobar si una arista forma parte de un gráfico lleva O(1) tiempo, mientras que en las listas de adyacencia se tarda O(longitudDeLista ) tiempo
  • Añadir o quitar aristas del gráfico: matriz de adyacencia, misma diferencia que en el caso anterior
  • Recorriendo el gráfico: lista de adyacencia, toma tiempo O(N + E) en lugar de O(N^2)

Conclusión

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática.

Debido al hecho de que muchas cosas se pueden representar como gráficos, el recorrido de gráficos se ha convertido en una tarea común, especialmente utilizada en ciencia de datos y aprendizaje automático.

Los dos enfoques principales para representar gráficos en código son matrices de adyacencia y listas de adyacencia.