public ArrayDBIDs topologicalSort ( ) { ArrayModifiableDBIDs ids = DBIDUtil . newArray ( this . ids ) ; if ( mergeOrder != null ) { ids . sort ( new DataStoreUtil . AscendingByIntegerDataStore ( mergeOrder ) ) ; WritableDoubleDataStore maxheight = computeMaxHeight ( ) ; ids . sort ( new Sorter ( maxheight ) ) ; maxheight . destroy ( ) ; } else { ids . sort ( new DataStoreUtil . DescendingByDoubleDataStoreAndId ( parentDistance ) ) ; } // We used to simply sort by merging distance // But for e.g. Median Linkage, this would lead to problems, as links are // not necessarily performed in ascending order anymore! final int size = ids . size ( ) ; ModifiableDBIDs seen = DBIDUtil . newHashSet ( size ) ; ArrayModifiableDBIDs order = DBIDUtil . newArray ( size ) ; DBIDVar v1 = DBIDUtil . newVar ( ) , prev = DBIDUtil . newVar ( ) ; // Process merges in descending order for ( DBIDIter it = ids . iter ( ) ; it . valid ( ) ; it . advance ( ) ) { if ( ! seen . add ( it ) ) { continue ; } final int begin = order . size ( ) ; order . add ( it ) ; prev . set ( it ) ; // Copy // Follow parents of prev -> v1 - these need to come before prev. while ( ! DBIDUtil . equal ( prev , parent . assignVar ( prev , v1 ) ) ) { if ( ! seen . add ( v1 ) ) { break ; } order . add ( v1 ) ; prev . set ( v1 ) ; // Copy } // Reverse the inserted path: for ( int i = begin , j = order . size ( ) - 1 ; i < j ; i ++ , j -- ) { order . swap ( i , j ) ; } } // Reverse everything for ( int i = 0 , j = size - 1 ; i < j ; i ++ , j -- ) { order . swap ( i , j ) ; } return order ; }
Topological sort the object IDs .