diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-0 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-0
new file mode 100755
index 0000000..474b6b2
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-0
Binary files differ
diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-1 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-1
new file mode 100755
index 0000000..bc848f4
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-1
Binary files differ
diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-2 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-2
new file mode 100755
index 0000000..e3deba6
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-2
Binary files differ
diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-3 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-3
new file mode 100755
index 0000000..da5be93
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/singleread/part-3
Binary files differ
diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-0 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-0
new file mode 100755
index 0000000..9364723
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-0
Binary files differ
diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-1 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-1
new file mode 100755
index 0000000..ee43a38
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-1
Binary files differ
diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-2 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-2
new file mode 100755
index 0000000..5983e27
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-2
Binary files differ
diff --git a/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-3 b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-3
new file mode 100755
index 0000000..ffacdcf
--- /dev/null
+++ b/genomix/genomix-pregelix/data/PathTestSet_bidirection/tworeads_6/part-3
Binary files differ
diff --git a/genomix/genomix-pregelix/data/input/singleread b/genomix/genomix-pregelix/data/input/singleread
new file mode 100644
index 0000000..f99f2a9
--- /dev/null
+++ b/genomix/genomix-pregelix/data/input/singleread
@@ -0,0 +1 @@
+1	CCGTACGC
diff --git a/genomix/genomix-pregelix/data/input/tworeads_6 b/genomix/genomix-pregelix/data/input/tworeads_6
new file mode 100644
index 0000000..6cea299
--- /dev/null
+++ b/genomix/genomix-pregelix/data/input/tworeads_6
@@ -0,0 +1,2 @@
+1	AATAGAAC
+2	CCGTACGC
diff --git a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/format/DataCleanOutputFormat.java b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/format/DataCleanOutputFormat.java
index 1a961d8..24ee22e 100644
--- a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/format/DataCleanOutputFormat.java
+++ b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/format/DataCleanOutputFormat.java
@@ -8,7 +8,6 @@
 
 import edu.uci.ics.genomix.pregelix.api.io.binary.BinaryDataCleanVertexOutputFormat;
 import edu.uci.ics.genomix.pregelix.io.VertexValueWritable;
-import edu.uci.ics.genomix.pregelix.type.MessageFlag;
 import edu.uci.ics.genomix.type.PositionWritable;
 import edu.uci.ics.pregelix.api.graph.Vertex;
 import edu.uci.ics.pregelix.api.io.VertexWriter;
diff --git a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/graph/Graph.java b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/graph/Graph.java
index 3e66beb..3c24344 100644
--- a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/graph/Graph.java
+++ b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/graph/Graph.java
@@ -6,7 +6,9 @@
 
 public class Graph {
 
-    /**
+    private BufferedReader br;
+
+	/**
      * Construct a DOT graph in memory, convert it
      * to image and store the image in the file system.
      * 
@@ -14,7 +16,7 @@
      */
     private void start(String fileName) throws Exception {
         File filePathTo = new File("graph/" + fileName);
-        BufferedReader br = new BufferedReader(new FileReader(filePathTo));
+        br = new BufferedReader(new FileReader(filePathTo));
         String line = "";
         String[] split;
 
diff --git a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/io/VertexValueWritable.java b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/io/VertexValueWritable.java
index 9274c80..6befe53 100644
--- a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/io/VertexValueWritable.java
+++ b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/io/VertexValueWritable.java
@@ -25,10 +25,14 @@
     }
     
     public static class State extends VertexStateFlag{
+    	public static final byte HEAD_SHOULD_MERGEWITHPREV = 0b101 << 0;
+	    public static final byte HEAD_SHOULD_MERGEWITHNEXT = 0b111 << 0;
+    	    
         public static final byte NO_MERGE = 0b00 << 3;
         public static final byte SHOULD_MERGEWITHNEXT = 0b01 << 3;
         public static final byte SHOULD_MERGEWITHPREV = 0b10 << 3;
         public static final byte SHOULD_MERGE_MASK = 0b11 << 3;
+        public static final byte SHOULD_MERGE_CLEAR = 0b1110011;
     }
     
     private AdjacencyListWritable incomingList;
diff --git a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/BasicPathMergeVertex.java b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/BasicPathMergeVertex.java
index 07f1ff5..edadc50 100644
--- a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/BasicPathMergeVertex.java
+++ b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/BasicPathMergeVertex.java
@@ -222,22 +222,22 @@
      */
     public void startSendMsg() {
         if (VertexUtil.isHeadVertexWithIndegree(getVertexValue())) {
-            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.SHOULD_MERGEWITHNEXT));
+            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.HEAD_SHOULD_MERGEWITHNEXT));
             sendMsgToAllNextNodes(getVertexValue());
             voteToHalt();
         }
         if (VertexUtil.isRearVertexWithOutdegree(getVertexValue())) {
-            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.SHOULD_MERGEWITHPREV));
+            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.HEAD_SHOULD_MERGEWITHPREV));
             sendMsgToAllPreviousNodes(getVertexValue());
             voteToHalt();
         }
         if (VertexUtil.isHeadWithoutIndegree(getVertexValue())){
-            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.SHOULD_MERGEWITHNEXT));
+            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.HEAD_SHOULD_MERGEWITHNEXT));
             sendMsg(getVertexId(), outgoingMsg); //send to itself
             voteToHalt();
         }
         if (VertexUtil.isRearWithoutOutdegree(getVertexValue())){
-            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.SHOULD_MERGEWITHPREV));
+            outgoingMsg.setFlag((byte)(MessageFlag.IS_HEAD | MessageFlag.HEAD_SHOULD_MERGEWITHPREV));
             sendMsg(getVertexId(), outgoingMsg); //send to itself
             voteToHalt();
         }
