cyclesfinder.cc

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.
 *
 */
 
#include "CyclesFinder.h"

#include <algorithm>

CyclesFinder::CyclesFinder(Paths paths) { 

    table = paths;

    H = table.size();
    W = table[0].size();
            
    next.resize(H + 1);
    for (int y = 0; y <= H; y++)
        next[y].resize(W);
                
    calculated = false;
}
        
void
CyclesFinder::find_cycle(int k, Cycles & cycles) {
    
    if (!calculated) {
        sort(table.begin(), table.end(), PathsCompare());    
        calculate_next();
        calculated = true;
    }
    
    if (k % 2 == 0)
        coppie(k / 2, k / 2, cycles);
    else
        coppie(k / 2, k / 2 + 1, cycles);
    
}

/*
    Nota: le coppie (1,2) e (2,1) sono differenti a meno che x = y.
    in quel caso la coppia ripetuta va eliminata.
    Si elimina quella che ha il primo valore piu' grande.
*/
void 
CyclesFinder::print_ciclo(int x, int y, int x_, int y_, Cycles & cycles) 
{
    set<NodeAddress> s;
    int i;
    for (i = 0; i < x; i++)
        s.insert(table[x_][W-i-1]);        
    for (i = 1; i < y; i++)
        s.insert(table[y_][W-y+i]);
    if (s.size() != (unsigned int)(x + y - 1))
        return;

    Path v(s.size());

    for (i = 0; i < x; i++) {
        v[i] = table[x_][W-i-1];
    }
    for (i = 1; i < y; i++) {
        v[x + i - 1] = table[y_][W-y+i];
    }

    // print_path(v);

    Cycles::iterator i_;
    for (i_ = cycles.begin(); i_ != cycles.end(); i_++) {
        Path & pp = (Path&)(*i_);
        if (isPathEqual(pp, v))
            break;
    }
    if (i_ != cycles.end())
        return;
    cycles.insert(v);
        
}
            
void 
CyclesFinder::coppie (int x, int y, Cycles & cycles) 
{
    //printf("Cicli lunghi %d [x = %d, y = %d]\n", x+y, x, y);
    for (int x_ = 0; next[x_][W-x] != -1; x_ = next[x_][W-x])
        for (int y_ = 0; next[y_][W-y] != -1; y_ = next[y_][W-y])
            if (x_ != y_)
                if (table[x_][W-x] == table[y_][W-y]) {
                    if (table[y_][W-x] == table[x_][W-y]) {
                        if (x_ > y_)
                            print_ciclo(x, y, x_, y_, cycles);
                    }
                    else
                        print_ciclo(x, y, x_, y_, cycles);
                }
}

void
CyclesFinder::calculate_next() 
{            
    next.resize(next.size() + 1);
    next[H].resize(W);
    
    for (int x = 0; x < W; x++)
        next[0][x] = 0;

    for (int y = 1; y < H; y++) {
        
        int x;
        for (x = 0; (x < W) && (table[y][W-x-1] == table[y-1][W-x-1]); x++)
            next[y][W-x-1] = next[y-1][W-x-1];
        for (int tmp = 0; tmp < W-x; tmp++) {
            next[next[y-1][tmp]][tmp] = y;
            next[y][tmp] = y;
        }

    }
    
    for (int x = 0; x < W; x++) {
        next[next[H-1][x]][x] = H;
        next[H][x] = -1;
    }

}

void
CyclesFinder::print_paths(Paths & t)
{
	/*
    for (unsigned int y = 0; y < t.size(); y++) {
        printf("(%d) ", y);
        for (unsigned int x = 0; x < t[y].size(); x++)
            printf("%d  ", t[y][x]);
        printf("\n");
    }
    // printf("--------------------\n");
	*/
}

void
CyclesFinder::print_path(const Path & t)
{
    for (unsigned int x = 0; x < t.size(); x++)
        printf("%d ", t[x]);
    printf("\n");
    printf("--------------------\n");
}

bool 
CyclesFinder::isPathEqual(Path & a, Path & b) 
{
    unsigned i;
    for (i = 0; i < a.size() && a[i] == b[i]; i++);
    if (i == a.size())
        return true;
    for (i = 0; i < a.size() && a[i] == b[b.size()-i-1]; i++);
    return i == a.size();
}