QuickGraph, Graph Data Structures And Algorithms for .Net

Source code checked in, #19968

pelikhan — Wed, 16 Jul 2008 07:11:25 GMT

added support for msagl

Source code checked in, #19967

pelikhan — Wed, 16 Jul 2008 07:10:59 GMT

updated version number

New Post: layout algorithms

palesz — Tue, 08 Jul 2008 22:50:49 GMT

The implemented algorithms:
- Class diagram layout and Sugiyama
- Fruchterman-Reingold
- LinLog
- ISOM
- Kamada-Kawai

and i'm planning to implement more algorithms.

New Post: layout algorithms

palesz — Tue, 08 Jul 2008 22:49:24 GMT

I've implemented some layout algorithms (based on the interfaces of the QuickGraph). The implementation is not public at the moment, but i would like to make it opensource (i need some time to do this), so please wait for a little while... :)

New Post: Output from Dijkstra Algorithm

yavnery — Sat, 05 Jul 2008 12:28:59 GMT

Hi

First, I would like to thank you for creating QuickGraph

I have some problems with dijekstra

is it suppose to work?

I have observed the source code and found that its usind the dfs algorithm events.
in dijekstra you suppose to choose an edge that gives the minimal weight path from the discovered group to some vertex that wasnt discovered yet:

in each step
    examine the edges that goes out from the discovered vertices to the other
    select the closest undiscovered vertex v such that w(s,v) is minaimal
    add v to the discovered vertices

but what happens in the code is different.
its a simple dfs that doesnt choose the "right" vertex in each step

The key to success is to make it choose the right edge in each step, any idea how to make the dfs do that?

New Post: Need help with the dll's and with DFS.

Marcosjgr — Thu, 03 Jul 2008 15:13:54 GMT

Now I write the example about DFS.
For all the people new (like me) in QuickGraph i gonna a share my example:

namespace MyGraphDFS
{
    class Program
    {
        static void Main(string[] args)
        {
        AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);
            //Creando los Vertices
            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");

            // Creating Edges
            Edge<string> a_b = new Edge<string>("A", "B");
            Edge<string> e_b = new Edge<string>("E", "B");
            Edge<string> e_f = new Edge<string>("E", "F");
            Edge<string> h_f = new Edge<string>("H", "F");
            Edge<string> b_i = new Edge<string>("B", "I");
            Edge<string> f_i = new Edge<string>("F", "I");
            Edge<string> i_c = new Edge<string>("I", "C");
            Edge<string> i_g = new Edge<string>("I", "G");
            Edge<string> c_d = new Edge<string>("C", "D");
            Edge<string> c_b = new Edge<string>("C", "B");

            // Adding Edges
            graph.AddEdge(a_b);
            graph.AddEdge(e_b);
            graph.AddEdge(e_f);
            graph.AddEdge(h_f);
            graph.AddEdge(b_i);
            graph.AddEdge(f_i);
            graph.AddEdge(i_c);
            graph.AddEdge(i_g);
            graph.AddEdge(c_d);
            graph.AddEdge(c_b);

            ArrayList Entradas = new ArrayList();


            // Creating the algorithm dfs
            DepthFirstSearchAlgorithm<string, Edge<string>> dfs = new DepthFirstSearchAlgorithm<string, Edge<string>>(graph);

            PredecessorRecorder p = new PredecessorRecorder();

            // Add this if you want to search the shortes path only in Dijstra not necesary in DFS
            VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>();
            distObserver.Attach(dfs);



            // Adding the observer to take the output from DFS
            VertexRecorderObserver<string, Edge<string>> Observarecorrevertice = new VertexRecorderObserver<string, Edge<string>>();
            Observarecorrevertice.Attach(dfs);

            //Adding other observer, not necesary add this if you want to see what it does
            VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>();
            predecessorObserver.Attach(dfs);

