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

Графики в Java: Представление графиков в коде

Автор оригинала: Olivera Popović.

Вступление

Графики-это удобный способ хранения определенных типов данных. Концепция была перенесена из математики и приспособлена для нужд информатики.

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

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

  • Графики на Java
    • Представление графиков в коде
    • Поиск по глубине (DFS)
    • Поиск по ширине (BFS)
    • Алгоритм Дейкстры

Представление графиков в коде

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

Основными двумя подходами к этой проблеме являются матрицы смежности и списки смежности .

Матрица смежности

Давайте начнем с предположения, что у нас есть n узлов, и они удобно называются 0,1,...n-1 и что они содержат одно и то же значение, чье имя они имеют. Конечно, это случается редко, но это облегчает объяснение матрицы смежности.

Ситуация, когда наши узлы/вершины являются объектами (как, скорее всего, и было бы), очень сложна и требует большого количества методов обслуживания, которые создают больше проблем с матрицами смежности, чем они того стоят большую часть времени, поэтому мы обеспечим реализацию только “простого” случая.

Предположим, что у нас есть следующий график:

В этом графике есть 5 узлов – (0,1,2,3,4) с ребрами {1,2}, {1,3}, {2,4}, {3,0}. По определению, когда мы смотрим на невзвешенный неориентированный граф – позиция (i,j) в нашей матрице смежности равна 1 , если существует ребро между узлами i и j , в противном случае оно равно 0. В случае неориентированного графа матрица смежности симметрична.

Матрица смежности в предыдущем примере будет выглядеть следующим образом:

Мы также могли бы обратить процесс вспять, нарисовать график из заданной матрицы смежности.

Мы приведем пример обратного процесса, но с матрицей смежности взвешенного графика. В этом случае позиция (i,j) в нашей матрице равна весу ребра между узлами i и j , если оно существует, в противном случае оно равно бесконечности.

Примечание : Использование бесконечности в качестве веса считается “безопасным” способом показать, что ребра не существует. Но, например, если бы мы знали, что у нас будут только положительные веса, мы могли бы вместо этого использовать -1 или любое другое подходящее значение, которое мы выбрали.

Давайте построим взвешенный график из следующей матрицы смежности:

В качестве последнего примера мы покажем, как ориентированный взвешенный граф представлен матрицей смежности:

Обратите внимание, как с направленными графами матрица смежности не симметрична, например, у нас есть значение (0,3), но не (3,0). Также нет причин, по которым узел не может быть начальным и конечным узлом ребра, и у нас могут быть совершенно несвязанные узлы.

Реализация Матриц Смежности

Теперь, когда мы увидели, как матрицы смежности работают на бумаге, нам нужно рассмотреть их реализацию. Если бы наши “узлы” действительно были просто целочисленными значениями 0,1,...n-1 , реализация была бы довольно простой.

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

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

Мы также предоставим выбор между направленным и неориентированным графом, а также взвешенным/невзвешенным.

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;

    // ...
}

Тогда у нас будет простой конструктор:

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

Теперь давайте напишем метод, который позволяет нам добавлять ребра. Мы хотим убедиться, что в случае, если график взвешен и вес не указан, мы устанавливаем значение ребра равным 0, а если не взвешен, просто добавляем 1:

