Rand.H

<Rand.H>=
// File: Rand.H   
// Last Revision: 23-Mar-2001
// Description: functions for the generation of random values.

//
// Note: The two functions myrand() and smyrand() were written by Dell'Amico
// using the portable pseudorandom generator RnG (see below).


#ifndef _RAND_H
#define _RAND_H


 
float myrand();
float smyrand(int seed);
int lprand();
int sprand (int seed);
int dado(int num_facce); // returns an integer in [0, ... , num_facce-1] uniformly at random.

#endif
Defines _RAND_H (links are to index).

Rand.cpp

<Rand.cpp>=
// File: Rand.ccp 
// Last Revision: 23-Mar-2001
// Description: functions for the generation of random values.

//
// Note: The two functions myrand() and smyrand() were written by Dell'Amico
// using the portable pseudorandom generator RnG (see below).


#include "Rand.H"

#define PRANDMAX 1000000000

int dmxa, dmxb, dmxarr[55];


float myrand()
{
  return ((float)lprand()) / PRANDMAX;
}

float smyrand(int seed)
{
  return (float) sprand(seed);
}


int dado(int num_facce)
{
  return (int) (num_facce * myrand());
}


/*
    This file contains a set of c-language functions for generating
    uniform integers.   This is a COMPLETELY PORTABLE generator.
    it will give iDEnTiCAL sequences of random numbers for any
    architecture with at least 30-bit integers, regardless of the
    integer representation, MAXinT value, or roundoff/truncation
    method, etc.
    This Truly Remarkable RnG is described more fully in
    j. Bentley's column, ``The Software Exploratorium ''
    to appear in Unix Review in 1991.
    it is based on one in knuth, Vol 2, Section 3.2.2 (Algorithm A)

    This is a little driver program so you can test the code.
    Giving input parameters: 0 3 1
    should produce
       921674862
       250065336
       377506581
     Giving 1000000 1 2
     should produce
       572653995

       void main()
       {
       int i,j,n,m,seed;
       scanf("%d %d %d",&m,&n,&seed);
       i = sprand(seed);
       for(i=0; i< m;i++)
          j = lprand();
       for (i=0; i< n; i++)
          printf("\n%ld",lprand());
       }
*/


// ---------RnG---------------------
//   Returns long ints from the
//   range 0...PRANDMAX-1

int lprand()
{ 
  dmxa --;
  if (dmxa < 0) dmxa = 54;
  dmxb --;
  if (dmxb < 0) dmxb = 54;
  int t = dmxarr[dmxa] - dmxarr[dmxb];
  return dmxarr[dmxa] = ( (t < 0) ? t + PRANDMAX : t);
}


//-----------RnG initializer------------
//  Call once before using lprand

int sprand (int seed)
{
  int i, ii, last, next;
  dmxarr[0] = last = seed;
  next = 1;
  for (i=1; i< 55; i++ ) {
    ii =  21 * i % 55;
    dmxarr[ii] = next;
    next = last - next;
    if (next < 0)   next += PRANDMAX;
    last = dmxarr[ii];
  }
  dmxa = 0;
  dmxb = 24;
  for(i = 0; i<= 164; i++)
      lprand();
  return seed;
}
Defines dado, dmxa, dmxarr, dmxb, lprand, myrand, PRANDMAX, smyrand, sprand (links are to index).

heap.H

<heap.H>=

#include <string.h>

template<class T> inline bool less(const T& a, const T& b) {
  return (a < b);
}

inline bool less(const char* a, const char* b) {
  return (strcmp(a, b) < 0 ? true : false);
}

template<class T> inline void swap(T& a, T& b) {
  T temp(a);
  a = b;
  b = temp;
}

