A C++ implementation of a O(n log n) algorithm computing a maximal stable set of an interval graph.

1

Author:
: Sid-Ahmed-Ali Touati
This software implements the algorithm published in U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810.

Citation of the authors: "Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We exhibit a O (n log n) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling".

And I add that this algorithm solves also some problems in register allocation inside compilers.

Dowload the sources under GPL licence .

Sample Example

This algorithm is implemented in the main function (see header.h section)

int MAXIMAL_STABLE_SET_IG (const std::list< INTERVAL > & intervals, int * colour)

Below a example showing how to use this function.

#include "interval.h"

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[])
{
  std::list<INTERVAL> intervals;
        std::list<INTERVAL>::iterator it;       
  int alpha, i, colour[200];
 //  example of the paper: U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the  channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810
  intervals.push_back(INTERVAL(1,4));
  intervals.push_back(INTERVAL(2,8));
  intervals.push_back(INTERVAL(3,6));
  intervals.push_back(INTERVAL(5,10));
  intervals.push_back(INTERVAL(7,13));
  intervals.push_back(INTERVAL(9,11));
  intervals.push_back(INTERVAL(12,14));
  alpha=MAXIMAL_STABLE_SET_IG(intervals, &colour[0]);
  cout<<"The First example is the one explained in the paper : U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the  channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810.\n";
  cout<<"The minimal number of colours is "<<alpha<<endl;
  it=intervals.begin();
  for(i=0;i<intervals.size();i++){
        cout<<"Interval number "<<i<<" : "<<*it<<endl;
        cout<<"Coloured with colour number "<<colour[i]<<endl;
        it++;
  }

  cout<<"-----------------------------------------\n";
  cout<<"Now another example. We add new intervals\n";
  cout<<"-----------------------------------------\n";
  // another tricky example
  intervals.push_back(INTERVAL(1,9));
  intervals.push_back(INTERVAL(6,8));
  intervals.push_back(INTERVAL(8,10));
  intervals.push_back(INTERVAL(10,11));
  intervals.push_back(INTERVAL(5,10));
  intervals.push_back(INTERVAL(9,11));
  intervals.push_back(INTERVAL(14,15));

  alpha=MAXIMAL_STABLE_SET_IG(intervals, &colour[0]);
        it=intervals.begin();
  cout<<"Now, the minimal number of colours is "<<alpha<<endl;
  for(i=0;i<intervals.size();i++){
        cout<<"Interval number "<<i<<" : "<<*it<<endl;
        cout<<"Coloured with colour number "<<colour[i]<<endl;
         it++;
  }
  return EXIT_SUCCESS;
}

September 2007, by Sid-Ahmed-Ali Touati (Copyright University of Versailles)