/*
 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;
    }
}

В случае, если график не взвешен и указан вес,мы просто игнорируем это и устанавливаем значение [источник, назначение] равным 1, указывая, что ребро действительно существует:

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

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

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

И после этого удобный метод, который выводит края более понятным способом:

/*
 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();
    }
}

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

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

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

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

Что дает нам результат:

     /       /      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

Если бы мы построили график на основе этой матрицы, он выглядел бы следующим образом:

Git Essentials

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

Списки смежности

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

Как следует из названия, мы используем списки для представления всех узлов, к которым наш узел имеет ребро. Чаще всего это реализуется с помощью HashMap и LinkedList s.

Списки смежности благоприятствуют ориентированным графам, так как именно там они наиболее прямолинейны, а неориентированные графики требуют лишь немного большего обслуживания.

В этом примере мы видим, что:

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

Очевидно, что для узла 0 мы создадим Список ссылок , содержащий узел 3. Для узла 1 мы создадим Связанный список , содержащий узлы 3 и 2, и так далее.

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

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

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

Мы будем реализовывать списки смежности с объектами в качестве узлов, а не индексов. Это рекомендуется при объяснении списков смежности и более полезно знать, так как вы, скорее всего, будете работать с объектами в проекте.

Реализация Списков Смежности

Код может показаться сложным на первый взгляд, но при ближайшем рассмотрении он довольно прост. Во-первых, давайте начнем с простого Узла класса:

public class Node {
    int n;
    String name;

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

Теперь давайте определим График :

public class Graph {

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

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

Теперь давайте добавим метод added() . Хотя на этот раз мы будем использовать два метода: вспомогательный метод и фактический метод.

В вспомогательном методе мы также проверим наличие возможных повторяющихся ребер. Прежде чем добавлять границу между A и B , мы сначала удалим ее и только затем добавим. Если он существовал (мы добавляем дубликат ребра), он был удален, и после его повторного добавления остался только один.

Хотя, если бы он не существовал, удаление несуществующего ребра приведет к исключению NullPointerException поэтому мы вводим временную копию списка:

public void addEdgeHelper(Node a, Node b) {
    LinkedList 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);
    }
}

Наконец, у нас будут вспомогательные методы print Edge() и has Edge () , которые довольно просты:

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

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

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

Мы получаем результат:

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

Примечание: Это, конечно, сильно зависит от того, как Java обрабатывает объекты в памяти. Мы должны убедиться , что дальнейшие изменения нашего a узла в main , после того как мы добавим его в наш график, отразятся на нашем графике! Иногда это то, к чему мы стремимся, но иногда это не так. В любом случае, мы должны знать, что в этом случае узел a в нашем графике совпадает с узлом a в main .

Конечно, мы могли бы реализовать это по-другому. Другим популярным подходом является добавление списка исходящих ребер к самому объекту Node и соответствующее изменение класса Graph :

public class Node {
    int n;
    String name;
    LinkedList 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);
    }
}

Оба подхода по-своему соответствуют концепции объектно-ориентированной инкапсуляции, поэтому подойдет любой из них.

Матрицы смежности против Списки смежности

Матрицы смежности имеют гораздо более быстрое время поиска, чем списки смежности. Например, если бы мы хотели проверить, является ли узел 0 имеет ребро, ведущее к узлу 4 мы могли бы просто проверить матрицу по индексам [0,4] , что дает нам постоянное время выполнения.

С другой стороны, нам потенциально потребуется проверить весь список 0 соседей в списке смежности, чтобы определить, есть ли ребро, ведущее к узлу 4 , что дает нам линейное (O(n)) время поиска.

Добавление ребер также намного быстрее в матрицах смежности – просто измените значение в позиции [i,j] , чтобы добавить ребро из узла i в узел j , в то время как со списками (если у нас нет доступа к указателю на последний элемент) также может потребоваться O(n) время, особенно если нам нужно проверить, существует ли это ребро уже в списке или нет.

Что касается пространства – списки смежности намного эффективнее по очень простой причине. Большинство реальных графиков-это то , что мы называем разреженными , что означает, что ребер намного меньше, чем максимально возможное количество ребер.

Почему это так важно? Ну, в матрице смежности у нас всегда есть матрица размера n x n (где n – количество узлов), независимо от того, есть ли у нас всего несколько ребер или почти максимальное число (где каждый узел соединен друг с другом).

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

В более конкретных терминах, если бы у нас был граф с N узлами и E ребрами, пространственная сложность этих двух подходов была бы:

Что я должен выбрать для реализации?

Короткий ответ – списки смежности. Они более просты при работе с объектами, и большую часть времени нас не волнует немного лучшее время поиска, которое обеспечивают матрицы смежности, по сравнению с обслуживанием кода и удобочитаемостью.

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

Так, например, если операция, которую вы, скорее всего, собираетесь использовать, является:

  • Проверка того , является ли ребро частью графика: матрица смежности , поскольку проверка того, является ли ребро частью графика, занимает O(1) время, в то время как в списках смежности требуется O(список длины) время
  • Добавление или удаление ребер из графика: матрица смежности , та же разница, что и в предыдущем случае
  • Обход графика: список смежности , занимает O(N + E) время вместо O(N^2)

Вывод

Графики-это удобный способ хранения определенных типов данных. Концепция была перенесена из математики и приспособлена для нужд информатики.

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

Основными двумя подходами к представлению графиков в коде являются матрицы смежности и списки смежности .