template<class T> class heap {
private:
  size_t size;
  size_t length;
  T* a;

public:
  heap(size_t initial_size = 10):
    size(initial_size),
    length(0),
    a(new T[initial_size])
  { }

  heap(T array[], size_t nUsed):a(array), size(sizeof(array)), length(nUsed)
  { }
  
  virtual ~heap() {
    delete[] a;
  }
  
  size_t get_used() {
    return length;
  }
  
  bool is_empty() {
    return (length == 0);
  }
  
  T min() {
    if (is_empty()) {
      throw(3);
    }
    return a[0];
  }
  
  void del_min() {
    a[0] = a[length - 1];
    --length;
    movedown(0);
  }

  void movedown(size_t pos) {
    T moving_elem = a[pos];
    size_t iSon, iSonDx;

    for(;;) {
      iSon = (pos << 1) + 1;
      if((iSonDx = iSon + 1) < length && less(a[iSonDx], a[iSon]))
        ++iSon;
      if(iSon < length && less(a[iSon], moving_elem)) {
        a[pos] = a[iSon];
        pos = iSon;
      }
      else {
        a[pos] = moving_elem;
        return;
      }
    }     
  }
  
  void insert(const T& elem) {
    if (length == size) {
      size_t newsize = size * 2 + 1;
      T* b = new T[newsize];
      memcpy((void*)a, (void*)b, sizeof(T)*size);
      swap(a, b);
      size = newsize;
      delete[] b;
    }
    
    a[length] = elem;
    
    moveup(length);
        
    ++length;
  }
  
  void moveup(size_t pos) {
    T moving_elem = a[pos];
    int father;

    while((father = (int)(pos - 1) >> 1) >= 0 && less(moving_elem, a[father])) {    
      a[pos] = a[father];
      pos = father;
    }

    a[pos] = moving_elem;
  }

  void touch(size_t pos) {
    if(pos > 0 && pos < length && less(a[pos], a[(pos - 1) >> 1]))
      moveup(pos);
    else
      movedown(pos);
  }
};

wGraph.H

<wGraph.H>=
/* File: wGraph.H   
 * Last Revision: 2-Apr-2001
 * Description: a data type for weighted graphs.
 *   a weighted graph is a graph G=(V,E) with integer weights on the edges.
 *
 *  author: Romeo Rizzi.
 *
 * Classes declared:   wGraph
 *
 * The class wGraph implements:
 * 1) The data structure storing a given weighted graph,
 * 2) The methods for quering this data structure,
 * 3) The methods to generate "DSJ_U" and "DSJ_G" graphs (see below),
 * 4) The methods for loading the input graph from a file.
 *    (natural extension of DIMACS format, or of JOHNSON format).
 */


#ifndef _W_GRAPH_H
#define _W_GRAPH_H

#include <fstream.h>
#include <math.h>
#include "Rand.H"


#define MAX_NODES 10000
#define MAX_W 100

#define DIMACS 1
#define BINARY_DIMACS 2
#define JOHNSON 3

#define SQR(x) ( (x)*(x) )



enum graph_enum { DSJ_U,  DSJ_G};
/* We generate two kinds of graphs:
 * DSJ_U: Each node is put in the plane and receives two random coordinates.
 *        Two nodes  u and v are then connected by an edge uv, if and only
 *        if their distance does not exceed a given constant.
 *        In case the edge exists, then its weight is choosen uniformly
 *        at random in the interval [1, ..., MAX_W].
* DSJ_G: Random weighted graphs where the probability that there exists
 *        an edge between any two nodes is a constant.
 *        In case the edge exists, then its weight is choosen uniformly
 *        at random in the interval [1, ..., MAX_W].
 *        Thus the expected degree of any vertex is a constant.
 *        Such graphs are indeed characterized by their expected degree.
 *
 * Note: G and U graphs are extensions of the unweighted graphs
 *       produced in the class Graph or as by Dell'Amico - Maffioli.
 *       Starting from a same seed we obtain the same support graph
 *       as in the class Graph or as Dell'Amico - Maffioli.
 */