@@ -390,7 +390,7 @@
         if(headFlag > 0)
             outFlag |= MessageFlag.IS_HEAD;
         switch(getVertexValue().getState() & State.SHOULD_MERGE_MASK) {
-            case MessageFlag.SHOULD_MERGEWITHNEXT:
+            case State.SHOULD_MERGEWITHNEXT:
                 setSuccessorAdjMsg();
                 if(ifFlipWithPredecessor())
                     outgoingMsg.setFlip(true);
@@ -401,7 +401,7 @@
                 sendMsg(getNextDestVertexId(getVertexValue()), outgoingMsg);
                 deleteVertex(getVertexId());
                 break;
-            case MessageFlag.SHOULD_MERGEWITHPREV:
+            case State.SHOULD_MERGEWITHPREV:
                 setPredecessorAdjMsg();
                 if(ifFilpWithSuccessor())
                     outgoingMsg.setFlip(true);
@@ -415,34 +415,62 @@
         }
     }
     
+    public void setStateAsMergeWithNext(){
+    	byte state = getVertexValue().getState();
+        state |= State.SHOULD_MERGEWITHNEXT;
+        getVertexValue().setState(state);
+    }
+    
+    public byte isHeadShouldMergeWithPrev(){
+    	return (byte) (getVertexValue().getState() & State.HEAD_SHOULD_MERGEWITHPREV);
+    }
     /**
      * This vertex tries to merge with next vertex and send update msg to neighber
      * @throws IOException 
      */
     public void sendUpdateMsgToPredecessor(){
-        byte state = getVertexValue().getState();
-        state |= State.SHOULD_MERGEWITHNEXT;
-        getVertexValue().setState(state);
-        if(getVertexValue().getFFList().getLength() > 0)
-            getVertexValue().setMergeDest(getVertexValue().getFFList().getPosition(0));
-        else
-            getVertexValue().setMergeDest(getVertexValue().getFRList().getPosition(0));
-        broadcastUpdateMsg();
+    	setStateAsMergeWithNext();
+    	if(isHeadShouldMergeWithPrev() == 0){
+		    if(getVertexValue().getFFList().getLength() > 0)
+		        getVertexValue().setMergeDest(getVertexValue().getFFList().getPosition(0));
+		    else
+		        getVertexValue().setMergeDest(getVertexValue().getFRList().getPosition(0));
+		    broadcastUpdateMsg();
+    	}
     }
     
+    public void setStateAsMergeWithPrev(){
+        byte state = getVertexValue().getState();
+        state |= State.SHOULD_MERGEWITHPREV;
+        getVertexValue().setState(state);
+    }
+    
+    public byte isHeadShouldMergeWithNext(){
+    	return (byte) (getVertexValue().getState() & State.HEAD_SHOULD_MERGEWITHNEXT);
+    }
     /**
      * This vertex tries to merge with next vertex and send update msg to neighber
      * @throws IOException 
      */
     public void sendUpdateMsgToSuccessor(){
-        byte state = getVertexValue().getState();
-        state |= State.SHOULD_MERGEWITHPREV;
+    	setStateAsMergeWithPrev();
+    	if(isHeadShouldMergeWithNext() == 0){
+		    if(getVertexValue().getRFList().getLength() > 0)
+		        getVertexValue().setMergeDest(getVertexValue().getRFList().getPosition(0));
+		    else
+		        getVertexValue().setMergeDest(getVertexValue().getRRList().getPosition(0));
+		    broadcastUpdateMsg();
+    	}
+    }
+    
+    /**
+     * set state as no_merge
+     */
+    public void setStateAsNoMerge(){
+    	byte state = getVertexValue().getState();
+    	//state |= State.SHOULD_MERGE_CLEAR;
+        state |= State.NO_MERGE;
         getVertexValue().setState(state);
-        if(getVertexValue().getRFList().getLength() > 0)
-            getVertexValue().setMergeDest(getVertexValue().getRFList().getPosition(0));
-        else
-            getVertexValue().setMergeDest(getVertexValue().getRRList().getPosition(0));
-        broadcastUpdateMsg();
     }
     
     /**
diff --git a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/P4ForPathMergeVertex.java b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/P4ForPathMergeVertex.java
index 02916ec..c66830c 100644
--- a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/P4ForPathMergeVertex.java
+++ b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/operator/pathmerge/P4ForPathMergeVertex.java
@@ -94,17 +94,16 @@
         // "deterministically random", based on node id
         //randGenerator.setSeed(randSeed);
         //randSeed = randGenerator.nextInt();
-        randGenerator.setSeed((randSeed ^ nodeID.hashCode()) * 100000);//randSeed + nodeID.hashCode()
+        randGenerator.setSeed((randSeed ^ nodeID.hashCode()) * 100000 * getSuperstep());//randSeed + nodeID.hashCode()
         return randGenerator.nextFloat() < probBeingRandomHead;
     }
-
+    
     /**
      * set nextID to the element that's next (in the node's FF or FR list), returning true when there is a next neighbor
      */