            //Not necesay, add if you want to see what it does
        EdgePredecessorRecorderObserver<string, Edge<string>> edgepreobs = new EdgePredecessorRecorderObserver<string, Edge<string>>();
            //EdgeRecorderObserver<string, Edge<string>> recorredorobservadorarista = new EdgeRecorderObserver<string, Edge<string>>();
            //recorredorobservadorarista.Attach(dfs);

            // Add this if you want that the user enter the start path
        // If not put only dfs.Compute("A"); or the letter that you want
            Console.WriteLine("Ingrese el nodo inicial de recorrido: A, B, C, D, E, F, G, H, I ");
            string nodo = Console.ReadLine();
            nodo = nodo.ToUpper();

            //Add this if you want to see what the events does
        dfs.StartVertex += new VertexEventHandler<string>(dfs_StartVertex);
            dfs.DiscoverVertex += new VertexEventHandler<string>(dfs_DiscoverVertex);
            dfs.FinishVertex += new VertexEventHandler<string>(dfs_FinishVertex);
            dfs.ForwardOrCrossEdge += new EdgeEventHandler<string, Edge<string>>(dfs_ForwardOrCrossEdge);

        //Start DFS algorithm
            dfs.Compute(nodo);

            Console.WriteLine("El recorrido en algoritmo DFS partiendo de {0} es:", nodo);
            //Here print the DFS result, if you want to save the output add the ArrayList if not only put all and delete lnodos
            ArrayList lnodos = new ArrayList();
            int recorredorlnodos = 0;
            foreach (string a in Observarecorrevertice.Vertices)
            {
                Console.Write(a);
                lnodos.Add(a);
                //Console.WriteLine(lnodos[recorredorlnodos]);
                recorredorlnodos++;
            }
            Console.WriteLine();
            Console.WriteLine("Los nodos de todo el recorrido son:");
            //Add this if you want to print the total recorder
            foreach (KeyValuePair<string, int> kvp in distObserver.Distances)
                Console.Write(kvp.Key);

            Console.WriteLine();
            //Add this if you want to print predecessors
            Console.WriteLine("Todos los caminos apartir del nodo {0} son:", nodo);
            foreach (KeyValuePair<string, Edge<string>> kvp in predecessorObserver.VertexPredecessor)
                Console.WriteLine("{1} {2}", nodo, kvp.Key, kvp.Value);

            //Add this if you want to print the final Vertices in the path
        Console.WriteLine("Vertices Finales de cada ciclo:");
            foreach (string z in predecessorObserver.EndPathVertices)
                Console.WriteLine(z);

            //Not necesary
            //Console.WriteLine("hola");
            //foreach (Edge<string> c in recorredorobservadorarista.Edges)
            //{
            //    Console.WriteLine(c);
            //    if (c.Source == c.Source)
            //        Console.WriteLine("queonda");
            //}

            // don't forget add this
            Observarecorrevertice.Detach(dfs);
            distObserver.Detach(dfs);
            predecessorObserver.Detach(dfs);

            //recorredorobservadorarista.Detach(dfs);

            //Not necesary put this if you want
        foreach (string v in graph.Vertices)
                foreach (Edge<string> e in graph.OutEdges(v))
                    Console.WriteLine(e);
            //The same not necesary
        foreach (KeyValuePair<Edge<string>,Edge<string>> x in edgepreobs.EdgePredecessors)
                Console.WriteLine(x.Value);

            Console.Read();
        }

        //Here you can see how the events works, if you don't want to use the events just comment or delete this and the handlers (//Add this if you want to see what the events does).
    static void dfs_StartVertex(object sender, VertexEventArgs<string> e)
        {

            Console.WriteLine("Ocurrio el evento StartVertex! Aqui estan los Vertices de entradas:");
            ArrayList Ent = new ArrayList();
            foreach (char x in e.Vertex)
            {
                Console.WriteLine(x);
                Ent.Add(x);

            }
            int i;
            for (i = 0; i < 1; i++)
                Console.WriteLine(Ent[i]);
            //throw new Exception("The method or operation is not implemented.");
        }

