Каким образом я могу представить взвешенный ориентированный граф в Java?

Question

Мне нужен метод, который будет обходить график, работая на смежности, возвращая общий вес пути.Я не уверен, как идти о добавлении веса в методе "public double getPathWeight (List path)".Кроме того, возможно, у меня есть ощущение, что мой публичный метод void addEdge может содержать некоторые ошибки, поэтому, если бы я мог получить некоторые указатели и на этот метод, это помогло бы мне невероятно завершить мой график.Мой график написан в терминах общего параметра VertexType.И я работаю со структурой данных списка смежности.

import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.Map;
import java.util.Set;
import java.util.List;

public class Graph<VertexType> {
private Map<VertexType, TreeMap<VertexType, Double>> adjacency;

public Graph()
{
    adjacency = new java.util.HashMap<>();
}

public void addEdge(VertexType v1, VertexType v2, double weight)
{
    Set <VertexType> set = new HashSet<VertexType>(); 

    if(adjacency.get(v1)!=null)
    {
        set = (Set<VertexType>) adjacency.get(v1); 
        set.add(v2); 
        adjacency.put(v1,(TreeMap<VertexType, Double>) set); 
    }
    else //adds edge if adjacency is null
    {
        set.add(v2); 
        adjacency.put(v1,(TreeMap<VertexType, Double>) set); 
    }
}


public Set<VertexType> getVertices()
{
    return adjacency.keySet();
}

public void dumpGraph()
{
    for (Map.Entry<VertexType,TreeMap<VertexType,Double>> entry :
             adjacency.entrySet())
    {
        System.out.println(entry.getKey() + " -> " + 
entry.getValue());
    }
}


public double getPathWeight(List<VertexType> path) throws 
GraphPathException
{

       //need help with this method

    }

}

Answer 1

Чтобы было проще, я хотел бы, чтобы вы кое-что подумали:

• Почему вы вводите Set в вашем addEdge методе?Можете ли вы выполнить задачу добавления ребра без него?

• Как рассчитать вес пути?Подумайте о том, чтобы просто перебирать узлы / вершины, заданные в аргументе getPathWeight, и искать в своем adjacency.

Я думаю, что это довольно просто, вам просто нужно знать как получить вес ребра, который находится между 2 заданными вершинами (Но сначала вам нужно проверить из вашего adjacency, что этот ребро действительно существует, или список, заданный path, неверен, можетв этом случае следует исключить).

Фактический код будет выглядеть примерно так, но я бы посоветовал вам сначала подумать самостоятельно и попробовать написать код, прежде чем читать дальше.:) (Я думаю, что если вы можете решить структуру данных для Графа - которая составляет Map<VertexType, Map<VertexType, Double>>, и я чувствую, что она достаточно хороша, то вы можете легко заполнить метод getPathWeight правильным кодом самостоятельно)

У вас может быть простой тип реализации addEdge:

public void addEdge(VertexType v1, VertexType v2, double weight) {
    adjacency.computeIfAbsent(v1, v -> new HashMap<>()).put(v2,weight);
}

Простая реализация getPathWeight:

public double getPathWeight(List<VertexType> path) throws GraphPathException {
    VertexType previousVertex = path.get(0);

    double resultWeight = 0.0;
    for (int i = 1; i < path.size(); i++) {
        VertexType currentVertex = path.get(i);
        Map<VertexType, Double> adjacencyForPreviousVertex = adjacency.get(previousVertex);
        if (adjacencyForPreviousVertex == null) {
            throw new GraphPathException("Vertex " + previousVertex + " don't exist in graph");
        }
        Double currentEdgeWeight = adjacencyForPreviousVertex.get(currentVertex);
        if (currentEdgeWeight == null) {
            throw new GraphPathException(currentVertex + "Vertex don't exist as an adjacent Vertex of " + previousVertex);
        }
        resultWeight += currentEdgeWeight;
        previousVertex = currentVertex;
    }
    return resultWeight;
}

Answer 2

Не дав вам ответа, позвольте мне изложить подход.Предположим, у нас есть следующие данные:

{A -> {C -> 10, D -> 100}}
{C -> {D -> 10}}
{D -> {}}

Итак, A подключен к C & D, C подключен к D.Очень простой DAG.

Позволяет вычислить стоимость пути A -> C -> D.

Сначала мы вычислим стоимость вершины A -> C.Нам нужно получить A с внешней карты, это даст нам {C -> 10, D -> 100}.Далее нам нужно получить конец вершины, поэтому мы получаем C из внутреннего Map - 10.

Итак A -> C = 10.

Сначала мы рассчитаем стоимостьвершины C -> D.Нам нужно получить C с внешней карты, это даст нам {C -> {D -> 10}}.Далее нам нужно получить конец вершины, поэтому мы получаем D из внутреннего Map - 10.

Итак C -> D = 10.

Общая стоимость: 20

---

Как выглядит алгоритм для этого?В псевдокоде:

double weight = 0;
for (int i = 0; i < path.size() - 1; ++i) {
    Map<> inner = adjacency[path[i]]
    weight += inner[path[i + 1]]
}

Мы перебираем path до одного элемента до конца.Затем мы получаем начальную вершину из adjacency и получаем конечную вершину из inner.Это дает нам стоимость этого преимущества.Мы добавляем это к общей сумме.

Затем мы перемещаем один вдоль path - предыдущий конечный край становится следующим начальным краем.

Мы зацикливаемся до одного перед концом pathпоскольку мы всегда «заглядываем вперед» на одну вещь;т.е. последний край не может стать начальным краем, так как нет конечного края.