Ważony wykres ukierunkowany w bibliotece QuickGraph

Question

Oto przykład mojego problemu.

Chciałbym kod w C# w taki sposób, abym mógł badać strukturę i znaleźć informacje, takie jak:

• Całkowita odległość od do B .
• Najkrótsza odległość od do E (mając na uwadze nie można iść na kierunku strzały).

Pomyślałem więc chciałbym użyć listy sąsiedztwa modelować mój wykres, ale potem pomyślałem, że jest to wspólna sprawa, i zaczął rozglądać się za biblioteki, aby pomóc przyspieszyć ten proces (nie trzeba wymyślać koła. itd.)

Natknąłem się na this Library, który polecił mi kilka razy na różne tematy, ale stwierdzam, że jest to naprawdę trudne modelowanie mojego narysowanego wykresu powyżej.

Answer 1

Możliwe rozwiązanie to modelowanie wykresu jako AdjacencyGraph<string, Edge<string>> i skonstruowanie słownika kosztowego o wartości Dictionary<Edge<string>, double>, w którym koszty stanowią odległości.

// ... 
private AdjacencyGraph<string, Edge<string>> _graph; 
private Dictionary<Edge<string>, double> _costs; 

public void SetUpEdgesAndCosts() 
{ 
    _graph = new AdjacencyGraph<string, Edge<string>>(); 
    _costs = new Dictionary<Edge<string>, double>(); 

    AddEdgeWithCosts("A", "D", 4.0); 
    // snip 
    AddEdgeWithCosts("C", "B", 1.0); 
} 

private void AddEdgeWithCosts(string source, string target, double cost) 
{ 
    var edge = new Edge<string>(source, target); 
    _graph.AddVerticesAndEdge(edge); 
    _costs.Add(edge, cost); 
} 

Twój _graph jest teraz:

Następnie można znaleźć najkrótszą drogę od A do E, używając:

private void PrintShortestPath(string @from, string to) 
{ 
    var edgeCost = AlgorithmExtensions.GetIndexer(_costs); 
    var tryGetPath = _graph.ShortestPathsDijkstra(edgeCost, @from); 

    IEnumerable<Edge<string>> path; 
    if (tryGetPath(to, out path)) 
    { 
     PrintPath(@from, to, path); 
    } 
    else 
    { 
     Console.WriteLine("No path found from {0} to {1}."); 
    } 
} 

ten jest dostosowany od QuickGraph wiki. Drukuje:

Path found from A to E: A > D > B > E