class Graph {
/* A graph G has n nodes and m edges.
 * We number the nodes of G as: 1, ... ,n.
 *
 * Data Structures: 
 *
 * 1)  THE ADJACENCY MATRIX:  adj_M
 *   adj_M [u][v] == 1  if edge (u,v) exists;  0 otherwise.
 *
 * 2)  THE MATRIX of WEIGHTS:  W
 *   W [u][v] gives the weight of edge (u,v) when such an edge exists.
 *
 * 3)  THE SEQUENCE OF NEIGHBORS:  list_of_neighbors  and  first_nei
 *   list_of_neighbors has the following structure:
 *    <neighbors node 1, neighbors node 2, ... , neighbors node i, ..., neighbors node n>
 *                                               |
 *                                               first_nei[i]
 *    
 *   first_nei[i] = the position in list_of_neighbors[] of the first neighbor of vertex i
 *
 *  The neighbors of vertex i are:
 *               list_of_neighbors[first_nei[i]], list_of_neighbors[first_nei[i]+1],...,list_of_neighbors[first_nei[i+1]-1]).
 *
 *  NOTE:  (a detail in our implementation of list_of_neighbors)
 *   Between the neighbors of node i and the neighbors
 *   of node (i+1) we put a 0 as separetor. 
 *   This trick allows for a faster scan of the neighbors of any node. 
 *   (See procedures  first_neighbor(node u)  and next_neighbor()  below.
 */

  int n_nodes;         // number of nodes.
  int n_edges;         // number of edges. 
  int half_n_nodes;    // half_n_nodes = (n_nodes /2).
  int **adj_M;
  int **W;
  
// SEQUENCE OF NEIGHBORS:
  int *first_nei;
  int *list_of_neighbors;
  int *deg;   // the degree array of nodes. (degree= number of neighbors).
  int max_deg;          //  the maximum degree of a node.
  int *neighbor_pos;   // used to scan the neighbor of a node.
  void Make_Star_DataStructure();
  // derives "list_of_neighbors" and "first_nei" from "adj_M".

// ALLOCATING  THE  ADJACENCY MATRIX  "adj_M".
  void allocate_adj_M();

// ALLOCATING  THE  MATRIX  OF  WEIGHTS  "W".
  void allocate_W();

// STORING RANDOM WEIGHTS INTO MATRIX  "W".
  void random_W();

// GENERATING  "DSJ_U"  and  "DSJ_G"  GRAPHS:
  int iseed;     // seed to random generate graphs DSJ_U or DSJ_G.
  double density, distance;

  void generate_G_graph(double density);
 /* Instantiates a graph of type "G".
  * assumes "adj_M" having been allocated before the call.
  * At termination "adj_M" is the adjacency matrix of the generated graph.
  * However the star data structures are not yet initialized at termination
  * and will be derived from "adj_M" in a second phase by the method "Make_Star_DataStructure()".   */
 
  void generate_U_graph(double distance);
 /* Instantiates a graph of type "U".
  * assumes "adj_M" having been allocated before the call.
  * At termination "adj_M" is the adjacency matrix of the generated graph.
  * However the star data structures are not yet initialized at termination
  * and will be derived from "adj_M" in a second phase by the method "Make_Star_DataStructure()".   */

// LOADING UP A GRAPH FROM A FILE:
  void dimacs_input(const char *file);
  //  inputs a graph in the binary (compressed) dimacs format.
  //  see URL:

  void johnson_input(const char *file);
  //  inputs a graph in the johnson format.
  //  see URL:
  
 public:
        
  Graph (graph_enum gen, int n, double expected_deg, int np, int seed=1);
 /* Generates a graph of type <gen> with <n> nodes.
  * <seed> is the seed to random generate the graph: different calls with
  * the same <seed> (and the same <gen>) produce identical graphs.
  * (in fact, for a given pair (<gen>, <seed>), we produce the same graph
  * as Dell'Amico-Maffioli generator).
  * <expected_deg> is the expected degree of the random graph to be instantiated.
  * <np> is the problem number and is output after the graph
  * has been generated together with other informations about the graph.
  */

  Graph (const int format, const char *file);    
  // Creates a graph by loading it from a <file> in a given <format>. 
  ~Graph();

  void write(const int format, const char *file);
  // saves the graph on a <file> according to the specifyied <format>
  // (useful for conversions, of no use for the search algorithms).

