Need help with the dll's and with DFS.

Topics: algorithm, graph
Jun 18, 2008 at 5:30 PM
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.

Jul 3, 2008 at 4:13 PM
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.




Coordinator
Aug 25, 2008 at 6:26 PM
Could you please layout correctly your entires? They are barely readable (too much white space, etc...) Thanks.