Can someone help plz!!

Topics: algorithm, graph
Oct 15, 2007 at 12:06 AM
Edited Oct 15, 2007 at 12:09 AM

// im trying to use List<> so it can be dynamic
// only way i can get this to work if i name everything individually
// making my graph pretty uselsess
////////////////////
using System;
using System.Collections.Generic;
using System.Text;

using QuickGraph;
using QuickGraph.Glee;
using QuickGraph.Graphviz;
using QuickGraph.Algorithms.ShortestPath;
using QuickGraph.Serialization;
using QuickGraph.Collections;
using QuickGraph.Algorithms.Observers;


namespace DrawLine
{
class SortGraph
{
AdjacencyGraph<int, Edge<int>> AdjGraph = new AdjacencyGraph<int, Edge<int>>();

public SortGraph()
{


}

public List<string> LoadGraph(ListLineClass myLine, int Count)
{


List<Edge<int>> EdgeList = new List<Edge<int>>();
List<string> StringList = new List<string>();

string tmpString;

for (int i = 0; i < Count; i++)
AdjGraph.AddVertex(i);


for (int i = 0; i < myLine.ListLine.Count; i++)
{

Edge<int> tmpEdge = new Edge<int>(myLine.ListLinei.NodeIndex1 + 100, myLine.ListLinei.NodeIndex2 + 100);

EdgeList.Add(tmpEdge);

}

for (int i = 0; i < EdgeList.Count; i++)
{

AdjGraph.AddEdge(EdgeListi);

}


Dictionary<Edge<int>, double> edgeLength = new Dictionary<Edge<int>, double>(AdjGraph.EdgeCount);

for (int i = 0; i < AdjGraph.EdgeCount; i++)
{

edgeLength.Add(EdgeListi, myLine.ListLinei.MyLineLength);
}

DijkstraShortestPathAlgorithm<int, Edge<int>> dijkstra =
new DijkstraShortestPathAlgorithm<int, Edge<int>>(AdjGraph, edgeLength);


VertexDistanceRecorderObserver<int, Edge<int>> distObserver =
new VertexDistanceRecorderObserver<int, Edge<int>>();
distObserver.Attach(dijkstra);

VertexPredecessorRecorderObserver<int, Edge<int>> predecessorObserver =
new VertexPredecessorRecorderObserver<int, Edge<int>>();
predecessorObserver.Attach(dijkstra);

dijkstra.Compute(1);

tmpString = "Distance KeyLoop ";
StringList.Add(tmpString);
tmpString = "Distance ValueLoop ";
StringList.Add(tmpString);
foreach (KeyValuePair<int, int> kvp in distObserver.Distances)
{
StringList0 += ", " + kvp.Key;
StringList1 += ", " + kvp.Value;

}

tmpString = "Predecessor KeyLoop ";
StringList.Add(tmpString);
tmpString = "Predecessor ValueLoop ";
StringList.Add(tmpString);
foreach (KeyValuePair<int, Edge<int>> kvp in predecessorObserver.VertexPredecessors)
{
StringList2 += ", " + kvp.Key;
StringList3 += ", " + kvp.Value;

}

distObserver.Detach(dijkstra);
predecessorObserver.Detach(dijkstra);

return StringList;
}

}
}
Coordinator
Oct 15, 2007 at 6:58 PM
I'm confused, why not use the NodeIndex as the vertices of your graph? Why are you using the edge list and not adding directly to the graph.

Since I don't know what ListLineGraph looks like, it difficult to tell what you are trying to do.
Oct 15, 2007 at 9:20 PM
Edited Oct 15, 2007 at 9:36 PM
this is the only sample I found (this is a carbon copy, just with list<>)
http://www.codeplex.com/quickgraph/Thread/View.aspx?ThreadId=12668
if you have different samples i'd love to see them. Im new the more info the better.


what my listLineGraph looks like
public class ListLineClass
{
public List<LineClass> ListLine = new List<LineClass>();
}

public class LineClass
{
public Line MyLine = new Line();

public bool NoColide;
public bool Checked;
public float MyLineLength;
public int NodeIndex1;// which 2 nodes line is connected too
public int NodeIndex2;
public Color colour;
}

Coordinator
Oct 16, 2007 at 3:50 AM
Edited Oct 16, 2007 at 3:50 AM
  • create a custom edge to hold the lineclass,
public class EdgeLineClass : TaggedEdge<LineClass>
{
    public EdgeLineClass(LineClass lc) : base(lc.NodeIndex1, lc.NodeIndex2, lc) 
    {}
}

  • fill up the graph,
AdjacencyGraph<int, EdgeLineClass> g = new ...;
foreach(LineClass lc in ...)
{
    // add vertices
    if (!g.ContainsVertex(lc.NodeIndex1)) 
        g.AddVertex(lc.NodeIndex1);
    if (!g.ContainsVertex(lc.NodeIndex2)) 
        g.AddVertex(lc.NodeIndex2);
    // add edge
    g.AddEdge(new EdgeLineClass(lc));
}

that's it :)
Oct 16, 2007 at 11:05 AM
Edited Oct 16, 2007 at 11:07 AM
thank you for the quick reply. Turns out I have a talent for making everything allot more difficult then they really are. I hope you have patience because I will be asking a few more (follow up dijskstar)
Im having trouble adding edge cost or length to the graph?

public void AddWeight()
{

Dictionary<EdgeLineClass, double> edgeLength = new Dictionary<EdgeLineClass, double>(g.EdgeCount);

for (int i = 0; i < g.EdgeCount; i++)
{
// how do i get edgecost into the graph?
edgeLength.Add( ????, myLine.ListLinei.MyLineLength);
}



}
public string MyDijkstra()
{
string tmp = "dijkstra test: ";

// IVertexListGraph<int, EdgeLineClass> MyNode = null; // a graph of cities
//IDictionary<EdgeLineClass, double> NodeDistances = null; // a dictionary of city distances

int sourceNode = 1; // starting city
int targetNode = 3; // ending city

// creating the algorithm instance
DijkstraShortestPathAlgorithm<int, EdgeLineClass> dijkstra =
new DijkstraShortestPathAlgorithm<int, EdgeLineClass>(g, NodeDistances);

// creating the observer
VertexPredecessorRecorderObserver<int, EdgeLineClass> vis = null;
try
{
vis = new VertexPredecessorRecorderObserver<int, EdgeLineClass>();
vis.Attach(dijkstra);

// compute and record shortest paths
dijkstra.Compute(sourceNode);

// vis can create all the shortest path in the graph
foreach (EdgeLineClass e in vis.Path(targetNode))
{
tmp += e.ToString();
}
}
finally
{
if (vis != null)
vis.Detach(dijkstra);
}



return tmp;
}
Coordinator
Oct 16, 2007 at 4:14 PM
Now that the edges have been added to your graph, enumerate them and update the weight map
foreach(EdgeListClass edge in g.Edges)
{
     edgeLength.Add(edge, edge.Tag.MyLineLength);
}

note: please use the wiki formating for the source code when posting questions