  int n()  const                // returns the number of nodes.
     { return n_nodes; }           
  int m()  const                // returns the number of edges.
     { return n_edges; } 
  int half_n()  const           // returns half the number of nodes.
     { return half_n_nodes; } 

  int edge(int u, int v) const  // returns 1 if nodes u and v are adjacent.
     {return  adj_M [u][v]; }   // returns 0 otherwise.
                                // note: edge(x,x) == 0, no self-connection.  

  int weight(int u, int v) const   // returns the weight of edge uv.
     {return  W [u][v]; }   // the returned value is not defined
                            // if u and v are not adjacent.

  int max_degree()              // returns the maximum degree.
     { return max_deg; }
  int degree(int v)  const      // returns the degree of node v.
     { return deg[v]; }

  int first_neighbor(int v);   // returns 0 if no neighbor. 
  int next_neighbor();   // returns 0 if no next neighbor.

  int size_of_cut(const int *x);  // returns the number of edges whose
                                  // endpoints have different x[] values.
};                     


inline int Graph::next_neighbor()   // returns 0 if no next neighbor. 
      { return *(neighbor_pos ++); }    

inline int Graph::first_neighbor(int v)   { // returns 0 if no neighbor. 
   neighbor_pos = list_of_neighbors + first_nei[v];
   return next_neighbor();
}        

#endif
Defines BINARY_DIMACS, DIMACS, JOHNSON, MAX_NODES, MAX_W, SQR, _W_GRAPH_H (links are to index).

wGraph.cpp

<wGraph.cpp>=
/* File: wGraph.cpp 
 * Last Revision: 2-Apr-2001
 * Description: this file contains the definition of the class wGraph
 * as declared in the file wGraph.H  (see file wGraph.H  to get more insight).
 *
 *  programmer: Romeo Rizzi.
 *
 * Classes defined:   wGraph
 */


#include "wGraph.H"
#include <stdlib.h>



Graph::Graph(graph_enum gen, int num_nodi, double expected_deg,
                                 int np, int seed)
{
  n_nodes = num_nodi;   n_edges = 0;   half_n_nodes = num_nodi/2;

// Initialize the random generator and other parameters to generate the graph. 
  iseed = (long)(n_nodes *131 + expected_deg *101 + np *191 + seed ) % 32767;
  smyrand(iseed);
  density  = (double) expected_deg / (n_nodes - 1) ;
  distance =  sqrt(expected_deg / (n_nodes * 3.141592653589793238));


// Allocate the adjacency matrix "adj_M [u][v]".
  allocate_adj_M(); 

// Allocate the matrix of weights "W [u][v]".
  allocate_W();

// Generate a type (gen) graph. Generate the adjacency matrix adj_M[u][v]. 
  switch (gen) {
        case DSJ_G : generate_G_graph(density);
                     break;
        case DSJ_U : generate_U_graph(distance);
                     break;
  }

  Make_Star_DataStructure();

  cout << "\n\nN= " << n_nodes << " Nu= " << expected_deg 
       << " Tipo grafo= " << gen << " N.lati= " << n_edges 
       << " Seed= " << iseed << " N.problema= " << np << endl;
}

void Graph::allocate_adj_M()
{
  adj_M = new int*[n_nodes] -1;
  for (int i = n_nodes; i; i--)  {
      adj_M[i] = new int[n_nodes] -1;
      for(int j = n_nodes; j; j--)  adj_M[i][j] = 0;
  }
}

void Graph::allocate_W()
{
  W = new int*[n_nodes] -1;
  for (int i = n_nodes; i; i--)  {
      W[i] = new int[n_nodes] -1;
      for(int j = n_nodes; j; j--)  W[i][j] = 0;
  }
}

Graph::~Graph()
{
   for(int i = n_nodes; i; i--) {
     delete [] (adj_M[i] +1);
     delete [] (W +1);
   }
   delete [] (adj_M +1);
   delete [] (W +1);
   delete [] (first_nei +1);
   delete [] (list_of_neighbors +1);
   delete [] (deg +1);
}

