diff options
Diffstat (limited to 'src/intersim2/.svn/pristine/90')
| -rw-r--r-- | src/intersim2/.svn/pristine/90/90e277f393024f15eeb6e024bd34ac972b818aaf.svn-base | 210 | ||||
| -rw-r--r-- | src/intersim2/.svn/pristine/90/90f780ee11bbe517547a3648019db3592a5e7675.svn-base | 88 |
2 files changed, 298 insertions, 0 deletions
diff --git a/src/intersim2/.svn/pristine/90/90e277f393024f15eeb6e024bd34ac972b818aaf.svn-base b/src/intersim2/.svn/pristine/90/90e277f393024f15eeb6e024bd34ac972b818aaf.svn-base new file mode 100644 index 0000000..0fda1c1 --- /dev/null +++ b/src/intersim2/.svn/pristine/90/90e277f393024f15eeb6e024bd34ac972b818aaf.svn-base @@ -0,0 +1,210 @@ +// $Id$ + +/* + Copyright (c) 2007-2012, Trustees of The Leland Stanford Junior University + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + Neither the name of the Stanford University nor the names of its contributors + may be used to endorse or promote products derived from this software without + specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + POSSIBILITY OF SUCH DAMAGE. +*/ + +#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( Module *parent, const string& name, + int inputs, int outputs ) : + DenseAllocator( parent, name, inputs, outputs ) +{ + _from.resize(outputs); + _s = new int [inputs]; + _ns = new int [inputs]; + _prio = 0; +} + +MaxSizeMatch::~MaxSizeMatch( ) +{ + delete [] _s; + delete [] _ns; +} + +void MaxSizeMatch::Allocate( ) +{ + + // augment as many times as possible + // (this is an O(N^3) maximum-size matching algorithm) + while( _ShortestAugmenting( ) ); + + // next time, start at next input to ensure fairness + _prio = (_prio + 1) % _inputs; +} + + +bool MaxSizeMatch::_ShortestAugmenting( ) +{ + int i, j, jn; + int slen, nslen; + + // start with empty stack + slen = 0; + + // push all unassigned inputs to the stack + for ( i = 0; i < _inputs; ++i ) { + j = (i + _prio) % _inputs; + if ( _inmatch[j] == -1 ) { // start with unmatched left nodes + _s[slen++] = j; + } + } + + _from.assign(_inputs, -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 + int * 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; +} diff --git a/src/intersim2/.svn/pristine/90/90f780ee11bbe517547a3648019db3592a5e7675.svn-base b/src/intersim2/.svn/pristine/90/90f780ee11bbe517547a3648019db3592a5e7675.svn-base new file mode 100644 index 0000000..8cdb445 --- /dev/null +++ b/src/intersim2/.svn/pristine/90/90f780ee11bbe517547a3648019db3592a5e7675.svn-base @@ -0,0 +1,88 @@ +// $Id$ + +/* + Copyright (c) 2007-2012, Trustees of The Leland Stanford Junior University + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + Redistributions in binary form must reproduce the above copyright notice, this + list of conditions and the following disclaimer in the documentation and/or + other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND + ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR + ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON + ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/*module.cpp + * + *The basic class that is extended by all other components of the network + *Provides the basic hierarchy structure and basic fuctions + * + */ + +#include <iostream> +#include <cstdlib> + +#include "booksim.hpp" +#include "module.hpp" + +Module::Module( Module *parent, const string& name ) +{ + _name = name; + + if ( parent ) { + parent->_AddChild( this ); + _fullname = parent->_fullname + "/" + name; + } else { + _fullname = name; + } +} + +void Module::_AddChild( Module *child ) +{ + _children.push_back( child ); +} + +void Module::DisplayHierarchy( int level, ostream & os ) const +{ + vector<Module *>::const_iterator mod_iter; + + for ( int l = 0; l < level; l++ ) { + os << " "; + } + + os << _name << endl; + + for ( mod_iter = _children.begin( ); + mod_iter != _children.end( ); mod_iter++ ) { + (*mod_iter)->DisplayHierarchy( level + 1 ); + } +} + +void Module::Error( const string& msg ) const +{ + cout << "Error in " << _fullname << " : " << msg << endl; + exit( -1 ); +} + +void Module::Debug( const string& msg ) const +{ + cout << "Debug (" << _fullname << ") : " << msg << endl; +} + +void Module::Display( ostream & os ) const +{ + os << "Display method not implemented for " << _fullname << endl; +} |