#!/usr/bin/perl

#
# Take a discrete MTX formatted file, and generate
# a file suitable for use by METIS.
#
# Once generated, the program "kmetis" can be run
# to generate the appropriate partitioning.
#

$infn = shift || die usage();
$outfn = shift || die usage();

open( MTX, "<$infn" ) || die "couldn't open $infn: $!\n";

# grab the header
$line = <MTX>;
chomp $line;
if ( $line ne "%%MatrixMarket matrix coordinate real general" ) {
    print "Error -- unsupported MTX type!\n";
    exit( 0 );
}

$line = <MTX>;
chomp $line;
( $nstates, $tmp, $nnz ) = split( /\s+/, $line );
if ( $nstates ne $tmp ) {
    print "Error -- non-symmetric matrices are not supported!\n";
    exit( 0 );
}

print "[$nstates] [$tmp] [$nnz]\n";

for ( $i=0; $i<$nnz; $i++ ) {
    $line = <MTX>;
    chomp $line;

    ( $row, $col, $val ) = split( /\s+/, $line );
    $row = int( $row )-1;
    $col = int( $col )-1;

    $val = abs( $val );
    $tw = $graph{$row}{$col};
    if ( $val > 0 && $val > $tw ) {
	$graph{$row}{$col} = $val;
	$graph{$col}{$row} = $val;
    }

    if ( $val > $maxval ) {
	$maxval = $val;
    }
}

close( MTX );

print "maxval is $maxval\n";

open( METIS, ">$outfn" ) || die "couldn't open $outfn: $!\n";

#
# Count the number of edges
#

$nedges = 0;
foreach $ss (keys(%graph)) {
    foreach $es (keys(%{$graph{$ss}})) {
	if ( $es != $ss ) {
	    $nedges++;
	}
    }
}
$nedges /= 2;

print METIS "$nstates $nedges 1\n";

#
# Print out the graph in METIS format
#
$i = 0;
foreach $ss ( sort { int($a) <=> int($b) } keys(%graph) ) {
    while ( $i < $ss ) {
	print STDERR "WHOA: unreferenced vertex $i!  Continuing anyway...\n";
	print METIS "\n";
	$i++;
    }

    foreach $es ( sort { int($a)<=>int($b) } keys(%{$graph{$ss}}) ) {
	if ( $es != $ss ) {

	    $w = $graph{$ss}{$es};
	    $w = int( 10000 * ( $w / $maxval ) );
	    if ( $w == 0 ) { $w = 1 };

	    $v = $es+1;
	    print METIS "$v $w ";
	}
    }

    print METIS "\n";
    $i++;
}

close( METIS );

sub usage() {
    print "usage: mdp2metis.pl infn.mtx outfn.metis\n";
}