commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From d..@apache.org
Subject cvs commit: jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search DFS.java
Date Wed, 23 Jul 2003 14:07:19 GMT
ddp         2003/07/23 07:07:18

  Modified:    graph2/src/java/org/apache/commons/graph/algorithm/search
                        DFS.java
  Log:
  Adding DFS Patch from Tomasz Skutnik
  
  Here's patch against HEAD version of DFS algorithm in
  jakarta-commons-sandbox/graph2 package - it uses less memory, which is
  important for very large graphs (as in my case). Additionally DFS now
  can use lazy graph implementations without causing full, in-memory
  vertex retrieval on search initialization.
  
  Revision  Changes    Path
  1.4       +6 -16     jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java
  
  Index: DFS.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- DFS.java	1 Jan 2003 02:19:02 -0000	1.3
  +++ DFS.java	23 Jul 2003 14:07:18 -0000	1.4
  @@ -94,7 +94,8 @@
        */
       public String getColor(Vertex v)
       {
  -        return (String) colors.get(v);
  +        String color = (String)colors.get(v);
  +        return color != null ? color : WHITE;
       }
   
   
  @@ -109,7 +110,7 @@
   
           Vertex v = graph.getTarget(e);
   
  -        if (colors.get(v) == WHITE)
  +        if (getColor(v) == WHITE)
           {
               visitVertex(graph, v, visitor);
           }
  @@ -124,7 +125,6 @@
                                Vertex v,
                                Visitor visitor)
       {
  -        colors.remove(v);
           colors.put(v, GRAY);
   
           visitor.discoverVertex(v);
  @@ -138,7 +138,6 @@
   
           visitor.finishVertex(v);
   
  -        colors.remove(v);
           colors.put(v, BLACK);
       }
   
  @@ -149,12 +148,7 @@
                         Vertex root,
                         Visitor visitor)
       {
  -        Iterator vertices = graph.getVertices().iterator();
  -        while (vertices.hasNext())
  -        {
  -            colors.put(vertices.next(), WHITE);
  -        }
  -
  +        colors.clear();
           visitor.discoverGraph(graph);
   
           visitVertex(graph, root, visitor);
  @@ -166,14 +160,10 @@
        * visit - Visits all nodes in the graph.
        */
       public void visit( DirectedGraph graph, Visitor visitor ) {
  -	Iterator vertices = graph.getVertices().iterator();
  -	while (vertices.hasNext()) {
  -	    colors.put( vertices.next(), WHITE );
  -	}
  -
  +    colors.clear();
   	visitor.discoverGraph( graph );
   	
  -	vertices = graph.getVertices().iterator();
  +	Iterator vertices = graph.getVertices().iterator();
   	while (vertices.hasNext()) {
   	    Vertex v = (Vertex) vertices.next();
   
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message