From 6b13ba9c7a74f37fd06abe5a7e52defc3d563861 Mon Sep 17 00:00:00 2001 From: "cmzmasek@gmail.com" Date: Tue, 18 Mar 2014 02:01:36 +0000 Subject: [PATCH] inprogress --- .../evoinference/TestPhylogenyReconstruction.java | 161 +++++++++++++++++++- .../evoinference/distance/NeighborJoiningR.java | 15 +- .../org/forester/evoinference/distance/Sarray.java | 143 +++++++++++++++++ .../evoinference/distance/{S.java => Sset.java} | 4 +- 4 files changed, 307 insertions(+), 16 deletions(-) create mode 100644 forester/java/src/org/forester/evoinference/distance/Sarray.java rename forester/java/src/org/forester/evoinference/distance/{S.java => Sset.java} (99%) diff --git a/forester/java/src/org/forester/evoinference/TestPhylogenyReconstruction.java b/forester/java/src/org/forester/evoinference/TestPhylogenyReconstruction.java index a27d9f6..71f418a 100644 --- a/forester/java/src/org/forester/evoinference/TestPhylogenyReconstruction.java +++ b/forester/java/src/org/forester/evoinference/TestPhylogenyReconstruction.java @@ -39,7 +39,8 @@ import org.forester.evoinference.distance.NeighborJoining; import org.forester.evoinference.distance.NeighborJoiningF; import org.forester.evoinference.distance.NeighborJoiningR; import org.forester.evoinference.distance.PairwiseDistanceCalculator; -import org.forester.evoinference.distance.S; +import org.forester.evoinference.distance.Sarray; +import org.forester.evoinference.distance.Sset; import org.forester.evoinference.matrix.character.BasicCharacterStateMatrix; import org.forester.evoinference.matrix.character.CharacterStateMatrix; import org.forester.evoinference.matrix.character.CharacterStateMatrix.BinaryStates; @@ -84,6 +85,13 @@ public class TestPhylogenyReconstruction { else { System.out.println( " failed." ); } + System.out.println( "Sarray" ); + if ( testSarray() ) { + System.out.println( " OK." ); + } + else { + System.out.println( " failed." ); + } System.out.println( "NJR" ); if ( testNeighborJoiningR() ) { System.out.println( " OK." ); @@ -91,7 +99,7 @@ public class TestPhylogenyReconstruction { else { System.out.println( " failed." ); } - // timeNeighborJoining(); + timeNeighborJoining(); } public static boolean test( final File test_dir ) { @@ -2246,7 +2254,7 @@ public class TestPhylogenyReconstruction { private static boolean testS() { try { - final S s0 = new S(); + final Sset s0 = new Sset(); s0.initialize( 1 ); s0.addPairing( 0, 1, 0 ); s0.addPairing( 7, 8, 0 ); @@ -2381,6 +2389,147 @@ public class TestPhylogenyReconstruction { return true; } + private static boolean testSarray() { + try { + final Sarray s0 = new Sarray(); + s0.initialize( 1 ); + s0.addPairing( 0, 1, 0 ); + s0.addPairing( 7, 8, 0 ); + s0.addPairing( 4, 55, 0 ); + s0.addPairing( 2, 3, 0 ); + s0.addPairing( 4, 5, 0 ); + s0.addPairing( 5, 6666, 0 ); + s0.addPairing( 5, 666, 0 ); + s0.addPairing( 5, 66, 0 ); + s0.addPairing( 5, 6, 0 ); + s0.addPairing( 6, 7, 0 ); + s0.addPairing( 3, 4, 0 ); + s0.addPairing( 1, 2, 0 ); + if ( s0.size() != 1 ) { + return false; + } + if ( s0.getS( 0 ).size() != 8 ) { + return false; + } + if ( s0.getValues( 0, 0 ).length != 1 ) { + return false; + } + if ( s0.getValues( 1, 0 ).length != 1 ) { + return false; + } + if ( s0.getValues( 2, 0 ).length != 1 ) { + return false; + } + if ( s0.getValues( 3, 0 ).length != 1 ) { + return false; + } + if ( s0.getValues( 4, 0 ).length != 2 ) { + return false; + } + if ( s0.getValues( 5, 0 ).length != 4 ) { + return false; + } + if ( s0.getValues( 6, 0 ).length != 1 ) { + return false; + } + if ( s0.getValues( 7, 0 ).length != 1 ) { + return false; + } + if ( s0.getValues( 0, 0 )[ 0 ] != 1 ) { + return false; + } + if ( s0.getValues( 5, 0 )[ 3 ] != 6 ) { + return false; + } + if ( s0.getValues( 5, 0 )[ 2 ] != 66 ) { + return false; + } + if ( s0.getValues( 5, 0 )[ 1 ] != 666 ) { + return false; + } + if ( s0.getValues( 5, 0 )[ 0 ] != 6666 ) { + return false; + } + s0.removePairing( 5, 6666, 0 ); + if ( s0.getValues( 5, 0 ).length != 3 ) { + System.out.println( s0.getValues( 5, 0 ).length ); + return false; + } + // if ( s0.getValues( 5, 0 ).contains( 6666 ) ) { + // return false; + // } + // s0.removePairing( 5, 666, 0 ); + // if ( s0.getValues( 5, 0 ).contains( 666 ) ) { + // return false; + // } + // s0.removePairing( 5, 66, 0 ); + // if ( s0.getValues( 5, 0 ).contains( 66 ) ) { + // return false; + // } + // if ( s0.getValues( 5, 0 ).size() != 1 ) { + // return false; + // } + // if ( s0.getS( 0 ).size() != 8 ) { + // return false; + // } + // s0.removePairing( 5, 6, 0 ); + // if ( s0.getS( 0 ).size() != 7 ) { + // return false; + // } + // s0.addPairing( 5, 6, 0 ); + // if ( s0.getS( 0 ).size() != 8 ) { + // return false; + // } + // if ( s0.getValues( 5, 0 ).size() != 1 ) { + // return false; + // } + // if ( !s0.getValues( 5, 0 ).contains( 6 ) ) { + // return false; + // } + // s0.addPairing( 5, 403, 0 ); + // if ( s0.getValues( 5, 0 ).size() != 2 ) { + // return false; + // } + // if ( !s0.getValues( 5, 0 ).contains( 403 ) ) { + // return false; + // } + // s0.addPairing( 693, 100, 0 ); + // s0.addPairing( 693, 101, 0 ); + // if ( s0.getValues( 693, 0 ).size() != 2 ) { + // return false; + // } + // s0.addPairing( 2, 33, 0 ); + // s0.addPairing( 2, 333, 0 ); + // final Set[] a = s0.toArray( 0 ); + // if ( !a[ 0 ].contains( 1 ) ) { + // return false; + // } + // if ( a[ 0 ].size() != 1 ) { + // return false; + // } + // if ( !a[ 1 ].contains( 2 ) ) { + // return false; + // } + // if ( a[ 1 ].size() != 1 ) { + // return false; + // } + // if ( !a[ 2 ].contains( 3 ) ) { + // return false; + // } + // if ( !a[ 2 ].contains( 33 ) ) { + // return false; + // } + // if ( !a[ 2 ].contains( 333 ) ) { + // return false; + // } + } + catch ( final Exception e ) { + e.printStackTrace( System.out ); + return false; + } + return true; + } + private static boolean testNeighborJoiningR() { try { final NeighborJoiningR nj0 = NeighborJoiningR.createInstance(); @@ -2970,7 +3119,7 @@ public class TestPhylogenyReconstruction { private static void timeNeighborJoining() { final NeighborJoiningR njr = NeighborJoiningR.createInstance(); - for( int n = 3; n <= 9; ++n ) { + for( int n = 3; n <= 10; ++n ) { final int x = ( int ) Math.pow( 2, n ); final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x ); mt.randomize( new Date().getTime() ); @@ -2979,7 +3128,7 @@ public class TestPhylogenyReconstruction { System.out.println( "Size: " + x + " -> " + ( new Date().getTime() - start_time ) + "ms" ); } final NeighborJoiningF njf = NeighborJoiningF.createInstance(); - for( int n = 3; n <= 9; ++n ) { + for( int n = 3; n <= 10; ++n ) { final int x = ( int ) Math.pow( 2, n ); final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x ); mt.randomize( new Date().getTime() ); @@ -2988,7 +3137,7 @@ public class TestPhylogenyReconstruction { System.out.println( "Size: " + x + " -> " + ( new Date().getTime() - start_time ) + "ms" ); } final NeighborJoining nj = NeighborJoining.createInstance(); - for( int n = 3; n <= 9; ++n ) { + for( int n = 3; n <= 10; ++n ) { final int x = ( int ) Math.pow( 2, n ); final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x ); mt.randomize( new Date().getTime() ); diff --git a/forester/java/src/org/forester/evoinference/distance/NeighborJoiningR.java b/forester/java/src/org/forester/evoinference/distance/NeighborJoiningR.java index c92fd54..be18018 100644 --- a/forester/java/src/org/forester/evoinference/distance/NeighborJoiningR.java +++ b/forester/java/src/org/forester/evoinference/distance/NeighborJoiningR.java @@ -29,7 +29,6 @@ import java.text.DecimalFormat; import java.util.ArrayList; import java.util.List; import java.util.Map.Entry; -import java.util.Set; import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix; import org.forester.phylogeny.Phylogeny; @@ -49,7 +48,7 @@ public final class NeighborJoiningR { private final boolean _verbose; private int _min_i; private int _min_j; - private S _s; + private Sarray _s; private double _d_min; //TODO remove me private int[] _rev_mappings; private double _umax; @@ -274,7 +273,7 @@ public final class NeighborJoiningR { _mappings = new int[ _n ]; _rev_mappings = new int[ _n ]; _d_values = distances.getValues(); - _s = new S(); + _s = new Sarray(); _s.initialize( distances ); initExternalNodes(); if ( _verbose ) { @@ -304,8 +303,8 @@ public final class NeighborJoiningR { System.out.print( " " ); } System.out.print( "\t\t" ); - for( final Entry> entry : _s.getSentrySet( _mappings[ j ] ) ) { - System.out.print( DF.format( ( double ) entry.getKey() / S.FACTOR ) + "=" ); + for( final Entry entry : _s.getSentrySet( _mappings[ j ] ) ) { + System.out.print( DF.format( ( double ) entry.getKey() / Sarray.FACTOR ) + "=" ); boolean first = true; for( final int v : entry.getValue() ) { if ( !first ) { @@ -333,7 +332,7 @@ public final class NeighborJoiningR { X: for( int j = 1; j < _n; ++j ) { final double r_j = _r[ j ]; final int m_j = _mappings[ j ]; - for( final Entry> entry : _s.getSentrySet( m_j ) ) { + for( final Entry entry : _s.getSentrySet( m_j ) ) { for( final int sorted_i : entry.getValue() ) { final double m = _d_values[ sorted_i ][ m_j ] - ( ( _r[ _rev_mappings[ sorted_i ] ] + r_j ) / n_minus_2 ); @@ -352,7 +351,7 @@ public final class NeighborJoiningR { final double r_j = _r[ j ]; final int m_j = _mappings[ j ]; boolean first = true; - for( final Entry> entry : _s.getSentrySet( m_j ) ) { + for( final Entry entry : _s.getSentrySet( m_j ) ) { if ( first ) { first = false; continue; @@ -372,7 +371,7 @@ public final class NeighborJoiningR { } if ( _verbose ) { System.out.println(); - for( final Entry> entry : _s.getSentrySet( m_j ) ) { + for( final Entry entry : _s.getSentrySet( m_j ) ) { for( final int sorted_i : entry.getValue() ) { System.out.print( sorted_i ); System.out.print( "->" ); diff --git a/forester/java/src/org/forester/evoinference/distance/Sarray.java b/forester/java/src/org/forester/evoinference/distance/Sarray.java new file mode 100644 index 0000000..badcc69 --- /dev/null +++ b/forester/java/src/org/forester/evoinference/distance/Sarray.java @@ -0,0 +1,143 @@ + +package org.forester.evoinference.distance; + +import java.text.DecimalFormat; +import java.util.ArrayList; +import java.util.List; +import java.util.Map.Entry; +import java.util.Set; +import java.util.SortedMap; +import java.util.TreeMap; + +import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix; + +public final class Sarray { + + public final static int FACTOR = 1000000; + private final static boolean DEBUG = true; + private final List> _data; + + public Sarray() { + _data = new ArrayList>(); + } + + final public void addPairing( final double key, final int value, final int j ) { + addPairing( ( int ) ( FACTOR * key ), value, getS( j ) ); + } + + final public void addPairing( final int key, final int value, final int j ) { + addPairing( key, value, getS( j ) ); + } + + final public SortedMap getS( final int j ) { + return _data.get( j ); + } + + final public int[] getValues( final int key, final int j ) { + return getS( j ).get( key ); + } + + final public void initialize( final BasicSymmetricalDistanceMatrix d ) { + for( int j = 0; j < d.getSize(); ++j ) { + final TreeMap map = new TreeMap(); + _data.add( map ); + for( int i = 0; i < j; ++i ) { + addPairing( ( int ) ( FACTOR * d.getValues()[ i ][ j ] ), i, map ); + } + } + //System.out.println( toString() ); + } + + final public void initialize( final int size ) { + for( int j = 0; j < size; ++j ) { + final TreeMap map = new TreeMap(); + _data.add( map ); + } + } + + final public void removePairing( final double key, final int value, final int j ) { + removePairing( ( int ) ( key * FACTOR ), value, j ); + } + + final public void removePairing( final int key, final int value, final int j ) { + final SortedMap m = _data.get( j ); + final int[] x = m.get( key ); + if ( x == null ) { + System.out.println(); + System.out + .println( "________________________________________________________________________________________" ); + System.out.println( toString() ); + throw new IllegalArgumentException( "key " + key + " (->" + value + ") does not exist for row " + j ); + } + if ( x.length == 1 ) { + m.remove( key ); + } + else { + int[] xnew = new int[ x.length - 1 ]; + int xc = 0; + for( int i = 0; ++i < x.length; ++i ) { + int xv = x[ i ]; + if ( xv != value ) { + xnew[ xc++ ] = xv; + } + } + m.put( key, xnew ); + } + } + + final public int size() { + return _data.size(); + } + + // Slow, only for testing + @SuppressWarnings( "unchecked") + final public Set[] toArray( final int j ) { + return _data.get( j ).values().toArray( new Set[ _data.get( j ).size() ] ); + } + + @Override + final public String toString() { + final DecimalFormat df = new DecimalFormat( "0.000000" ); + final StringBuilder sb = new StringBuilder(); + for( int j = 0; j < size(); ++j ) { + sb.append( j ); + sb.append( ": " ); + for( final Entry entry : getSentrySet( j ) ) { + final double key = entry.getKey(); + final int[] values = entry.getValue(); + sb.append( df.format( key / FACTOR ) + "->" ); + boolean first = true; + for( final int v : values ) { + if ( !first ) { + sb.append( "," ); + } + first = false; + sb.append( v ); + } + sb.append( " " ); + } + sb.append( "\n" ); + } + return sb.toString(); + } + + final Set> getSentrySet( final int j ) { + return getS( j ).entrySet(); + } + + final private static void addPairing( final int key, final int value, final SortedMap m ) { + if ( !m.containsKey( key ) ) { + final int[] x = new int[ 1 ]; + x[ 0 ] = value; + m.put( key, x ); + } + else { + final int[] x = new int[ m.get( key ).length + 1 ]; + for( int i = 0; i < x.length - 1; i++ ) { + x[ i ] = m.get( key )[ i ]; + } + x[ x.length - 1 ] = value; + m.put( key, x ); + } + } +} diff --git a/forester/java/src/org/forester/evoinference/distance/S.java b/forester/java/src/org/forester/evoinference/distance/Sset.java similarity index 99% rename from forester/java/src/org/forester/evoinference/distance/S.java rename to forester/java/src/org/forester/evoinference/distance/Sset.java index fa05363..6ad7df3 100644 --- a/forester/java/src/org/forester/evoinference/distance/S.java +++ b/forester/java/src/org/forester/evoinference/distance/Sset.java @@ -12,13 +12,13 @@ import java.util.TreeMap; import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix; -public final class S { +public final class Sset { public final static int FACTOR = 1000000; private final static boolean DEBUG = true; private final List>> _data; - public S() { + public Sset() { _data = new ArrayList>>(); } -- 1.7.10.2