Java: как отображать графики?

Я реализую некоторые алгоритмы, чтобы научить себя графам и как работать с ними. Что вы порекомендуете, это лучший способ сделать это на Java? Я думал примерно так:

public class Vertex {

    private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map.

    //methods to manipulate outnodes
}

public class Graph {
    private ArrayList<Vertex> nodes;
    //algorithms on graphs
}

Но я в основном только что сделал это. Есть ли лучший способ?

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

Ответ 1

Если вам нужны взвешенные ребра и мультиграфы, вы можете добавить еще один класс Edge.

Я бы также рекомендовал использовать generics, чтобы указать, какой подкласс класса Vertex и Edge используется в настоящее время. Например:

public class Graph<V extends Vertex> {
List<V> vertices;
...
}

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

BTW Создание таких структур эффективно может быть довольно сложным, так что, возможно, вы могли бы дать нам более подробную информацию о том, какую работу вы хотели бы использовать для них? Для более сложных задач я бы предложил вам взглянуть на различные библиотеки графиков Java, чтобы получить вдохновение.

Ответ 2

Каждый node называется однозначно и знает, с кем он связан. Список соединений позволяет подключить node к произвольному числу других узлов.

public class Node {
    public String name;
    public List<Edge> connections;
}

Каждое соединение направлено, имеет начало и конец и взвешено.

public class Edge {
    public Node start;
    public Node end;
    public double weight;
}

Граф - это ваша коллекция узлов. Вместо List<Node> рассмотрите Map<String, Node> для быстрого поиска по имени.

public class Graph {
    List<Node> nodes;
}

Ответ 3

Посмотрите на графическую библиотеку http://jung.sourceforge.net/doc/index.html. Вы все еще можете практиковать реализацию своих собственных алгоритмов (возможно, сначала начать поиск по ширине или глубине), но вам не нужно беспокоиться о создании структуры графика.

Ответ 4

Время от времени у меня была та же проблема и я сделал свою собственную реализацию. Я предлагаю вам реализовать другой класс: Edge. Затем Vertex будет иметь список границ.

public class Edge {
    private Node a, b;
    private directionEnum direction;     // AB, BA or both
    private int weight;
    ...
}

Это сработало для меня. Но может быть, так просто. Эта библиотека может помочь вам, если вы посмотрите на ее код: http://jgrapht.sourceforge.net/

Ответ 5

Я бы рекомендовал graphviz, когда вы дойдете до точки, где хотите отобразить свои графики.

и его спутники: посмотрите на Laszlo Szathmary GraphViz класс вместе с notugly.xls.

Ответ 6

Даже во время этого вопроса, более 3 лет назад, Sage (который является полностью бесплатным) существовал и был довольно хорош в теории графов. Но в 2012 году речь идет о лучшем инструменте теории графов. Таким образом, у Sage уже есть огромное количество материала теории графов, в том числе и других бесплатных и открытых исходных текстов, которые есть там. Таким образом, просто возиться с различными вещами, чтобы узнать больше, легко, так как не требуется никакого программирования.

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

В настоящее время этот ответ может быть не так полезен для OP (так как он был 3 года), но, надеюсь, он полезен для любого другого, кто видит этот вопрос в будущем.

Ответ 7

Почему бы не упростить и использовать матрицу смежности или смежность список?

Ответ 8

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

Java-реализация того же самого здесь в моем блоге.

Ответ 9

class Graph<E> {
    private List<Vertex<E>> vertices;

    private static class Vertex<E> {
        E elem;
        List<Vertex<E>> neighbors;
    }
}

Ответ 10

Простое представление, написанное "Роберт Седжвик" и "Кевин Уэйн", доступно на http://algs4.cs.princeton.edu/41graph/Graph.java.html

Объяснение скопировано с указанной выше страницы.

Класс Graph представляет собой неориентированный граф вершин от 0 до V - 1.

Он поддерживает следующие две основные операции: добавляет ребро к графику, итерации по всем вершинам, смежным с вершиной. Он также обеспечивает методы для возврата числа вершин V и числа ребер E. Разрешены параллельные ребра и автопилы. По соглашению, self-loop v-v появляется в список смежности v дважды и вносит два значения в степень v.

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

Ответ 11

class Vertex {
    private String name;
    private int score; // for path algos
    private boolean visited; // for path algos
    List<Edge> connections;
}

class Edge {
    private String vertex1Name; // same as Vertex.name
    private String vertex2Name;
    private int length;
}

class Graph {
    private List<Edge> edges;
}