Нужно реализовать метод 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;
}
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Само приложение хотелось бы создавать на Android studioПрошу подсказать с технологиями, которые стоит использовать в создании (напр