interval.h File Reference

This is a header file of the classes and functions implementing an O(n log n) algorithm computing a maximal stable set in an interval graph. In fact, our implementation takes a set of intervals, not an interval graph. More...

#include <iostream>
#include <list>

Classes

class  ENDPOINT
class  INTERVAL
 This class represents a closed interval object. An interval is a pair of double values [x,y], representing all values (of type double) starting from x to y. We name them the left and the right of the interval. Also, we ca associate a cost (weight) to an interval. More...
struct  SortTable
class  INVALID_INTERVAL

Functions

bool operator== (const ENDPOINT &x, const ENDPOINT &y)
bool operator<= (const ENDPOINT &x, const ENDPOINT &y)
bool operator< (const ENDPOINT &x, const ENDPOINT &y)
bool operator> (const ENDPOINT &x, const ENDPOINT &y)
bool operator>= (const ENDPOINT &x, const ENDPOINT &y)
bool operator== (const INTERVAL &I, const INTERVAL &J)
bool operator< (const INTERVAL &I, const INTERVAL &J)
bool operator> (const INTERVAL &I, const INTERVAL &J)
int lexicographic_compare (const ENDPOINT &, const ENDPOINT &)
int MAXIMAL_STABLE_SET_IG (const std::list< INTERVAL > &intervals, int *colour)

Detailed Description

This is a header file of the classes and functions implementing an O(n log n) algorithm computing a maximal stable set in an interval graph. In fact, our implementation takes a set of intervals, not an interval graph.

Function Documentation

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

This function implements the algorithm described 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

It computes the minimal number of colour for a set of intervals. Two interfering intervals should not have the same colour. The algorithms runs in $ O(n \times \log n) $.

Parameters:
[in] intervals A list containing the intervals to be processed
[out] colour $ colour[i] $ is the colour of the interval number i. Two interfering intervals should not have the same colour. $ \forall I,J: I \cap J \neq \phi \Longrightarrow colour[I] \neq colour[J] $.
Returns:
$ \alpha $ the minimal number of colours. Colours are numbered from 0 to $ \alpha-1 $. This function returns -1 if error.
Remarks:
The weight of the intervals are useless for this algorithm.
Precondition:
the size of the coulour vector should at least equal to the number of input intervals.

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