setpartition.cc,v

这是P2P流媒体方案－NICE的实现源码

head	1.1;
access;
symbols;
locks; strict;
comment	@// @;


1.1
date	2002.07.02.19.30.23;	author rbraud;	state Exp;
branches;
next	;


desc
@@


1.1
log
@Initial revision
@
text
@/*
 * File: setpartition.cc
 * Author: Suman Banerjee <suman@@cs.umd.edu>
 * Date: 15th February, 2002
 * Terms: GPL
 *
 * NICE Application Layer Multicast
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "setpartition.h"
#include "common.h"

#undef LOG_SET_PARTITION

/* There are num elements with the cost matrix specified.
 * This splits the element set into two partitions. The
 * min size for each of the partitions is specified.
 */
void two_partition (int num, double * cost, int min_size, \
		    int * & final_l1, int & final_l1_count, int & c1, \
		    int * & final_l2, int & final_l2_count, int & c2) {

#ifdef LOG_SET_PARTITION
  printf ("Beginning set partition\n");
  fflush(stdout);
#endif

  assert ( min_size <= (num / 2) );
  int * res_l1 = NULL;
  int * res_l2 = NULL;
  int res_l1_count = 0;
  int res_l2_count = 0;
  int * l1 = (int *) safe_malloc (sizeof(int) * num);
  int * l2 = (int *) safe_malloc (sizeof(int) * num);
  int l1_count, l2_count;
  double actual_partition_max_radius = -1.0;
  
  for (int i = 0; i < num; i++) {
    for (int j = i+1; j < num; j++) {

      double this_l1_max_dist, this_l2_max_dist;
      two_partition_given_centers(num,cost,i,j,min_size,l1,l1_count,l2,l2_count,this_l1_max_dist,this_l2_max_dist);

      long this_l1_max_dist_long = USECS(this_l1_max_dist);
      long this_l2_max_dist_long = USECS(this_l2_max_dist);

      // double this_partition_max_radius = (this_l1_max_dist > this_l2_max_dist) ? this_l1_max_dist : this_l2_max_dist;
      long this_partition_max_radius_long = (this_l1_max_dist_long > this_l2_max_dist_long) ? this_l1_max_dist_long : this_l2_max_dist_long;

      long actual_partition_max_radius_long = USECS(actual_partition_max_radius);

      if ( (actual_partition_max_radius < 0.0) || (this_partition_max_radius_long < actual_partition_max_radius_long) ) {

        if (res_l1 != NULL) {
          free(res_l1);
        }
        if (res_l2 != NULL) {
          free(res_l2);
        }
        res_l1 = l1;
        res_l2 = l2;
        res_l1_count = l1_count;
        res_l2_count = l2_count;
	c1 = i;
	c2 = j;
        l1 = (int *) safe_malloc (sizeof(int) * num);
        l2 = (int *) safe_malloc (sizeof(int) * num);
      }
    }
  }
  free(l1);
  free(l2);

  final_l1 = res_l1;
  final_l2 = res_l2;
  final_l1_count = res_l1_count;
  final_l2_count = res_l2_count;

#ifdef LOG_SET_PARTITION
  printf ("Finishing set partition\n");
  fflush(stdout);
#endif

  return;
}

void two_partition_given_centers (int num, double * cost, int c1, int c2, \
				 int min_size, int * l1, int& l1_count, \
				 int * l2, int& l2_count, \
				 double& max_dist_l1, double& max_dist_l2 ) {

  l1_count = 0;
  l2_count = 0;
  max_dist_l1 = -1.0;
  max_dist_l2 = -1.0;

  for (int i = 0; i < num; i++) {

    if ( (i != c1) && (i != c2) ) {

      long cost1_long = USECS(cost[i*num+c1]);
      long cost2_long = USECS(cost[i*num+c2]);

      if (cost1_long < cost2_long)
        add_to_list(l1,l1_count,i,cost[i*num+c1],max_dist_l1);
      else
        add_to_list(l2,l2_count,i,cost[i*num+c2],max_dist_l2);
    }
  }

  /* If we dont meet the size bounds, need to shift things */
  if ( (l1_count < (min_size-1)) || (l2_count < (min_size-1)) ) {

    if (l1_count >= (min_size-1)) {
      shift_from_larger_to_smaller_list(l1,l1_count,l2,l2_count,c1,min_size-1-l2_count,cost,num);
    }
    else {
      shift_from_larger_to_smaller_list(l2,l2_count,l1,l1_count,c2,min_size-1-l1_count,cost,num);
    }
  }
  l1[l1_count++] = c1;
  l2[l2_count++] = c2;
    
  return;
}

void shift_from_larger_to_smaller_list (int * larger_l, int& larger_l_count, \
					int * smaller_l, int& smaller_l_count, \
					int larger_center, \
					int transfer_count, \
					double * cost, int row_size) {

  assert (transfer_count <= larger_l_count);
  bubble_sort_list_based_on_cost_with_element(larger_l,larger_l_count,larger_center,cost,row_size);
  for (int k = 0; k < transfer_count; k++) {
    smaller_l[k + smaller_l_count] = larger_l[k];
  }
  for (int k = transfer_count; k < larger_l_count; k++) {
    larger_l[k - transfer_count] = larger_l[k];
  }

  larger_l_count -= transfer_count;
  smaller_l_count += transfer_count;
  return;
}

void add_to_list (int * l, int & count, int elem, double elem_cost, double & max_dist_l) {

  l[count] = elem;
  count ++;
  if ( (max_dist_l < 0.0) || (elem_cost > max_dist_l) )
    max_dist_l = elem_cost;
  return;
}

/* Add this element to the list, but keeps the list sorted */
void add_to_sorted_list (int * l, int & count, int elem, double elem_cost, double & max_dist_l) {

  int i = 0;
  for (i = 0; i < count; i++)
    if (l[i] > elem_cost)
      break;

  for (int j = count-1; j >= i; j--)
    l[j+1] = l[j];

  l[i] = elem;
  count ++;
  if ( (max_dist_l < 0.0) || (elem_cost > max_dist_l) )
    max_dist_l = elem_cost;
  return;
}

void bubble_sort_list_based_on_cost_with_element (int * l, int count, int elem, double * cost, int row_size) {

  for (int i = 0; i < count; i++) {
    for (int j =  i+1; j < count; j++) {
      if (cost[elem*row_size+l[i]] > cost[elem*row_size+l[j]]) { // swap
        int temp = l[i];
        l[i] = l[j];
        l[j] = temp;
      }
    }
  }
  return;
}

@