C# Graph Traversal

Question

This algorithm does a great job of traversing the nodes in a graph.

Dictionary<Node, bool> visited = new Dictionary<Node, bool>();

Queue<Node> worklist = new Queue<Node>();

visited.Add(this, false);

worklist.Enqueue(this);

while (worklist.Count != 0)
{
    Node node = worklist.Dequeue();

    foreach (Node neighbor in node.Neighbors)
    {
        if (!visited.ContainsKey(neighbor))
        {
            visited.Add(neighbor, false);
            worklist.Enqueue(neighbor);
        }
    }
}

I can use this to find a target node in the graph. The worklist dequeues (or pops) the items as the worklist is processed. Once I find the target how can I return the full path to the node?

Update I am trying to figure out how to reverse the path to the root. The method is called on the root node, after that, children may have two parents, so it isn't as simple as calling the parent property on each node and traversing back up.

The goal of the method is to find the path, not to iterate all nodes, or to check if a node does exist.

Answer 1

Is "this", that is, the current instance, the "root" of the graph, if there is such a thing?

Is the graph cyclic or acyclic? I'm afraid I don't know all the terms for graph theory.

Here's what I really wonder about:

A -> B -> C ------> F
     B -> D -> E -> F

Here are my questions:

• Will this occur?
• Can "this" in your code ever start at B?
• What will the path to F be?

If the graph never joins back together when it has split up, doesn't contain cycles, and "this" will always be the root/start of the graph, a simple dictionary will handle the path.

Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>();

for each node you visit, add the neighbouring node as key, and the node it was a neighbour of as the value. This will allow you to, once you've find the target node, to backtrack back to get the reversed path.

In other words, the dictionary for the graph above, after a full traversal would be:

B: A
C: B
D: B
E: D
F: C (or E, or both?)

To find the path to the E-node, simply backtrack:

E -> D -> B -> A

Which gives you the path:

A -> B -> D -> E

Answer 2

Since you're not tracking the path to the "current" node at all times you will have to construct that when you have found the target. If your Node class have a Parent property you could easily backtrack up the tree to construct the full path.

Answer 3

Keep track of the predecessor nodes. In the easiest implementation, this is a dictionary, and usually denoted as π in pseudo-codes:

Dictionary<Node, bool> visited = new Dictionary<Node, bool>();
Dictionary<Node, Node> π = new Dictionary<Node, Node>();

Queue<Node> worklist = new Queue<Node>();

visited.Add(this, false);

worklist.Enqueue(this);

while (worklist.Count != 0)
{
    Node node = worklist.Dequeue();

    foreach (Node neighbor in node.Neighbors)
    {
        if (!visited.ContainsKey(neighbor))
        {
            visited.Add(neighbor, false);
            π.Add(neighbor, node);
            worklist.Enqueue(neighbor);
        }
    }
}

Then you can iterate through these predecessors to backtrack the path from any node, say e:

while (π[e] != null) {
    Console.WriteLine(e);
    e = π[e];
}

Answer 4

Peter is almost correct. I don't think you can store a link to the parent vertex in the node class, because it changes depending on the vertex at which you start your breadth first search. You need to create a Parent Dictionary with the keys being nodes and the values being parent nodes. As you visit each vertex (but before processing) you add the parents to the dictionary. Then you can walk up the parent path back to the root vertex.

Answer 5

I tried use this snippet to get the alternative paths from to vertex (vertices in my code), using source and destiny, but simply dont work...

public String EncontrarMenorCaminho(Vertice o, Vertice d)
        {
            Dictionary<Vertice, bool> visited = new Dictionary<Vertice, bool>();
            Dictionary<Vertice, Vertice> previous = new Dictionary<Vertice, Vertice>();
            Queue<Vertice> worklist = new Queue<Vertice>();
            String operacao = "Registro de operações realizadas:\r\n\r\n";

            visited.Add(o, false);
            worklist.Enqueue(o);
            while (worklist.Count != 0)
            {
                Vertice v = worklist.Dequeue();
                foreach (Vertice neighbor in EncontrarVizinhos(v))
                {
                    if (!visited.ContainsKey(neighbor))
                    {
                        visited.Add(neighbor, false);
                        previous.Add(neighbor, v);
                        worklist.Enqueue(neighbor);
                    }
                }
            }

            if (previous.Count > 0)
            {
                for (int p = 0; p < previous.Count; p++)
                {
                    Vertice v1 = previous.ElementAt(p).Key;
                    Vertice v2 = previous.ElementAt(p).Value;
                    EncontrarAresta(v1, v2).Selecionado = true;
                    EncontrarAresta(v2, v1).Selecionado = true;
                    operacao += v1.Info.ToString() + "x" + v2.Info.ToString() + "\r\n";
                }
            }

            List<Vertice> grupos = new List<Vertice>();

            foreach (Aresta a in ArestasSelecionadas())
            {
                if (!grupos.Contains(a.Origem)) grupos.Add(a.Origem);
            }

            foreach (Vertice v in grupos)
            {
                int menorpeso = this.infinito;
                foreach(Vertice vz in EncontrarVizinhos(v))
                {
                    Aresta tmp = EncontrarAresta(v,vz);
                    if (tmp.Selecionado == true && tmp.Peso < menorpeso)
                    {
                        menorpeso = tmp.Peso;
                    }
                    else
                    {
                        tmp.Selecionado = false;
                    }
                }

            }




            DesenharMapa();

            return operacao;

Basicly the operation is get all marked edges (Selecionado = true) and verify again if is necessary continue selected...

In this sample, I want get the shortest path from vertext 'N' to vertex 'Q':

See a preview image here: http://img94.imageshack.us/img94/9738/grafo.png