diff options
Diffstat (limited to 'src/intersim/maxsize.cpp')
| -rw-r--r-- | src/intersim/maxsize.cpp | 181 |
1 files changed, 181 insertions, 0 deletions
diff --git a/src/intersim/maxsize.cpp b/src/intersim/maxsize.cpp new file mode 100644 index 0000000..3d1349a --- /dev/null +++ b/src/intersim/maxsize.cpp @@ -0,0 +1,181 @@ +#include "booksim.hpp"
+#include <iostream>
+
+#include "maxsize.hpp"
+
+// shortest augmenting path:
+//
+// for all unmatched left nodes,
+// push node onto work stack
+// end
+//
+// for all j,
+// from[j] = undefined
+// end
+//
+// do,
+//
+// while( !stack.empty ),
+//
+// nl = stack.pop
+// for each edge (nl,j),
+// if ( ( lmatch[nl] != j ) && ( from[j] == undefined ) ),
+// if ( rmatch[j] == undefined ),
+// stop // augmenting path found
+// else
+// from[j] = nl
+// newstack.push( rmatch[j] )
+// end
+// end
+// end
+// end
+//
+// stack = newstack
+// end
+//
+
+//#define DEBUG_MAXSIZE
+//#define PRINT_MATCHING
+
+MaxSizeMatch::MaxSizeMatch( const Configuration &config,
+ Module *parent, const string& name,
+ int inputs, int outputs ) :
+DenseAllocator( config, parent, name, inputs, outputs )
+{
+ _from = new int [_outputs];
+ _s = new int [_inputs];
+ _ns = new int [_inputs];
+}
+
+MaxSizeMatch::~MaxSizeMatch( )
+{
+ delete [] _from;
+ delete [] _s;
+ delete [] _ns;
+}
+
+void MaxSizeMatch::Allocate( )
+{
+ // clear matching
+ for ( int i = 0; i < _inputs; ++i ) {
+ _inmatch[i] = -1;
+ }
+ for ( int j = 0; j < _outputs; ++j ) {
+ _outmatch[j] = -1;
+ }
+
+ // augment as many times as possible
+ // (this is an O(N^3) maximum-size matching algorithm)
+ while ( _ShortestAugmenting( ) );
+}
+
+
+bool MaxSizeMatch::_ShortestAugmenting( )
+{
+ int i, j, jn;
+ int slen, nslen;
+ int *t;
+
+ slen = 0;
+ for ( i = 0; i < _inputs; ++i ) {
+ if ( _inmatch[i] == -1 ) { // start with unmatched left nodes
+ _s[slen] = i;
+ slen++;
+ }
+ _from[i] = -1;
+ }
+
+ for ( int iter = 0; iter < _inputs; iter++ ) {
+ nslen = 0;
+
+ for ( int e = 0; e < slen; ++e ) {
+ i = _s[e];
+
+ for ( j = 0; j < _outputs; ++j ) {
+ if ( ( _request[i][j].label != -1 ) && // edge (i,j) exists
+ ( _inmatch[i] != j ) && // (i,j) is not contained in the current matching
+ ( _from[j] == -1 ) ) { // no shorter path to j exists
+
+ _from[j] = i; // how did we get to j?
+
+#ifdef DEBUG_MAXSIZE
+ cout << " got to " << j << " from " << i << endl;
+#endif
+ if ( _outmatch[j] == -1 ) { // j is unmatched -- augmenting path found
+ goto found_augmenting;
+ } else { // j is matched
+ _ns[nslen] = _outmatch[j]; // add the destination of this edge to the leaf nodes
+ nslen++;
+
+#ifdef DEBUG_MAXSIZE
+ cout << " adding " << _outmatch[j] << endl;
+#endif
+ }
+ }
+ }
+ }
+
+ // no augmenting path found yet, swap stacks
+ t = _s;
+ _s = _ns;
+ _ns = t;
+ slen = nslen;
+ }
+
+ return false; // no augmenting paths
+
+ found_augmenting:
+
+ // the augmenting path ends at node j on the right
+
+#ifdef DEBUG_MAXSIZE
+ cout << "Found path: " << j << "c <- ";
+#endif
+
+ i = _from[j];
+ _outmatch[j] = i;
+
+#ifdef DEBUG_MAXSIZE
+ cout << i;
+#endif
+
+ while ( _inmatch[i] != -1 ) { // loop until the end of the path
+ jn = _inmatch[i]; // remove previous edge (i,jn) and add (i,j)
+ _inmatch[i] = j;
+
+#ifdef DEBUG_MAXSIZE
+ cout << " <- " << j << "c <- ";
+#endif
+
+ j = jn; // add edge from (jn,in)
+ i = _from[j];
+ _outmatch[j] = i;
+
+#ifdef DEBUG_MAXSIZE
+ cout << i;
+#endif
+ }
+
+#ifdef DEBUG_MAXSIZE
+ cout << endl;
+#endif
+
+ _inmatch[i] = j;
+
+#ifdef PRINT_MATCHING
+ cout << "left matching: ";
+
+ for ( i = 0; i < _inputs; i++ ) {
+ cout << _inmatch[i] << " ";
+ }
+ cout << endl;
+
+ cout << "right matching: ";
+ for ( i = 0; i < _outputs; i++ ) {
+ cout << _outmatch[i] << " ";
+ }
+ cout << endl;
+#endif
+
+ return true;
+}
|