+
+
     protected boolean setNextInfo(VertexValueWritable value) {
-        if(headFlag > 0 && (getVertexValue().getState() & State.SHOULD_MERGEWITHPREV) > 0){
-            return false;
-        }
         if (value.getFFList().getCountOfPosition() > 0) {
             nextID.set(value.getFFList().getPosition(0));
             nextHead = isNodeRandomHead(nextID);
@@ -121,8 +120,9 @@
     /**
      * set prevID to the element that's previous (in the node's RR or RF list), returning true when there is a previous neighbor
      */
+     
     protected boolean setPrevInfo(VertexValueWritable value) {
-        if(headFlag > 0 && (getVertexValue().getState() & State.SHOULD_MERGEWITHNEXT) > 0){
+        if(headFlag > 0 && (getVertexValue().getState() & State.HEAD_SHOULD_MERGEWITHNEXT) > 0){
             return false;
         }
         if (value.getRRList().getCountOfPosition() > 0) {
@@ -152,6 +152,7 @@
             outFlag |= headFlag;
             
             outFlag |= MessageFlag.NO_MERGE;
+            setStateAsNoMerge();
             
             // only PATH vertices are present. Find the ID's for my neighbors
             curID.set(getVertexId());
@@ -167,12 +168,12 @@
                 if (curHead) {
                     if (hasNext && !nextHead && (getNextDestVertexId(getVertexValue()) != null)) {
                         // compress this head to the forward tail
-                        sendUpdateMsgToPredecessor(); //TODO up -> update  From -> to
+                		sendUpdateMsgToPredecessor(); //TODO up -> update  From -> to
                     } else if (hasPrev && !prevHead && (getPreDestVertexId(getVertexValue()) != null)) {
                         // compress this head to the reverse tail
                         sendUpdateMsgToSuccessor();
-                    } else
-                        voteToHalt();
+                    } //else
+                        //voteToHalt();
                 } else {
                     // I'm a tail
                     if (hasNext && hasPrev) {
@@ -180,24 +181,24 @@
                             // tails on both sides, and I'm the "local minimum"
                             // compress me towards the tail in forward dir
                             sendUpdateMsgToPredecessor();
-                        } else
-                            voteToHalt();
+                        } //else
+                            //voteToHalt();
                     } else if (!hasPrev) {
                         // no previous node
                         if (!nextHead && curID.compareTo(nextID) < 0) {
                             // merge towards tail in forward dir
                             sendUpdateMsgToPredecessor();
-                        } else
-                            voteToHalt();
+                        } //else
+                            //voteToHalt();
                     } else if (!hasNext) {
                         // no next node
                         if (!prevHead && curID.compareTo(prevID) < 0) {
                             // merge towards tail in reverse dir
                             sendUpdateMsgToSuccessor();
-                        } else
-                            voteToHalt();
-                    } else
-                        voteToHalt();
+                        } //else
+                            //voteToHalt();
+                    } //else
+                        //voteToHalt();
                 }
             }
         }