        static void dfs_ForwardOrCrossEdge(object sender, EdgeEventArgs<string, Edge<string>> e)
        {
            Console.WriteLine("Ocurrio el Evento ForwardOrCrossEdge");

            //throw new Exception("The method or operation is not implemented.");
        }

        static void dfs_FinishVertex(object sender, VertexEventArgs<string> e)
        {
            Console.WriteLine("Evento FinishVertex, Vertice siguiente:");
            foreach (char y in e.Vertex)
                Console.WriteLine(y);
            //throw new Exception("The method or operation is not implemented.");
        }

        static void dfs_DiscoverVertex(object sender, VertexEventArgs<string> e)
        {
            Console.WriteLine("Se ha inciado el Evento DiscoverVertex, se descubre un Vertex");
            foreach (char x in e.Vertex)
                Console.WriteLine(x);
            //throw new Exception("The method or operation is not implemented.");

        }
    }
}

Well I post other question (Ordering Graph), if anybody know the answer please share it.

Marcosjgr wrote:
Hi.

I need some help with the program. I downloaded the source and i create my graph like this:

using

System;

using

System.Collections.Generic;

using

System.Text;

using

QuickGraph;

using

QuickGraph.Algorithms;

using

QuickGraph.Algorithms.Search;

namespace

GrafoDFS

{

class Program

{

static void Main(string[] args)

{

AdjacencyGraph<int, TaggedEdge<int, string>> g = new AdjacencyGraph<int, TaggedEdge<int, string>>();

int v1 = 1;

int v2 = 2;

int v3 = 3;

int v4 = 4;

int v5 = 5;

int v6 = 6;

int v7 = 7;

int v8 = 8;

int v9 = 9;

int v10 = 10;

g.AddVertex(v1);

g.AddVertex(v2);

g.AddVertex(v3);

g.AddVertex(v4);

g.AddVertex(v5);

g.AddVertex(v6);

g.AddVertex(v7);

g.AddVertex(v8);

g.AddVertex(v9);

g.AddVertex(v10);

TaggedEdge<int, string> e1 = new TaggedEdge<int, string>(v1, v2, "Aristae1");

g.AddEdge(e1);

TaggedEdge<int, string> e2 = new TaggedEdge<int, string>(v2, v3, "Aristae2");

g.AddEdge(e2);

TaggedEdge<int, string> e3 = new TaggedEdge<int, string>(v3, v4, "Aristae3");

g.AddEdge(e3);

TaggedEdge<int, string> e4 = new TaggedEdge<int, string>(v3, v5, "Aristae4");

g.AddEdge(e4);

TaggedEdge<int, string> e5 = new TaggedEdge<int, string>(v5, v6, "Aristae5");

g.AddEdge(e5);

TaggedEdge<int, string> e6 = new TaggedEdge<int, string>(v6, v7, "Aristae6");

g.AddEdge(e6);

TaggedEdge<int, string> e7 = new TaggedEdge<int, string>(v7, v8, "Aristae7");

g.AddEdge(e7);

TaggedEdge<int, string> e8 = new TaggedEdge<int, string>(v8, v9, "Aristae8");

g.AddEdge(e8);

TaggedEdge<int, string> e9 = new TaggedEdge<int, string>(v9, v10, "Aristae9");

g.AddEdge(e9);

TaggedEdge<int, string> e10 = new TaggedEdge<int, string>(v10, v4, "Aristae10");

g.AddEdge(e10);

foreach (int v in g.Vertices)

Console.WriteLine(v);

Console.ReadKey();

}

}

Well so now i read your manual to implement DFS:

// A graph that implements the IVertexListGraph interface
IvertexListGraph<Vertex,Edge> g = ...;

In this Step I have IvertexListGraph class but in <Vertex,Edge> but Vertex does not appears in the context of the librarys.

// create algorithm
DepthFirstSearchAlgorithm< Vertex,Edge > dfs
= new DepthFirstSearchAlgorithm<Vertex,Edge>(g);
//do the search
dfs.Compute();

So Anybody can help me to implement DFS in my example, please?
And where is the link to download the correct and complete library?

I have Microsoft Visual Studio 2005 SP1 Pro Edition with XP Pro.

Thanks.

Sorry about bad english.

New Post: Examples to start from

amorphis — Thu, 03 Jul 2008 12:22:54 GMT

Is it possible to provide a complete short example application with any visualization?
Your documentation does not help much.

Thanx in advance,

New Post: Find all paths from start vertex to the end vertex.

urubucremoso — Thu, 03 Jul 2008 12:08:41 GMT

Hi all.

I'm using quick graph in my project and I need to know the number of paths from the start vertex to the end vertex, it doesn't matter the size of the path, just the number of paths. I searched in this API but it hasn't a way to do this. does it have?

Does anyone know how can I implement this? I'm studying the possibility of implement a kind of DFS algorithm, but with some changes to do this? Is it the best solution or is there a better one?

Thanks a lot.

New Post: Ordering graphs.

Marcosjgr — Wed, 02 Jul 2008 21:34:58 GMT

Hi.
I just started with QuickGraph and I want to ordering the output of the graph. Example:
We have the Nodes connected like:

     Edge<string> a_b = new Edge<string>("A", "B");
     Edge<string> e_b = new Edge<string>("E", "B");
     Edge<string> e_f = new Edge<string>("E", "F");
     Edge<string> h_f = new Edge<string>("H", "F");
     Edge<string> b_i = new Edge<string>("B", "I");
     Edge<string> f_i = new Edge<string>("F", "I");
     Edge<string> i_c = new Edge<string>("I", "C");
     Edge<string> i_g = new Edge<string>("I", "G");
     Edge<string> c_d = new Edge<string>("C", "D");
     Edge<string> c_b = new Edge<string>("C", "B");

So I want to print in this order, first the possible starting nodes, I mean the nodes that does not had InEdges behind:
In this case [A,E,H]
And then the others nodes that had the previous predecessor nodes [A,E,H]
In this case [F, B, I, G, C, D]
So the the final printing is:
[A, E, H, F, B, I, G, C, D]

Anybody know how to do it?

Thanks.

New Post: Output from Dijkstra Algorithm

ElSendrella — Sun, 29 Jun 2008 20:55:04 GMT

Really It was agreat discussion as iam new with quick graph and also want to run the dijkstra algorithm With SharpMap,
But I have some Questions:

1)AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);
   1.1)what's true value mean??
   1.2) are this wil be available if we exchange "string" with sharpMap.Geometry of type Point ??????

