nanodeath / CrowLib

Crow: Find your shortest path!
http://www.effectgames.com/effect/article.psp.html/community/Pathfinding_library_Dijkstra_s_Algorithm
MIT License
40 stars 6 forks source link

Deletion of connected edges or vertices #16

Open VincentBlouin opened 12 years ago

VincentBlouin commented 12 years ago

Hi, I noticed that there is an error when removing an edge or vertex in a connected graph (no x,y coordinates) . Here are some functions that I use to delete my connected edges and vertices.

note that "graphForTraversal" in an instance of crow.Graph()

  function removeEdgeInGraphForTraversal(edge){
        var sourceVertex = graphForTraversal.getNode(
            edge.sourceVertex().getId()
        );
        var destinationVertex = graphForTraversal.getNode(
            edge.destinationVertex().getId()
        );
        removeVertexInConnections(destinationVertex, sourceVertex.connections);
        removeVertexInConnections(sourceVertex, destinationVertex.connections);         
    }

   function removeVertexInGraphForTraversal(vertex){
        graphForTraversal.removeNode(
            graphForTraversal.getNode(vertex.getId())
        );
        var node = findVertexInGraphForTraversalNodesAfterItWasDeleted(
            vertex
        );
        $.each(node.connections, function(){
            var connection = this;
            var connectedNode = graphForTraversal.getNode(connection.id);
            removeVertexInConnections(vertex, connectedNode.connections);
        });          
    }

    function removeVertexInConnections(vertex, connections){
        for(var j in connections){
            var connection = connections[j];
            if(connection.id == vertex.getId()){
                connections.splice(j,1);
            }
        }
    }

    function findVertexInGraphForTraversalNodesAfterItWasDeleted(vertex){
        for(var i in graphForTraversal.nodes){
            var node = graphForTraversal.nodes[i];
            if(node.id == vertex.getId()){
                return node;
            }
        }
    }