diff options
Diffstat (limited to 'src/intersim/maxsize.cpp')
| -rw-r--r-- | src/intersim/maxsize.cpp | 181 |
1 files changed, 0 insertions, 181 deletions
diff --git a/src/intersim/maxsize.cpp b/src/intersim/maxsize.cpp deleted file mode 100644 index 3d1349a..0000000 --- a/src/intersim/maxsize.cpp +++ /dev/null @@ -1,181 +0,0 @@ -#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;
-}
|