QuickGraph Dijkstra exemple

J'ai un AdjacencyGraph<string, Edge<string>> qui je voudrais courir AlgorithmExtensions.ShortestPathsDijkstra sur, mais le QuickGraph la documentation n'est pas le meilleur.

Quelqu'un aurait-il un exemple que je peux suivre?

Tout ce que j'ai trouvé sur Google utilisé un observateur, ce qui le AlgorithmExtension ne nécessite pas de.

OriginalL'auteur Ben S | 2009-04-01

algorithm c#quickgraph shortest-path

12

J'ai mis à jour la doc, mais en un mot, vous avez besoin d'un graphique, une pondération de bord de la carte (en tant que délégué) et une racine de vertex. Le AlgorithmExtensions méthode retourne un 'TryFunc' que vous pouvez requête d'extraction de chemins les plus courts.
```
using QuickGraph;
using QuickGraph.Algorithms;

IVertexAndEdgeListGraph<TVertex, TEdge> graph = ...;
Func<TEdge, double> edgeCost = e => 1; //constant cost
TVertex root = ...;

//compute shortest paths
TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathDijkstra(edgeCost, root);

//query path for given vertices
TVertex target = ...;
IEnumerable<TEdge> path;
if (tryGetPaths(target, out path))
    foreach(var edge in path)
        Console.WriteLine(edge);
```
Comment puis-je utiliser cet algorithme avec la dépendance sur la touche Func<T,U>.NET 2.0? Ne QuikcGrpah cela?
La correction de fautes de frappe... TryFunc<TVertex, IEnumerable<TEdge>> tryGetPaths = graph.ShortestPathsDijkstra(edgeCost, root);

OriginalL'auteur Peli

Exemple tiré de quickgraph.codeplex.com sur l'exécution de l'Algorithme de Dijkstra sur un QuickGraph.

AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);
//Add some vertices to the graph
graph.AddVertex("A");
graph.AddVertex("B");
graph.AddVertex("C");
graph.AddVertex("D");
graph.AddVertex("E");
graph.AddVertex("F");
graph.AddVertex("G");
graph.AddVertex("H");
graph.AddVertex("I");
graph.AddVertex("J");
//Create the edges
Edge<string> a_b = new Edge<string>("A", "B");
Edge<string> a_d = new Edge<string>("A", "D");
Edge<string> b_a = new Edge<string>("B", "A");
Edge<string> b_c = new Edge<string>("B", "C");
Edge<string> b_e = new Edge<string>("B", "E");
Edge<string> c_b = new Edge<string>("C", "B");
Edge<string> c_f = new Edge<string>("C", "F");
Edge<string> c_j = new Edge<string>("C", "J");
Edge<string> d_e = new Edge<string>("D", "E");
Edge<string> d_g = new Edge<string>("D", "G");
Edge<string> e_d = new Edge<string>("E", "D");
Edge<string> e_f = new Edge<string>("E", "F");
Edge<string> e_h = new Edge<string>("E", "H");
Edge<string> f_i = new Edge<string>("F", "I");
Edge<string> f_j = new Edge<string>("F", "J");
Edge<string> g_d = new Edge<string>("G", "D");
Edge<string> g_h = new Edge<string>("G", "H");
Edge<string> h_g = new Edge<string>("H", "G");
Edge<string> h_i = new Edge<string>("H", "I");
Edge<string> i_f = new Edge<string>("I", "F");
Edge<string> i_j = new Edge<string>("I", "J");
Edge<string> i_h = new Edge<string>("I", "H");
Edge<string> j_f = new Edge<string>("J", "F");
//Add the edges
graph.AddEdge(a_b);
graph.AddEdge(a_d);
graph.AddEdge(b_a);
graph.AddEdge(b_c);
graph.AddEdge(b_e);
graph.AddEdge(c_b);
graph.AddEdge(c_f);
graph.AddEdge(c_j);
graph.AddEdge(d_e);
graph.AddEdge(d_g);
graph.AddEdge(e_d);
graph.AddEdge(e_f);
graph.AddEdge(e_h);
graph.AddEdge(f_i);
graph.AddEdge(f_j);
graph.AddEdge(g_d);
graph.AddEdge(g_h);
graph.AddEdge(h_g);
graph.AddEdge(h_i);
graph.AddEdge(i_f);
graph.AddEdge(i_h);
graph.AddEdge(i_j);
graph.AddEdge(j_f);
//Define some weights to the edges
Dictionary<Edge<string>, double> edgeCost = new Dictionary<Edge<string>, double>(graph.EdgeCount);
edgeCost.Add(a_b, 4);
edgeCost.Add(a_d, 1);
edgeCost.Add(b_a, 74);
edgeCost.Add(b_c, 2);
edgeCost.Add(b_e, 12);
edgeCost.Add(c_b, 12);
edgeCost.Add(c_f, 74);
edgeCost.Add(c_j, 12);
edgeCost.Add(d_e, 32);
edgeCost.Add(d_g, 22);
edgeCost.Add(e_d, 66);
edgeCost.Add(e_f, 76);
edgeCost.Add(e_h, 33);
edgeCost.Add(f_i, 11);
edgeCost.Add(f_j, 21);
edgeCost.Add(g_d, 12);
edgeCost.Add(g_h, 10);
edgeCost.Add(h_g, 2);
edgeCost.Add(h_i, 72);
edgeCost.Add(i_f, 31);
edgeCost.Add(i_h, 18);
edgeCost.Add(i_j, 7);
edgeCost.Add(j_f, 8);
//We want to use Dijkstra on this graph
DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, edgeCost);
//attach a distance observer to give us the shortest path distances
VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>();
distObserver.Attach(dijkstra);
//Attach a Vertex Predecessor Recorder Observer to give us the paths
VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>();
predecessorObserver.Attach(dijkstra);
//Run the algorithm with A set to be the source
dijkstra.Compute("A");
foreach (KeyValuePair<string, int> kvp in distObserver.Distances)
Console.WriteLine("Distance from root to node {0} is {1}", kvp.Key, kvp.Value);
foreach(KeyValuePair<string, Edge<string>> kvp in predecessorObserver.VertexPredecessors)
Console.WriteLine("If you want to get to {0} you have to enter through the in edge {1}", kvp.Key, kvp.Value );
//Remember to detach the observers
distObserver.Detach(dijkstra);
predecessorObserver.Detach(dijkstra);

