Помощь в реализации Java Graph

Question

Мне нужно написать программу, которая сохраняет вершины в графе и соединяет их. Вход для программы дан как:

Plot 3 5 to 5 8
Plot 6 1 to 3 5
etc

Исходя из этого ввода, я буду хранить вершины (3,5), которые являются x и y координатами. Затем я должен был бы соединить эту координату с (5,8).

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

Answer 1

Простой способ думать о графиках - разбить их на компоненты Node и Edge.(Примечание: то, что вы называете вершиной, я называю узлом. Достаточно близко.)

Давайте рассмотрим следующие варианты:

// Option 1
class Node<V> {
    V data;
    Set<Node<V>> edges;
    // if it were a directed graph, you'd need:
    // Set<Node<V>> edgesAway;
}

// Option 2
class Node<V> {
    V data;
    Set<Edge<V>> edges;
    // if it were a directed graph, you'd need:
    // Set<Edge<V>> edgesAway;
}

class Edge<V> {
    Node<V> source;
    Node<V> destination;
}

Теперь график - это не более чем:

// option 1
class Graph<V> {
    Set<Node<V>> nodes;
}

// option 2
class Graph<V> {
    Set<Node<V>> nodes;
    Set<Edge<V>> edges;
}

Вариант 1 является самым простым и простым в реализации.Вариант 2 дает вам больше гибкости, например, добавляет веса к значениям ребер.

Теперь у вас есть данные в этих узлах, верно?А пока давайте просто представим данные как строковое представление координат.

class SomeObject {
    String data;
    int x;
    int y;

    public boolean equals(Object o) {
        if(o instanceof SomeObject) {
            SomeObject so = (SomeObject)o;
            return so.x == x && so.y == y;
        }
        return false;
    }

    public int hashCode() {
        return x * 100 + y; // it works... close enough :)
    }
}

// somewhere later:
Graph<SomeObject> graph = ...

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

Answer 2

Для этого вы можете использовать уже созданную библиотеку, например JDSL