cyclesfinder.h

clustering for ns-2 simulation

/**
 * Copyright (c) 2006 Michele Mastrogiovanni.
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 *
 */
 
#ifndef _CYCLESFINDER_H_
#define _CYCLESFINDER_H_

#include <vector>
#include "clustering-header.h"

/*
  Definizione di Path: 
*/
typedef vector<NodeAddress> Path;

// Confronta fra due percorsi:
// Il percorso a e' minore di b se:
//      1) Il percorso a e' piu' corto di b oppure
//      2) I due percorsi sono diversi e a e'lessicograficamente minore.
//
struct PathsCompare : public binary_function<Path,Path,bool> 
{
    bool operator()(const Path & a, const Path & b) const {
	
        if (a.size() != b.size())
            return a.size() < b.size();
        
        Path::const_reverse_iterator ri_a = a.rbegin();
        Path::const_reverse_iterator ri_b = b.rbegin();

        for (ri_a = a.rbegin(); ri_a != a.rend(); ri_a++) {
            if ((*ri_a) != (*ri_b))
                break;
            ri_b++;
        }
        if (ri_a == a.rend())
            return false;
        
        return (*ri_a) < (*ri_b);
        
    }
};

/*
    Definizione di insieme di percorsi
*/
typedef vector<Path> Paths;

// Definizione di cicli.
//
typedef set<Path, PathsCompare> Cycles;

//
//
class CyclesFinder {

    public:
        CyclesFinder(Paths paths);
        
        void find_cycle(int MAX, Cycles & cycles);
        void print_paths(Paths & t);
        void print_path(const Path & t);
    
    protected:

        void print_ciclo(int x, int y, int x_, int y_, Cycles & cycles);
        void coppie (int x, int y, Cycles & cycles);
        void calculate_next();
        bool isPathEqual(Path & a, Path & b);
                
    protected:
        int W;
        int H;
        Paths table;
        Paths next;
        bool calculated;

};

#endif