Clasificaci贸n topol贸gica en Java

    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!

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *