c# - grafo - busqueda en profundidad c++

Implementación de la primera búsqueda de profundidad en C#usando List and Stack

Question

Quiero crear una primera búsqueda de profundidad en la que he tenido cierto éxito.

Aquí está mi código hasta ahora (Excepto mi constructor, tenga en cuenta que las clases Vertex y Edge solo contienen propiedades, nada importante que publicar aquí):

private Stack<Vertex> workerStack = new Stack<Vertex>();
private List<Vertex> vertices = new List<Vertex>();
private List<Edge> edges = new List<Edge>();

private int numberOfVertices;
private int numberOfClosedVertices;
private int visitNumber = 1;

private void StartSearch()
{
    // Make sure to visit all vertices
    while (numberOfClosedVertices < numberOfVertices && workerStack.Count > 0)
    {
        // Get top element in stack and mark it as visited
        Vertex workingVertex = workerStack.Pop();
        workingVertex.State = State.Visited;

        workingVertex.VisitNumber = visitNumber;
        visitNumber++;

        numberOfClosedVertices++;

        // Get all edges connected to the working vertex
        foreach (Vertex vertex in GetConnectedVertices(workingVertex))
        {
            vertex.Parent = workingVertex;
            workerStack.Push(vertex);
        }
    }
}

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> vertices = new List<Vertex>();

    // Get all vertices connected to vertex and is unvisited, then add them to the vertices list
    edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

    return vertices;
}

Está trabajando en la forma en que se visitan todos los vértices, pero no en el orden correcto.

Aquí hay una comparación de cómo se visita la mina en comparación con la wikipedia:

Parece que el mío está cambiando y está comenzando de derecha a izquierda.

¿Sabes qué lo causa? (También cualquier consejo sobre mi implementación sería muy apreciado)

Gracias

EDIT: obtuve mi respuesta, pero aún quería mostrar el resultado final para el método GetConnectedVertices:

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> connectingVertices = new List<Vertex>();

    (from edge in edges
     where edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited
     select edge).
     Reverse().
     ToList().
     ForEach(edge => connectingVertices.Add(edge.VertexTarget));

    return connectingVertices;
}

Answer 1

Parece que el mío está cambiando y está comenzando de derecha a izquierda. ¿Sabes qué lo causa?

Como han notado otros, está presionando los nodos-a-visitar-siguiente en la pila en orden de izquierda a derecha. Eso significa que se saltan de derecha a izquierda, ya que una pila invierte el orden. Las pilas son las últimas en entrar, primero en salir.

Puede solucionar el problema haciendo que GetConnectedVertices cree una pila, no una lista. De esta forma, los vértices conectados se invierten dos veces , una vez cuando van a la pila devuelta y una vez cuando entran en la pila real.

También agradecería cualquier consejo sobre mi implementación

La implementación funciona, supongo, pero tiene muchos problemas fundamentales. Si me presentaran ese código para su revisión, esto es lo que diría:

En primer lugar, suponga que desea hacer dos búsquedas en profundidad de esta estructura de datos al mismo tiempo. Ya sea porque lo estaba haciendo en varios hilos, o porque tiene un bucle anidado en el que el bucle interno hace un DFS para un elemento diferente al bucle externo. ¿Lo que pasa? Interfieren entre sí porque ambos intentan mutar los campos "Estado" y "VisitNumber". Es realmente una mala idea tener lo que debería ser una operación "limpia" como buscar realmente hacer que su estructura de datos esté "sucia".

Hacerlo también imposibilita el uso de datos permanentes inmutables para representar partes redundantes de su gráfico.

Además, noto que omites el código que limpia. ¿Cuándo se vuelve a establecer "Estado" en su valor original? ¿Qué pasa si hiciste un segundo DFS? Inmediatamente fallaría ya que la raíz ya está visitada.

Una mejor opción por todas estas razones es mantener el estado "visitado" en su propio objeto, no en cada vértice.

A continuación, ¿por qué todos los objetos de estado son variables privadas de una clase? Este es un algoritmo simple; no hay necesidad de construir una clase completa para ello. Un primer algoritmo de búsqueda de profundidad debe tomar el gráfico para buscar como un parámetro formal, no como un estado de objeto, y debe mantener su propio estado local según sea necesario en las variables locales, no en los campos.

Luego, la abstracción de la gráfica es ... bueno, no es una abstracción. Son dos listas, una de vértices y otra de bordes. ¿Cómo sabemos que esas dos listas son incluso consistentes? Supongamos que hay vértices que no están en la lista de vértices pero están en la lista de bordes. ¿Cómo lo previenen? Lo que quieres es una abstracción gráfica. Deje que la implementación de la abstracción gráfica se preocupe por cómo representar los bordes y encontrar vecinos.

Luego, tu uso de ForEach es legal y común, pero me duele la cabeza. Es difícil leer su código y razonar al respecto con todas las lambdas. Tenemos una declaración "foreach" perfectamente buena. Úselo.

A continuación, está mutando una propiedad "principal", pero no está del todo claro para qué es esta propiedad o por qué está siendo mutada durante un cruce. Los vértices en un gráfico arbitrario no tienen "padres" a menos que el gráfico sea un árbol, y si el gráfico es un árbol, entonces no hay necesidad de realizar un seguimiento del estado "visitado"; no hay bucles en un árbol. ¿Que esta pasando aqui? Este código es simplemente extraño, y no es necesario realizar un DFS.

Luego, su método de ayuda llamado GetConnectedVertices es una mentira. No tiene vértices conectados, se conecta vértices no visitados. Los métodos cuyos nombres se encuentran son muy confusos.

¡Finalmente, esto pretende ser una búsqueda en profundidad, pero no busca nada! ¿Dónde se está buscando lo que se busca? ¿Dónde se devuelve el resultado? Esto no es una búsqueda, es un cruce.

Comenzar de nuevo. ¿Qué deseas? Un recorrido en profundidad de un gráfico dado un vértice inicial . Entonces implemente eso. Comience por definir lo que está atravesando. Un gráfico. ¿Qué servicio necesitas de un gráfico? Una forma de obtener el conjunto de vértices vecinos:

interface IGraph
{
    IEnumerable<Vertex> GetNeighbours(Vertex v);
}

¿Cuál es tu método de retorno? Una secuencia de vértices en primer orden en profundidad. ¿Qué se necesita? Un vértice inicial. DE ACUERDO:

static class Extensions
{
    public static IEnumerable<Vertex> DepthFirstTraversal(
        this IGraph graph, 
        Vertex start) 
    { ... }
}

Ahora tenemos una implementación trivial de la primera búsqueda en profundidad; ahora puede usar la cláusula Where:

IGraph myGraph = whatever;
Vertex start = whatever;
Vertex result = myGraph.DepthFirstTraversal(start)
                       .Where(v=>something)
                       .FirstOrDefault();

OK, entonces, ¿cómo vamos a implementar ese método para que haga un cruce sin arruinar el estado del gráfico? Mantenga su propio estado externo:

public static IEnumerable<Vertex> DepthFirstTraversal(
    this IGraph graph, 
    Vertex start) 
{
    var visited = new HashSet<Vertex>();
    var stack = new Stack<Vertex>();

    stack.Push(start);

    while(stack.Count != 0)
    {
        var current = stack.Pop();

        if(!visited.Add(current))
            continue;

        yield return current;

        var neighbours = graph.GetNeighbours(current)
                              .Where(n=>!visited.Contains(n));

        // If you don''t care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse()) 
            stack.Push(neighbour);
    }
}

¿Ves cuánto más limpio y más corto es eso? Sin mutación de estado. Sin perder el tiempo con listas de bordes. No hay funciones auxiliares mal nombradas. Y el código realmente hace lo que dice que hace: atraviesa un gráfico.

También obtenemos los beneficios de los bloques de iteradores; es decir, si alguien está usando esto para una búsqueda de DF, entonces la iteración se abandona cuando se cumplen los criterios de búsqueda. No tenemos que hacer un cruce completo si encontramos el resultado temprano.

Answer 2

El problema está en el orden en que buscas los elementos. Tu for each en StartSearch no garantiza el orden de los elementos. Tampoco encuentra FindAll en el método GetConnectedVertices . Miremos esta línea:

edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

Debe agregar un OrderBy() para garantizar el orden deseado.

Answer 3

Esta es mi implementación, una pila es lo suficientemente buena. Se realiza un reverso antes del ciclo foreach.

    /// <summary>
    /// Depth first search implementation in c#
    /// </summary>
    /// <typeparam name="T">Type of tree structure item</typeparam>
    /// <typeparam name="TChilds">Type of childs collection</typeparam>
    /// <param name="node">Starting node to search</param>
    /// <param name="ChildsProperty">Property to return child node</param>
    /// <param name="Match">Predicate for matching</param>
    /// <returns>The instance of matched result, null if not found</returns>
    public static T DepthFirstSearch<T, TChilds>(this T node, Func<T, TChilds> ChildsProperty, Predicate<T> Match) 
        where T:class
    {
        if (!(ChildsProperty(node) is IEnumerable<T>))
            throw new ArgumentException("ChildsProperty must be IEnumerable<T>");

        Stack<T> stack = new Stack<T>();
        stack.Push(node);
        while (stack.Count > 0) {
            T thisNode = stack.Pop();
            #if DEBUG
            System.Diagnostics.Debug.WriteLine(thisNode.ToString());
            #endif
            if (Match(thisNode))
                return thisNode;
            if (ChildsProperty(thisNode) != null) {
                foreach (T child in (ChildsProperty(thisNode) as IEnumerable<T>).Reverse()) 
                    stack.Push(child);
            }
        }
        return null;
    }

Answer 4

Generalicé el código de @ Eric para el cruce DFS para cualquier T para hacer que las cosas funcionen para cualquier tipo que tenga hijos, pensé que compartiría:

public static IEnumerable<T> DepthFirstTraversal<T>(
    T start,
    Func<T, IEnumerable<T>> getNeighbours)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(start);

    while (stack.Count != 0)
    {
        var current = stack.Pop();
        visited.Add(current);
        yield return current;

        var neighbours = getNeighbours(current).Where(node => !visited.Contains(node));

        // If you don''t care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse())
        {
            stack.Push(neighbour);
        }
    }
}

Ejemplo de uso:

var nodes = DepthFirstTraversal(myNode, n => n.Neighbours);

Answer 5

Los elementos se mostrarán de la pila en el orden inverso al modo en que se insertan:

stach.push () resulta en: 1 2 3 4 5

stack.pop () da como resultado: 5 4 3 2 1 (entonces: de derecha a izquierda)

Answer 6

Puede disfrutar esto:

        public static bool DepthFirstSearch<T>(this IEnumerable<T> vertices, T rootVertex, T targetVertex, Func<T, IEnumerable<T>> getConnectedVertices, Func<T, T, bool> matchFunction = null)
    {
        if (getConnectedVertices == null)
        {
            throw new ArgumentNullException("getConnectedVertices");
        }
        if (matchFunction == null)
        {
            matchFunction = (t, u) => object.Equals(t, u);
        }
        var directlyConnectedVertices = getConnectedVertices(rootVertex);
        foreach (var vertex in directlyConnectedVertices)
        {
            if (matchFunction(vertex, targetVertex))
            {
                return true;
            }
            else if (vertices.DepthFirstSearch(vertex, targetVertex, getConnectedVertices, matchFunction))
            {
                return true;
            }
        }
        return false;
    }