2)what's Mean By 'observers' ??? and can u just give me alittle explain about it's types i will use to run the dijkstraaa like:"VertexPredecessorRecorderObserver"and it's importance???

3)your cade seeked to compute all pathes from Node "A",
   Well,What about i want to get the shortest path from Node "A" To Node "D" ForExample.

4) why we do that:
// Remember to detach the observers
distObserver.Detach(dijkstra);
predecessorObserver.Detach(dijkstra);

thanxx in advance,
ElSendrella

New Post: QuickGraph ASP.NET and C#

novakmfk — Fri, 20 Jun 2008 15:01:34 GMT

What is necessary for to perform QuickGraph (Graphviz) using ASP.NET and C#?, Could you put some code example?, please, thx.

New Post: Need help with the dll's and with DFS.

Marcosjgr — Wed, 18 Jun 2008 16:30:27 GMT

Hi.

I need some help with the program. I downloaded the source and i create my graph like this:

using

System;

using

System.Collections.Generic;

using

System.Text;

using

QuickGraph;

using

QuickGraph.Algorithms;

using

QuickGraph.Algorithms.Search;

namespace

GrafoDFS

{

class Program

{

static void Main(string[] args)

{

AdjacencyGraph<int, TaggedEdge<int, string>> g = new AdjacencyGraph<int, TaggedEdge<int, string>>();

int v1 = 1;

int v2 = 2;

int v3 = 3;

int v4 = 4;

int v5 = 5;

int v6 = 6;

int v7 = 7;

int v8 = 8;

int v9 = 9;

int v10 = 10;

g.AddVertex(v1);

g.AddVertex(v2);

g.AddVertex(v3);

g.AddVertex(v4);

g.AddVertex(v5);

g.AddVertex(v6);

g.AddVertex(v7);

g.AddVertex(v8);

g.AddVertex(v9);

g.AddVertex(v10);

TaggedEdge<int, string> e1 = new TaggedEdge<int, string>(v1, v2, "Aristae1");

g.AddEdge(e1);

TaggedEdge<int, string> e2 = new TaggedEdge<int, string>(v2, v3, "Aristae2");

g.AddEdge(e2);

TaggedEdge<int, string> e3 = new TaggedEdge<int, string>(v3, v4, "Aristae3");

g.AddEdge(e3);

TaggedEdge<int, string> e4 = new TaggedEdge<int, string>(v3, v5, "Aristae4");

g.AddEdge(e4);

TaggedEdge<int, string> e5 = new TaggedEdge<int, string>(v5, v6, "Aristae5");

g.AddEdge(e5);

TaggedEdge<int, string> e6 = new TaggedEdge<int, string>(v6, v7, "Aristae6");

g.AddEdge(e6);

TaggedEdge<int, string> e7 = new TaggedEdge<int, string>(v7, v8, "Aristae7");

g.AddEdge(e7);

TaggedEdge<int, string> e8 = new TaggedEdge<int, string>(v8, v9, "Aristae8");

g.AddEdge(e8);

TaggedEdge<int, string> e9 = new TaggedEdge<int, string>(v9, v10, "Aristae9");

g.AddEdge(e9);

TaggedEdge<int, string> e10 = new TaggedEdge<int, string>(v10, v4, "Aristae10");

g.AddEdge(e10);

foreach (int v in g.Vertices)

Console.WriteLine(v);

Console.ReadKey();

}

New Post: Need Help about BFS

PetreL — Mon, 16 Jun 2008 21:57:34 GMT

Hi,
I am using QuickGraph library to implement a graph of states of a robot. I use the state of the robot as a Vertex and the control I give to the robot as a tag in an Edge.
I need help in using BFS since I am new in using this library. I need a way to give a starting state and a finish state and use BFS to find the quickest (least states between start and finish) route.
Is there a way to have BFS give me a list of edges so I can extract the commands from them?

Thanks in advance,

New Post: Loop Detection In Graph

ben123 — Wed, 11 Jun 2008 05:10:22 GMT

I actually found a way to do it. What I did was I only created a graph and then wrote a recursive function to enumerate each of the outedges and check to see if the next node is in the current
list of visited nodes. Seems to work. I also didn't use any of the algorithms or events.
Thanks anyway.

New Post: VertexColorDictionary

VansFannel — Tue, 10 Jun 2008 08:23:13 GMT

I've cheked out the last version from server on May, 30.

Today this class there isn't on server. Problem solved.

Updated Wiki: Developer Manual

pelikhan — Tue, 10 Jun 2008 07:52:55 GMT

Developer Manual

Compiling Pex

to compile the tests, install Pex http://research.microsoft.com/Pex/downloads.aspx
compile QuickGraph.sln

New Post: Loop Detection In Graph

pelikhan — Tue, 10 Jun 2008 07:52:02 GMT

You can detect loops by doing a depth first search and listening to back edges (gray edges). There's no algorithm in Pex that can enumerate all cycles. I suggest looking in the literature for such algorithm.

New Post: VertexColorDictionary

pelikhan — Tue, 10 Jun 2008 07:48:23 GMT

HeightFirstSearchDictionary? Which version are you using?

Source code checked in, #18592

pelikhan — Tue, 10 Jun 2008 07:46:02 GMT

more pex tests

Source code checked in, #18591

pelikhan — Tue, 10 Jun 2008 07:44:04 GMT

- requires Pex to compile. Download available at http://research.microsoft.com/pex