void Graph::Make_Star_DataStructure()
{
  deg = new int[n_nodes] -1;   max_deg = 0;
  first_nei = new int[n_nodes] -1;
  list_of_neighbors = new int[2*n_edges + n_nodes] -1;

  int pos = 1;
  for(int i = n_nodes; i; i--) {
     first_nei[i] = pos;
     for(int j = n_nodes; j; j--)   if (adj_M[i][j])  list_of_neighbors[ pos++ ] = j;
     deg[i] = pos - first_nei[i];
     list_of_neighbors[ pos++ ] = 0;
     if( deg[i] > max_deg )    max_deg = deg[i];
  }
}


// generate random weights and store them into matrix W
void Graph::random_W()
{
  for(int i = 1; i < n_nodes; i++) 
     for(int j = n_nodes; j > i; j--)
        if ( adj_M[i][j] )
          W[i][j] = W[j][i] = 1+dado(MAX_W);
}

// generate G graphs
void Graph::generate_G_graph(double density)
{
  for(int i = 1; i < n_nodes; i++) 
     for(int j = n_nodes; j > i; j--)
        if ( myrand() < density ) 
           {  adj_M[i][j] = adj_M[j][i] = 1; n_edges ++;  }
  random_W();
}

// generate U graphs
void Graph::generate_U_graph(double distance)
{ 
  int i, j;
  double *x, *y;
  x = new double[n_nodes +1];  y = new double[n_nodes +1];

  for(i = n_nodes; i; i--) { 
     x[i] = myrand();
     y[i] = myrand();
  }  

  for(i = n_nodes; i; i--) 
     for(j = n_nodes; j > i; j--)
        if(SQR( x[i] -x[j] ) + SQR( y[i] -y[j] ) < SQR(distance)) 
           { adj_M[i][j] = adj_M[j][i] = 1; n_edges ++; }

  delete [] x; delete [] y;

  random_W();
}




void Graph::dimacs_input(const char *file)
{
   ifstream in(file);
   if (!in.good()) {
      cerr << "err: input_graph: Input graph does not exist." << endl;
      exit(1);
   }

   char first_char_of_line, pippo[1000];

   in.get(first_char_of_line);
   while(first_char_of_line != 'p')  {
      in.getline(pippo,1000);
      in.get(first_char_of_line);
   }
   in >> pippo >> n_nodes >> n_edges;  in.getline(pippo,1000);

// Allocate the adjacency matrix "adj_M [u][v]".
   allocate_adj_M();

// Allocate the matrix of weights "W [u][v]".
   allocate_W();

   int i, j, w, num_arcs = n_edges;
   while(num_arcs--) {
      in.get(first_char_of_line);
      while(first_char_of_line != 'e')  {
         in.getline(pippo,1000);
         in.get(first_char_of_line);
      }
      in >> i >> j >> w;  in.getline(pippo,1000);
      adj_M[i][j] = 1;
      adj_M[j][i] = 1;      
      W[i][j] = w;
      W[j][i] = w;      
   }

   half_n_nodes = n_nodes /2;
}


void Graph::johnson_input(const char *file)
{
   ifstream  in(file);
   if (!in.good()) {
      cerr << "err: input_graph: Input graph does not exist." << endl;
      exit(1);
   }

   int max_node = 0, num_arc = 0, node_of_line, degree, neighbor, w;
   char pippo[50];

   do {
     in >> node_of_line >> pippo >> degree;
     if (node_of_line > max_node)  max_node = node_of_line;     
     num_arc += degree;
     for (; degree > 0; degree--)  {
        in >> neighbor;
        if (neighbor > max_node)  max_node = neighbor;             
     } 
   } while(in);

   n_nodes = max_node;  n_edges = num_arc /2;
   half_n_nodes = n_nodes /2;

// Allocate the adjacency matrix "adj_M [u][v]".
   allocate_adj_M();

// Allocate the matrix of weights "W [u][v]".
   allocate_W();

   in.close();
   in.open(file);

   do {
     in >> node_of_line >> pippo >> degree;
     for (; degree > 0; degree--)  {
       in >> neighbor >> w;
        adj_M[node_of_line][neighbor] = 1;
        adj_M[neighbor][node_of_line] = 1;       
        W[node_of_line][neighbor] = w;
        W[neighbor][node_of_line] = w;       
     } 
   } while(in);

   in.close();
}


