You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2011/06/18 16:52:31 UTC
svn commit: r1137196 - in
/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit:
NodeSequenceVisitor.java VisitTestCase.java
Author: simonetripodi
Date: Sat Jun 18 14:52:30 2011
New Revision: 1137196
URL: http://svn.apache.org/viewvc?rev=1137196&view=rev
Log:
added DepthFirstSearch test case
Added:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java (with props)
Modified:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java?rev=1137196&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java Sat Jun 18 14:52:30 2011
@@ -0,0 +1,54 @@
+package org.apache.commons.graph.visit;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import static java.util.Collections.unmodifiableList;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Vertex;
+
+public final class NodeSequenceVisitor<V extends Vertex, E extends Edge<V>>
+ extends BaseGraphVisitHandler<V, E>
+{
+
+ private final List<V> vertices = new ArrayList<V>();
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public void discoverVertex(V vertex) {
+ vertices.add( vertex );
+ }
+
+ /**
+ *
+ *
+ * @return
+ */
+ public List<V> getVertices()
+ {
+ return unmodifiableList( vertices );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java?rev=1137196&r1=1137195&r2=1137196&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java Sat Jun 18 14:52:30 2011
@@ -23,11 +23,13 @@ import static org.apache.commons.graph.v
import static org.apache.commons.graph.visit.Visit.depthFirstSearch;
import static org.junit.Assert.assertEquals;
+import java.util.ArrayList;
+import java.util.List;
+
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.model.BaseLabeledEdge;
import org.apache.commons.graph.model.BaseLabeledVertex;
import org.apache.commons.graph.model.UndirectedMutableGraph;
-import org.junit.Ignore;
import org.junit.Test;
public final class VisitTestCase
@@ -106,11 +108,76 @@ public final class VisitTestCase
assertEquals( expected, actual );
}
+ /**
+ * Graph picture can be see
+ * <a href="http://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/">here</a>
+ */
@Test
- @Ignore
public void verifyDepthFirstSearch()
{
- depthFirstSearch( null, null );
+ // vertices
+
+ BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+ BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+ BaseLabeledVertex c = new BaseLabeledVertex( "C" );
+ BaseLabeledVertex d = new BaseLabeledVertex( "D" );
+ BaseLabeledVertex e = new BaseLabeledVertex( "E" );
+ BaseLabeledVertex f = new BaseLabeledVertex( "F" );
+ BaseLabeledVertex g = new BaseLabeledVertex( "G" );
+ BaseLabeledVertex h = new BaseLabeledVertex( "H" );
+ BaseLabeledVertex s = new BaseLabeledVertex( "S" );
+
+ // input graph
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> input =
+ new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>();
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+ input.addVertex( d );
+ input.addVertex( e );
+ input.addVertex( f );
+ input.addVertex( g );
+ input.addVertex( h );
+ input.addVertex( s );
+
+ input.addEdge( new BaseLabeledEdge( "", s, a ) );
+ input.addEdge( new BaseLabeledEdge( "", s, b ) );
+
+ input.addEdge( new BaseLabeledEdge( "", a, c ) );
+ input.addEdge( new BaseLabeledEdge( "", a, d ) );
+
+ input.addEdge( new BaseLabeledEdge( "", b, e ) );
+ input.addEdge( new BaseLabeledEdge( "", b, f ) );
+
+ input.addEdge( new BaseLabeledEdge( "", e, g ) );
+ input.addEdge( new BaseLabeledEdge( "", e, h ) );
+
+ // expected node set
+
+ // order is not the same in the pic, due to Stack use
+ final List<BaseLabeledVertex> expected = new ArrayList<BaseLabeledVertex>();
+ expected.add( s );
+ expected.add( b );
+ expected.add( e );
+ expected.add( h );
+ expected.add( g );
+ expected.add( f );
+ expected.add( a );
+ expected.add( d );
+ expected.add( c );
+
+ // actual node set
+
+ NodeSequenceVisitor<BaseLabeledVertex, BaseLabeledEdge> visitor =
+ new NodeSequenceVisitor<BaseLabeledVertex, BaseLabeledEdge>();
+ depthFirstSearch( input, s, visitor );
+ final List<BaseLabeledVertex> actual = visitor.getVertices();
+
+ // assertion
+
+ assertEquals( expected, actual );
}
}