Oui, j'ai vu cela, mais je voudrais éviter de la gestion de l'observateur de moi-même. Le AlgorithmExtension poignées de cela, et l'exemple de qu'est-ce que je suis à la recherche pour.

OriginalL'auteur KingNestor

Voici un autre exemple (cela va dans LinqPad -- assurez-vous de F4 et ajoutez une référence à la QuickGraph dll)

void Main()
{
const int nNodes = 10;
var graphAsDict = RandomGraphWithSelfEdgeAsDict(nNodes).Dump("graphAsDict: Random graph as Dict");
var velg1 = graphAsDict.ToVertexAndEdgeListGraph(
kv => Array.ConvertAll<int, SEquatableEdge<int>>(
kv.Value.ToArray(),
v => new SEquatableEdge<int>(kv.Key, v))).Dump("velg1: Vertex and Edge-List Graph");
Func<SEquatableEdge<int>, double> edgeCost = (edge => 1.0D);
int start = new Random(Guid.NewGuid().GetHashCode()).Next(1, nNodes + 1).Dump("start point");
int end = new Random(Guid.NewGuid().GetHashCode()).Next(1, nNodes + 1).Dump("end point");
var algo = new DijkstraShortestPathAlgorithm<int, SEquatableEdge<int>>(velg1, edgeCost);
var predecessors = new VertexPredecessorRecorderObserver<int, SEquatableEdge<int>>();
using (predecessors.Attach(algo))
{
algo.Compute(start);
IEnumerable<SEquatableEdge<int>> path;
if (predecessors.TryGetPath(end, out path).Dump("TryGetPath"))
path.Dump("path");
}
}
public static int[] RandomPermutation(Random ran, int n)
{
var r = Enumerable.Range(1, n).ToArray();
for (var i = 0; i < n - 1; i++)
{
var k = ran.Next(i + 1, n);
var t = r[i];
r[i] = r[k];
r[k] = t;
}
return r;
}
public static Dictionary<int, IEnumerable<int>> 
RandomGraphWithSelfEdgeAsDict(int nNodes)
{
var ran = new Random(Guid.NewGuid().GetHashCode());
var result = new Dictionary<int, IEnumerable<int>>();
for (var j = 1; j <= nNodes; j++)
{
var k = ran.Next(0, nNodes);
var cs = RandomPermutation(ran, nNodes);
result[j] = cs.Take(k);
}
return result;
}

OriginalL'auteur Reb.Cabin

Vous devez vous connecter pour publier un commentaire.