Graph::Graph(const int format, const char *file) 
{
    switch (format) {
    case DIMACS : dimacs_input(file);  break;
                          
    case JOHNSON : johnson_input(file);  break;
      
    default:
      cerr << "err: input_graph: "
           << "We input only graphs in DIMACS or JOHNSON format." 
           << endl;
      exit(1);
    }

   Make_Star_DataStructure();
}


void Graph::write(const int format, const char *file) 
{
   if (format != DIMACS) {
      cerr << "err: output_graph: "
           << "We output only graphs in DIMACS format." << endl;
      exit(1);
   }

   ofstream  output(file);

   output << "p gp " << n_nodes << " " << n_edges << endl;
   for(int i = 1; i < n_nodes; i++)
      for(int j = i+1; j <= n_nodes; j++)   
         if (adj_M[i][j])   output << "e " << i << " " << j
                                   << " " << W[i][j] << endl;
   output.close();
}





int Graph::size_of_cut(const int *x)   // returns the number of edges whose
                                       // endpoints have different x[] values.
{
   int size = 0;
   for(int node = n_nodes; node; node--)  {
     int x_node = x[node];
     neighbor_pos = list_of_neighbors + first_nei[node];
     while(*neighbor_pos > node)
       if(x[*(neighbor_pos ++)] != x_node)
         ++size;
   }
   return  size;
}
Defines Graph (links are to index).

kruskal.cpp

<kruskal.cpp>=
#include <iostream.h>
#include "wGraph.H"
#include "heap.H"   // lo heap di Lorenzo Dematte 

void usageSyntaxHelp(int argc, char **argv);

struct elem {
  int father;
  int card;
};

class setUnion {
  int n;    // cardinality of the ground set.
  elem * eqClass;

 public:
  setUnion(int n) {
    eqClass = new elem[n+1];
    for(int i = 1; i <= n; i++) {
      eqClass[i].father = i;
      eqClass[i].card = 1;
    }
  }
  ~setUnion() { delete eqClass; }
  void Union(int i, int j) {
    if(eqClass[j].card < eqClass[i].card) {
      int swap = i;
      i = j;
      j = swap;
    }
    eqClass[i].father = j;
    eqClass[j].card = eqClass [j].card + eqClass [i].card ;
    eqClass[i].card = 0;
  }
  int find(int i) {
    while(eqClass[i].card == 0)  i = eqClass[i].father;
    return i;
  }
};

struct edge {
public:
  int node_A;
  int node_B;
  int weight;
};

inline bool less(const edge a, const edge b) {
  return (a.weight < b.weight);
}

int main(int argc, char **argv) {
  usageSyntaxHelp(argc, argv);
   
  Graph* G = new Graph(DIMACS, argv[1]);

  heap<edge> HeapOfEdges;

  for(int v = G->n(); v; v--)
    for(int nei = G->first_neighbor(v);
        nei; nei = G->next_neighbor())
      if(nei > v) {
        edge e;
        e.node_A = v;
        e.node_B = nei;
        e.weight = G->weight(v,nei);
        HeapOfEdges.insert(e);
      }
  
  setUnion components(G->n());

  int cost = 0;
  while (!HeapOfEdges.is_empty()) {
    edge e = HeapOfEdges.min();
    HeapOfEdges.del_min();
    int component_A = components.find(e.node_A);
    int component_B = components.find(e.node_B);
    if(component_A != component_B) {
      cost += e.weight;
      cout << "arco (" << e.node_A << "," << e.node_B << ")" << endl;
      components.Union(component_A, component_B);
    }
  }

  delete G;
  exit(0); 
}


void usageSyntaxHelp(int argc, char **argv) {
   if(argc != 2)  {

      exit(1);
   }
}
Defines main, usageSyntaxHelp (links are to index).