@@ -206,7 +207,7 @@
             while (msgIterator.hasNext()) {
                 incomingMsg = msgIterator.next();
                 processUpdate();
-                voteToHalt();
+                //voteToHalt();
             }
         } else if (getSuperstep() % 4 == 1){
             //send message to the merge object and kill self
diff --git a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/type/MessageFlag.java b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/type/MessageFlag.java
index 7b1b4e5..9468681 100644
--- a/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/type/MessageFlag.java
+++ b/genomix/genomix-pregelix/src/main/java/edu/uci/ics/genomix/pregelix/type/MessageFlag.java
@@ -3,6 +3,8 @@
 public class MessageFlag extends DirectionFlag {
     
     //public static final byte FLIP = 1 << 6;
+    public static final byte HEAD_SHOULD_MERGEWITHPREV = 0b101 << 0;
+    public static final byte HEAD_SHOULD_MERGEWITHNEXT = 0b111 << 0;
 
     
     public static String getFlagAsString(byte code) {
diff --git a/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobGen/JobGenerator.java b/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobGen/JobGenerator.java
index 62e5725..2c85e42 100644
--- a/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobGen/JobGenerator.java
+++ b/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobGen/JobGenerator.java
@@ -83,7 +83,7 @@
     private static void generateP4ForMergeGraphJob(String jobName, String outputPath) throws IOException {
         PregelixJob job = new PregelixJob(jobName);
         job.setVertexClass(P4ForPathMergeVertex.class);
-        job.setVertexInputFormatClass(DataCleanInputFormat.class);
+        job.setVertexInputFormatClass(NaiveAlgorithmForPathMergeInputFormat.class); //DataCleanInputFormat
         job.setVertexOutputFormatClass(DataCleanOutputFormat.class);
         job.setDynamicVertexValueSize(true);
         job.setOutputKeyClass(PositionWritable.class);
diff --git a/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobRun/PathMergeSmallTestSuite.java b/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobRun/PathMergeSmallTestSuite.java
index fd12bbd..44d24d6 100644
--- a/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobRun/PathMergeSmallTestSuite.java
+++ b/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/JobRun/PathMergeSmallTestSuite.java
@@ -45,6 +45,7 @@
 
     public static final String PreFix = "data/PathTestSet_bidirection"; //"graphbuildresult";
     public static final String[] TestDir = { PreFix + File.separator
+    + "tworeads_6"};/*
     + "2", PreFix + File.separator
     + "3", PreFix + File.separator
     + "4", PreFix + File.separator
@@ -52,7 +53,8 @@
     + "6", PreFix + File.separator
     + "7", PreFix + File.separator
     + "8", PreFix + File.separator
-    + "9", PreFix + File.separator};
+    + "9", PreFix + File.separator
+    + "tworeads"}; 
     /*+ "tipremove/TipRemoveGraph/bin/tworeads"};
     + "bridgeadd/BridgeAddGraph/bin/tworeads"};, PreFix + File.separator
     + "tipadd/TipAddGraph/bin/read"}, PreFix + File.separator
diff --git a/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/graphbuilding/JobRunStepByStepTest.java b/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/graphbuilding/JobRunStepByStepTest.java
index efaab3f..cc9e2d2 100644
--- a/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/graphbuilding/JobRunStepByStepTest.java
+++ b/genomix/genomix-pregelix/src/test/java/edu/uci/ics/genomix/pregelix/graphbuilding/JobRunStepByStepTest.java
@@ -46,11 +46,11 @@
 @SuppressWarnings("deprecation")
 public class JobRunStepByStepTest {
     private static final int KmerSize = 3;
-    private static final int ReadLength = 11;
+    private static final int ReadLength = 8;
     private static final String ACTUAL_RESULT_DIR = "actual";
     private static final String PATH_TO_HADOOP_CONF = "src/test/resources/hadoop/conf";
 
-    private static final String DATA_INPUT_PATH = "data/graphbuild.test/pathmerge_TestSet/9";
+    private static final String DATA_INPUT_PATH = "data/input/singleread";
     private static final String HDFS_INPUT_PATH = "/webmap";
     private static final String HDFS_OUTPUT_PATH = "/webmap_result";
 
diff --git a/genomix/genomix-pregelix/src/test/resources/jobs/P4ForMergeGraph.xml b/genomix/genomix-pregelix/src/test/resources/jobs/P4ForMergeGraph.xml
index ed5773c..ae0dc7e 100644
--- a/genomix/genomix-pregelix/src/test/resources/jobs/P4ForMergeGraph.xml
+++ b/genomix/genomix-pregelix/src/test/resources/jobs/P4ForMergeGraph.xml
@@ -122,7 +122,7 @@
 <property><name>mapred.map.tasks.speculative.execution</name><value>true</value></property>
 <property><name>mapred.inmem.merge.threshold</name><value>1000</value></property>
 <property><name>hadoop.logfile.size</name><value>10000000</value></property>
-<property><name>pregelix.vertexInputFormatClass</name><value>edu.uci.ics.genomix.pregelix.format.DataCleanInputFormat</value></property>
+<property><name>pregelix.vertexInputFormatClass</name><value>edu.uci.ics.genomix.pregelix.format.NaiveAlgorithmForPathMergeInputFormat</value></property>
 <property><name>mapred.job.queue.name</name><value>default</value></property>
 <property><name>mapred.job.tracker.persist.jobstatus.active</name><value>false</value></property>
 <property><name>pregelix.incStateLength</name><value>true</value></property>