\n" ;
$v = (int) $line ;
# attribute prefix, appendix, and weight to the array entry
#$tarr = array ( 'p' => "$i" , 'a' => "$j" , 'w' => $v ) ;
array_push ( $brr , $v ) ;
}
array_push ( $arr, $brr ) ;
}
fclose ( $handle ) ;
return $arr ;
}
function zerolist ( $weights , $n = 16 ) {
$arr = array ( ) ;
for ( $i = 0 ; $i < $n ; $i++ ) {
for ( $j = 0 ; $j < $n ; $j++ ) {
if ( $i == $j )
continue ;
$v = $weights [ $i ] [ $j ] ;
#$tarr = array ( 'p' => "$i" , 'a' => "$j" , 'w' => $v ) ;
#array_push ( $arr , $tarr ) ;
$entry = "$i-$j" ;
$arr [ $entry ] = $v ;
}
}
return $arr ;
}
function construct_iter ( $a_demands_b , $weights ) {
$iteration = array ( ) ;
for ( $i = 0 ; $i < count ( $a_demands_b ) ; $i++ ) {
$focus = $a_demands_b [ $i ] ;
$fp = $focus [ 'p' ] ;
$fa = $focus [ 'a' ] ;
$fw = $focus [ 'w' ] ;
# initial insurance: no repeat nodes
if ( $fp == $fa )
continue ;
for ( $j = 0 ; $j < count ( $a_demands_b ) ; $j++ ) {
$secondary = $a_demands_b [ $j ] ;
$sp = $secondary [ 'p' ] ;
$sa = $secondary [ 'a' ] ;
$sw = $secondary [ 'w' ] ;
# initial insurance: no repeat nodes
if ( $sp == $sa )
continue ;
if ( $fp == $sa )
continue ;
# collect prefix-appendix match
if ( $fa == $sp ) {
$np = "$fp-$fa" ;
$na = "$sa" ;
$nw = $fw + $weights [ $sp ] [ $sa ] ;
$narr = array ( 'p' => $np , 'a' => $na , 'w' => $nw ) ;
array_push ( $iteration , $narr ) ;
}
}
}
return $iteration ;
}
function iterate ( $iteration , $weights , $count ) {
# get current size (count the vertices)
reset ( $iteration ) ;
$key = key ( $iteration ) ;
preg_match_all ( '/(\d+)/' , $key , $matches ) ;
$current = count ( $matches [ 1 ] ) - 1 ;
# determine the increase in size to perform
$increase = ( $current * 2 >= $count ) ? $count - $current - 1 : $current ;
$increase = 1 ;
# perform initial constrained extension
$deposit = array ( ) ;
foreach ( $iteration as $fkey => $fval ) {
# strip numbers from sequence
preg_match_all ( '/(\d+)/' , $fkey , $matches ) ;
$num_arr = $matches [ 1 ] ;
$strip = $increase ;
# the focus set of remaining items
$fset = array ( ) ;
for ( $i = 0 ; $i < $strip ; $i++ )
array_push ( $fset , array_shift ( $num_arr ) ) ;
$fnk = implode ( '-' , $num_arr ) ;
#sort ( $fset ) ;
#$fst = implode ( '.' , $fset ) ;
#echo "new key: $fnk ; new str: $fst
\n" ;
foreach ( $iteration as $skey => $sval ) {
# strip numbers from sequence
preg_match_all ( '/(\d+)/' , $skey , $matches ) ;
$s_arr = $matches [ 1 ] ;
# the secondary set of remaining items
$sset = array ( ) ;
for ( $i = 0 ; $i < $strip ; $i++ )
array_unshift ( $sset , array_pop ( $s_arr ) ) ;
$snk = implode ( '-' , $s_arr ) ;
$sst = implode ( '-' , $sset ) ;
$intersect = array_intersect ( $fset , $sset ) ;
if ( $fnk == $snk && count ( $intersect ) == 0 ) {
$entry = "$fkey-$sst" ;
$wsum = $fval ;
$wsum = $wsum + $weights [ $num_arr [ count ( $num_arr ) - 1 ] ] [ $sset [ 0 ] ] ;
for ( $i = 1 ; $i < count ( $sset ) ; $i++ )
$wsum = $wsum + $weights [ $sset [ $i - 1 ] ] [ $sset [ $i ] ] ;
$deposit [ $entry ] = $wsum ;
}
}
}
# prepare the comparison buckets
$buckets = array ( ) ;
for ( $i = 0 ; $i < $count ; $i++ )
$buckets [ $i ] = array ( ) ;
# translate the deposited extensions into the buckets
foreach ( $deposit as $key => $val ) {
preg_match_all ( '/(\d+)/' , $key , $matches ) ;
$items = $matches [ 1 ] ;
$init = array_shift ( $items ) ;
sort ( $items ) ;
$midstr = arr2str ( $items ) ;
if ( ! isset ( $buckets [ $init ] [ $midstr ] ) )
$buckets [ $init ] [ $midstr ] = array ( ) ;
$entry = "$key:$val" ;
array_push ( $buckets [ $init ] [ $midstr ] , $entry ) ;
}
# perform the comparison reduction on each bucket of items
$preiteration = array ( ) ;
foreach ( $buckets as $init => $one ) {
foreach ( $one as $midstr => $items ) {
$maxc = "" ;
$maxw = 0 ;
foreach ( $items as $item ) {
list ( $chain , $weight ) = preg_split ( '/:/' , $item ) ;
if ( $weight >= $maxw ) {
$maxc = $chain ;
$maxw = $weight ;
}
}
$preiteration [ $maxc ] = $maxw ;
}
}
return $preiteration ;
}
# identify the number of elements n (stored in "$count")
$count = 11 ;
# acquire relational data from your source
$weights = acquire ( "11.txt" , $count ) ;
$iteration = zerolist ( $weights , $count ) ;
$iters = abs ( ceil ( log ( $count , 2 ) ) ) ;
$iters = $count - 2 ;
foreach ( $iteration as $key => $val ) {
echo "$key: $val
\n" ;
}
for ( $i = 0 ; $i < $iters ; $i++ ) {
$iteration = iterate ( $iteration , $weights , $count ) ;
foreach ( $iteration as $key => $val ) {
# comment out the following line to eliminate verbosity
echo "$key: $val
\n" ;
}
}
# append and then finish the circle for all results
$buckets = array ( ) ;
foreach ( $iteration as $item => $weight ) {
# get the first item
preg_match ( '/^(\d+)/' , $item , $matches ) ;
$first = $matches [ 1 ] ;
preg_match ( '/(\d+)$/' , $item , $matches ) ;
$last = $matches [ 1 ] ;
$entry = $item . '-' . $first ;
$w = $weight + $weights [ $last ] [ $first ] ;
if ( ! isset ( $buckets [ $first ] ) )
$buckets [ $first ] = array ( ) ;
$newdrop = "$entry:$w" ;
array_push ( $buckets [ $first ] , $newdrop ) ;
}
$results = array ( ) ;
foreach ( $buckets as $first => $items ) {
$maxc = "" ;
$maxw = 0 ;
foreach ( $items as $item ) {
list ( $chain , $weight ) = preg_split ( '/:/' , $item ) ;
if ( $weight >= $maxw ) {
$maxc = $chain ;
$maxw = $weight ;
}
}
$results [ $maxc ] = $maxw ;
}
reset ( $results ) ;
$chain = key ( $results ) ;
$weight = $results [ $chain ] ;
echo "sequence: $chain. weight sum: $weight.
\n" ;
/*
# translate back into the return array with extended values
$retval = array ( ) ;
foreach ( $preiteration as $key => $val ) {
preg_match_all ( '/(\d+)/' , $key , $matches ) ;
$items = $matches [ 1 ] ;
$a = array_pop ( $items ) ;
$p = implode ( '-' , $items ) ;
$w = $val ;
$narr = array ( 'p' => $p , 'a' => $a , 'w' => $w ) ;
array_push ( $retval , $narr ) ;
}
return $retval ;
*/
?>