Clasificación topológica en Java

C

Introducción

Al vestirse, como lo hace uno, lo más probable es que no haya tenido esta línea de pensamiento:

Oh, podría haber sido una buena idea ponerme la ropa interior 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, digamos que desea construir una casa, los pasos se verían así:

  • Sentar las bases
  • Construye muros con instalaciones
  • Ponga aislamiento
  • Poner decoraciones / fachada

En ese orden exacto, es indiscutible. No puede construir paredes si no tiene una base, y no puede colocar aislamiento si no hay paredes.

En este artículo presentaremos la idea de Clasificación topológica a través de los siguientes temas:

  • Introducción a los gráficos
  • Concepto de clasificación topológica
  • Implementación de la clasificación topológica
  • Modelado de problemas

Introducción a los gráficos

Dado que la clasificación topológica se aplica a los 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 nodes (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, debemos 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 está 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 ser en ambos sentidos.

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

Por otro lado, en el siguiente gráfico, la relación C-A está dirigido, lo que significa A tiene una 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 node:

Gráfico no dirigido:

Dos nodes (A y B) son nodes vecinos si existe una ruta no dirigida entre ellos.

Gráfico dirigido:

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

Acíclico

Un gráfico dado es acíclico solo si no existe un ciclo. Un ciclo es un camino para cualquier node. X, que comienza en X y lleva de vuelta a X. El siguiente gráfico es no 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 ordenar topológicamente si una secuencia a1, a2, a3… existe (ai siendo nodes de gráfico), donde para cada borde ai->aj, ai viene antes aj en la secuencia.

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

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 está tratando de clasificar topológicamente el siguiente gráfico:

# 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 dos siguientes afirmaciones son verdaderas:

  • X viene antes que B
  • B viene antes que X

Y debido a 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

Primero, construyamos clases para definir nodes y gráficos, y luego, usando dichas clases, definamos el siguiente gráfico:

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 nodes, agregar nodes, recuperarlos e imprimirlos.

Ahora, pasemos al Node clase:

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 nodes vecinos.

Con nuestras dos clases, creemos una instancia de un gráfico y lo rellenemos con algunos nodes:

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);
    }
}

Salida:

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í:

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 topoSort(g) para el gráfico inicializado arriba, obtenemos el siguiente resultado:

[4, 1, 2, 3]

Que es exactamente correcto.

Modelado de problemas mediante ordenació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, existe 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á pensando en Makefile o simplemente en dependencias del programa, estará absolutamente en lo cierto.

Un Makefile típico se ve así:

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 más bien, estamos definiendo en qué orden topológico se deben inspeccionar los archivos para ver si es necesaria una reconstrucción.

Es decir, si area_51_invasion.out depende de the_boys.c y the_boys.c está modificado por alguna razón, necesitamos reconstruir area_51_invasion.out y todo lo que depende de ese mismo archivo, es decir, todo lo que le precede en el orden topológico del Makefile.

Conclusión

Teniendo en cuenta que Toposort es básicamente algo que hacemos de forma regular. Es posible que incluso lo haya implementado en su software y ni siquiera lo sabía. Y si no lo ha hecho, ¡le sugiero que lo pruebe!

 

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad