Получить список ребер между двумя вершинами графа

109
04 июня 2021, 18:30

Нужно реализовать метод getPath так чтобы он возвращал список ребер, путь не обязательно должен быть оптимальным, но должно учитываться isDirected то есть направленный ли граф. Не уверен что объект Edge(ребро) должен быть таким.

Текущая реализация getPath и метода collect работает только если граф в форме связанного списка. В остальных случаях не работает.

Конструктивная критика по поводу базовой структуры данных

Map<Vertex<T>, List<Edge<T>>>

очень приветствуется, не уверен что это хороший вариант.

public class Graph<T> {
    private boolean isDirected = false;
    private Map<Vertex<T>, List<Edge<T>>> graph = new HashMap<>();
    public Graph() {
    }
    public Graph(boolean isDirected) {
        this.isDirected = isDirected;
    }
    public void addEdge(T first, T second) {
        final Vertex<T> master = new Vertex<>(first);
        final Vertex<T> slave = new Vertex<>(second);
        final Set<Vertex<T>> vertices = graph.keySet();
        if (!vertices.contains(master) || !vertices.contains(slave)) {
            throw new IllegalArgumentException();
        }
        graph.get(master).add(new Edge<>(master, slave));
        if (!isDirected) {
            graph.get(slave).add(new Edge<>(slave, master));
        }
    }
    public void addVertex(T value) {
        final List<Edge<T>> result = graph.putIfAbsent(new Vertex<>(value), new ArrayList<>());
        if (result != null) {
            throw new IllegalArgumentException();
        }
    }
    public Set<Edge<T>> getPath(T from, T to) {
        final Set<Edge<T>> visitedEdges = new HashSet<>();
        if (from.equals(to)) {
            return visitedEdges;
        }
        if (!isDirected) throw new IllegalStateException("Unsupported operation (Only directed graph)");
        return collect(new Vertex<>(from), new Vertex<>(to), new HashSet<>());
    }
    private Set<Edge<T>> collect(Vertex<T> previous, Vertex<T> target, Set<Edge<T>> visited) {
        Vertex<T> current = null;
        for (Edge<T> edge : graph.get(previous)) {
            current = edge.getNext();
            visited.add(edge);
            if (current.equals(target)) {
                return visited;
            }
        }
        return isNull(current) ? visited : collect(current, target, visited);
    }
}

Вершина:

@Data
@AllArgsConstructor
@EqualsAndHashCode
public class Vertex<T> {
    private T value;
}

Ребро:

@Data
@NoArgsConstructor
@AllArgsConstructor
public class Edge<T> {
    private Vertex<T> back;
    private Vertex<T> next;
}
READ ALSO
Есть желание написать клиент серверное приложение чат для Android

Есть желание написать клиент серверное приложение чат для Android

Само приложение хотелось бы создавать на Android studioПрошу подсказать с технологиями, которые стоит использовать в создании (напр

214