Clasificación topológica en Java

Al vestirse, como se hace uno, lo más probable es que no hayas tenido esta línea de pensamiento: Oh, podría haber sido una buena idea ponerme los calzoncillos antes de ponerme...

Introducción

A la hora de vestirse, como se hace, lo más probable es que no hayas tenido esta línea de pensamiento:

Oh, podría haber sido una buena idea ponerme los calzoncillos antes de ponerme los pantalones.

Eso es porque estamos acostumbrados a ordenar nuestras acciones topológicamente. O en términos más simples, estamos acostumbrados a deducir lógicamente qué acciones tienen que venir antes o después de otras acciones, o más bien qué acciones son requisitos previos para otras acciones.

Por ejemplo, supongamos que desea construir una casa, los pasos se verían así:

  1. Establecer los cimientos
  2. Construye paredes con instalaciones
  3. Poner aislamiento
  4. Poner decoraciones/fachada

En ese orden exacto, es indiscutible. No puedes construir paredes si no tienes una base, y no puedes poner aislamiento si no hay paredes.

En esta guía, cubriremos Clasificación topológica en Java.

Introducción a los gráficos

Dado que la clasificación topológica se aplica a Gráficos acílicos dirigidos (DAG), primero tenemos que hablar un poco sobre Gráficos.

Un gráfico es simplemente una estructura de datos que representa un conjunto de objetos que tienen ciertas relaciones entre sí: los objetos están representados por nodos (círculos) y las relaciones individuales por bordes (las líneas).

Hay muchos tipos diferentes de gráficos, pero para el problema que nos ocupa necesitamos aprender qué es un gráfico acíclico dirigido. Analicemos el gran término matemático malo en segmentos más pequeños y comprensibles.

Dirigido

Un gráfico es dirigido si cada relación entre 2 objetos no tiene que ser bidireccional (tiene que tener una dirección), a diferencia de un gráfico unidireccional donde cada relación tiene que ir en ambos sentidos.

En el siguiente gráfico, la relación ‘C-A’ es unidireccional, lo que significa que ‘C’ tiene una relación con ‘A’ y ‘A’ tiene una relación con ‘C’.

Por otro lado, en el siguiente gráfico, la relación C-A está dirigida, lo que significa que A tiene relación con C, pero C no tiene relación con A.

Debido a esta diferencia, tenemos que definir estrictamente cuáles son los vecinos del nodo:

Gráfico unidireccional:

​Dos nodos (A y B) son nodos vecinos si existe un camino unidireccional entre ellos.

Gráfico dirigido:

A es vecino de B si existe un borde directo, dirigido que lleva de B a A. El primer directo en esta definición se refiere al hecho de que la longitud del camino que conduce de B a A tiene que ser estrictamente 1.

Acíclico

Un gráfico dado es acíclico sólo si no existe un ciclo. Un ciclo es un camino para cualquier nodo ‘X’, que comienza en ‘X’ y conduce de regreso a ‘X’. El siguiente gráfico no es acíclico porque contiene un ciclo (X-B-C-X).

Concepto básico de clasificación topológica

Entonces, ¿cómo se ve la clasificación topológica cuando se usa en un gráfico y por qué el gráfico tiene que ser acíclico para que funcione?

Para responder a estas preguntas, definamos estrictamente lo que significa ordenar topológicamente un gráfico:

Un gráfico se puede clasificar topológicamente si existe una secuencia a1, a2, a3... (ai son nodos de gráfico), donde para cada borde ai->aj, ai viene antes de aj en la secuencia.

Si decimos que las acciones están representadas por nodos. La definición anterior básicamente significaría que debe existir una * orden indiscutible * de ejecución.

Para comprender mejor la lógica detrás de la clasificación topológica y por qué no puede funcionar en un gráfico que contiene un ciclo, supongamos que somos una computadora que intenta clasificar topológicamente el siguiente gráfico:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Let's say that we start our search at node X
# Current node: X
step 1: Ok, i'm starting from node X so it must be at the beginnig of the sequence.
    sequence: [X]

# The only available edge from X is X->B, so we 'travel' to B
# Current node: B
step 2: Right, B comes after X in the sequence for sure.
    sequence: [X,B]

# We travel to C using the edge B->C
# Current node: C
step 3: Same thing as the last step, we add C.
    sequence: [X,B,C]

# Current node: X
step 4: WHAT IN THE TARNATION, X AGAIN?
    sequence: [X,B,C,X]

Esta es la razón por la que no podemos ordenar topológicamente un gráfico que contiene un ciclo, porque las siguientes dos afirmaciones son verdaderas:

  • X viene antes de B
  • B viene antes de X

Y por eso, no podemos determinar un orden absoluto de las acciones dadas.

Ahora que estamos familiarizados con los conceptos del algoritmo, echemos un vistazo a la implementación en Java.

Implementación

En primer lugar, construyamos clases para definir nodos y gráficos, y luego usando dichas clases, definamos el siguiente gráfico:

 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
30
31
32
33
34
35
36
37
38
39
public class Graph {
    private List<Node> nodes;

    public Graph() {
        this.nodes = new ArrayList<>();
    }

    public Graph(List<Node> nodes) {
        this.nodes = nodes;
    }

    public void addNode(Node e) {
        this.nodes.add(e);
    }

    public List<Node> getNodes() {
        return nodes;
    }

    public Node getNode(int searchId) {
        for (Node node:this.getNodes()) {
            if (node.getId() == searchId) {
                return node;
            }
        }
        return null;
    }

    public int getSize() {
        return this.nodes.size();
    }

    @Override
    public String toString() {
        return "Graph{" +
                "nodes=" + nodes +
                "}";
    }
}

El gráfico es bastante simple, podemos instanciarlo vacío o con un conjunto de nodos, agregar nodos, recuperarlos e imprimirlos.

Ahora, pasemos a la clase Nodo:

 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 Node {
    private int id;
    private List<Integer> neighbors;

    public Node(int id) {
        this.id = id;
        this.neighbors = new ArrayList<>();
    }

    public void addNeighbor(int e) {
        this.neighbors.add(e);
    }

    public int getId() {
        return id;
    }

    public List<Integer> getNeighbors() {
        return neighbors;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", neighbors=" + neighbors +
                "}"+ "\n";
    }
}

Esta clase también es bastante simple: solo un constructor y una lista de nodos vecinos.

Con nuestras dos clases, instanciamos un gráfico y llenémoslo con algunos nodos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class GraphInit {
    public static void main(String[] args) {
        Graph g = new Graph();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.addNeighbor(2);
        node2.addNeighbor(3);
        node4.addNeighbor(3);
        g.addNode(node1);
        g.addNode(node2);
        g.addNode(node3);
        g.addNode(node4);
        System.out.println(g);
    }
}

Producción:

1
2
3
4
5
Graph{nodes=[Node{id=1, neighbors=[2]}
, Node{id=2, neighbors=[3]}
, Node{id=3, neighbors=[]}
, Node{id=4, neighbors=[3]}
]}

Ahora implementemos el algoritmo en sí:

 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
30
31
32
33
34
35
36
37
38
39
private static void topoSort(Graph g) {

    // Fetching the number of nodes in the graph
    int V = g.getSize();

    // List where we'll be storing the topological order
    List<Integer> order = new ArrayList<> ();

    // Map which indicates if a node is visited (has been processed by the algorithm)
    Map<Integer, Boolean> visited = new HashMap<>();
    for (Node tmp: g.getNodes())
        visited.put(tmp.getId(), false);

    // We go through the nodes using black magic
    for (Node tmp: g.getNodes()) {
        if (!visited.get(tmp.getId()))
            blackMagic(g, tmp.getId(), visited, order);
    }

    // We reverse the order we constructed to get the
    // proper toposorting
    Collections.reverse(order);
    System.out.println(order);
}

private static void blackMagic(Graph g, int v, Map<Integer, Boolean> visited, List<Integer> order) {
    // Mark the current node as visited
    visited.replace(v, true);
    Integer i;

    // We reuse the algorithm on all adjacent nodes to the current node
    for (Integer neighborId: g.getNode(v).getNeighbors()) {
        if (!visited.get(neighborId))
            blackMagic(g, neighborId, visited, order);
    }

    // Put the current node in the array
    order.add(v);
}

Si llamamos a topoSort(g) para el gráfico inicializado arriba, obtenemos el siguiente resultado:

1
[4, 1, 2, 3]

Lo cual es exactamente correcto.

Modelado de problemas mediante clasificación topológica {#modelado de problemas mediante clasificación topológica}

En un escenario del mundo real, la clasificación topológica se puede utilizar para escribir instrucciones de ensamblaje adecuadas para juguetes, automóviles y edificios de Lego.

En realidad, hay un tipo de clasificación topológica que la mayoría de los desarrolladores utilizan a diario (o cada hora), aunque de forma implícita. Si estás pensando en Makefile o simplemente en Dependencias del programa, estarías absolutamente en lo cierto.

Un Makefile típico se ve así:

1
2
area_51_invasion.out: me.c, the_boys.c, Chads.c, Karen.c, the_manager.c
    #instructions for assembly when one of the files in the dependency list is modified

Con esta línea definimos qué archivos dependen de otros archivos, o mejor dicho, estamos definiendo en qué orden topológico se deben inspeccionar los archivos para ver si se necesita una reconstrucción.

Es decir, si area_51_invasion.out depende de the_boys.c y the_boys.c se modifica por alguna razón, necesitamos reconstruir area_51_invasion.out y todo lo que depende de ese mismo archivo, eso es todo lo que viene antes que él en el orden topológico del Makefile.

Conclusión

Considerar Toposort es básicamente algo que hacemos regularmente. Es posible que incluso lo hayas implementado en tu software y ni siquiera lo sepas. Y si no lo has hecho, ¡te sugiero encarecidamente que le des una vuelta!