Рубрики
Без рубрики

Топологическая сортировка в Java

Автор оригинала: Vladimir Batoćanin.

Вступление

Когда вы одеваетесь, как это обычно бывает, у вас, скорее всего, не было такой мысли:

О, возможно, было бы хорошей идеей надеть трусы, прежде чем влезать в брюки.

Это потому, что мы привыкли сортировать наши действия топологически . Или, проще говоря , мы привыкли логически выводить, какие действия должны произойти до или после других действий , или, скорее, какие действия являются предпосылками для других действий.

Например, предположим, что вы хотите построить дом, шаги будут выглядеть так:

  1. Заложите фундамент
  2. Стройте стены с помощью инсталляций
  3. Положить в изоляцию
  4. Нанесите украшения/фасад

В таком точном порядке – это бесспорно. Вы не можете строить стены, если у вас нет фундамента, и вы не можете утеплить, если нет стен.

В этом руководстве мы рассмотрим Топологическую сортировку в Java .

Введение в графики

Поскольку топологическая сортировка применяется к Направленным ациклическим графам (DAG), сначала мы должны немного поговорить о Графах .

Граф – это просто структура данных, представляющая набор объектов, которые имеют определенные отношения друг с другом-объекты представлены узлами (окружностями), а отдельные отношения – ребрами (линиями).

Существует много различных видов графиков, но для рассматриваемой проблемы нам нужно узнать, что такое направленный ациклический граф. Давайте разберем большой плохой математический термин на более мелкие, более понятные сегменты.

Направленный

График направлен , если каждое отношение между 2 объектами не обязательно должно быть двунаправленным (оно должно иметь направление), в отличие от однонаправленного графика , где каждое отношение должно идти в обе стороны.

На графике ниже отношение C-A является однонаправленным, что означает, что C имеет отношение к A и A имеет отношение к C .

С другой стороны, на следующем графике отношение C-A направлено, что означает, что A имеет отношение к C , но C не имеет отношения к A .

Из-за этой разницы мы должны строго определить, каковы соседи узла :

Неориентированный граф:

​Два узла (A и B) являются соседними узлами, если между ними существует однонаправленный путь.

Направленный граф:

​ A является соседом B , если существует прямое, направленное ребро , которое ведет от B к А . Первое прямое в этом определении относится к тому факту, что длина пути, ведущего из B в A должно быть строго 1 .

Ациклический

Данный график является ациклическим только в том случае, если цикл не существует . Цикл-это путь для любого узла X , который начинается с X и ведет обратно к X . Следующий график не ациклический, потому что он содержит цикл ( X-B-C-X ).

Базовая Концепция Топологической Сортировки

Итак, как выглядит топологическая сортировка при использовании на графике и почему график должен быть ациклическим, чтобы он работал?

Чтобы ответить на эти вопросы, давайте строго определим, что означает топологическая сортировка графика:

График топологически сортируется, если последовательность a1 , a2 , a3 … существует ( ai будучи узлами графа), где для каждого ребра ai -> aj , ai предшествует aj в последовательности.

Если мы скажем, что действия представлены узлами . Приведенное выше определение в основном означало бы, что должен существовать бесспорный порядок выполнения.

Чтобы лучше понять логику топологической сортировки и почему она не может работать на графике, содержащем цикл, давайте представим, что мы компьютер, который пытается топологически отсортировать следующий график:

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

# 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]

Это причина, по которой мы не можем топологически отсортировать график, содержащий цикл, потому что оба следующих утверждения верны:

  • X предшествует B
  • B предшествует X

И из-за этого мы не можем определить абсолютный порядок данных действий.

Теперь, поскольку мы знакомы с концепциями алгоритмов, давайте взглянем на реализацию в Java.

Реализация

Во-первых, давайте построим классы для определения узлов и графиков, а затем, используя указанные классы, определим следующий график:

public class Graph {
    private List nodes;

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

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

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

    public List 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{" +
                "}";
    }
}

График довольно прост, мы можем создать его пустым или с набором узлов, добавить узлы, извлечь их и распечатать.

Теперь давайте перейдем к классу Узел :

public class Node {
    private int id;
    private List 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 getNeighbors() {
        return neighbors;
    }

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

Этот класс также довольно прост – просто конструктор и список соседних узлов.

В обоих наших классах давайте создадим экземпляр графика и заполним его несколькими узлами:

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

Выход:

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

Теперь давайте реализуем сам алгоритм:

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 order = new ArrayList<> ();

    // Map which indicates if a node is visited (has been processed by the algorithm)
    Map 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 visited, List 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);
}

Если мы вызовем topoSort(g) для графика, инициализированного выше, мы получим следующий результат:

[4, 1, 2, 3]

Что совершенно верно.

Моделирование Задач С Использованием Топологической Сортировки

В реальном сценарии топологическая сортировка может быть использована для написания надлежащих инструкций по сборке игрушек Lego, автомобилей и зданий.

На самом деле существует тип топологической сортировки, который используется ежедневно (или ежечасно) большинством разработчиков, хотя и неявно. Если вы думаете Makefile или просто Зависимости программ , вы были бы абсолютно правы.

Типичный файл Makefile выглядит следующим образом:

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

С помощью этой строки мы определяем, какие файлы зависят от других файлов, или, скорее, мы определяем, в каком топологическом порядке файлы следует проверять, чтобы определить, требуется ли перестроение.

То есть, если area_51_invasion.out зависит от the_boys.c и the_boys.c по какой-либо причине изменен, нам нужно перестроить area_51_invasion.out и все, что зависит от этого же файла, то есть все, что предшествует ему в топологическом порядке файла Makefile.

Вывод

Рассмотрение топосорта-это в основном то, что мы делаем на регулярной основе. Возможно, вы даже внедрили его в свое программное обеспечение и даже не знали об этом. А если вы этого не сделали, я настоятельно рекомендую вам попробовать!