Dilworth Decomposition in C++ using the LEDA Graph library

version 1.0

Author:
: Sid-Ahmed-Ali Touati (in memory of Vincent Bouchitté)

Who was Vincent Bouchitté ?

Vincent Bouchitté was one of my former professors at Ecole Normale Supérieure de Lyon (France). He taught me deep and excellent fundamental results of graph theory, lattices and orders. Thanks to his courses, we were able to produce fundamental results on code optimisation published in the following article:

Sid-Ahmed-Ali Touati. Register Saturation in Instruction Level Parallelism. International Journal of Parallel Programming, Springer-Verlag, Volume 33, Issue 4, August 2005. 57 pages.

Vincent Bouchitté was member of the LIP laboratory at Ecole Normale Supérieure de Lyon. He died after a long disease. He was 47 years old. Very discrete, he was very appreciated by all his colleagues and students. He leaves major results in graph theory and advised beautiful Ph.D. theses. He was buried at Salindre in France, his birthplace, on March 15th, 2005.

In memory of him, I implemented Dilworth decomposition. Vincent Bouchitté taught us beautiful algorithms and formal proofs on the subject.

Quick Recall of Basic Notions and Notations on Graphs and Orders

An order is simply a directed acyclic graph (DAG). Given a DAG $ G=(V,E) $, the following notations were used by Vincent Bouchitté and are usually used in lattices and orders algebra:

Why do we choose LEDA Graph Library ?

LEDA is a famous C++ graphs and general data structures library. We have used it since many years, and we can safely say that it is better than other existing C++ graph and data structures libraries that we experimented (BOOST, STL, etc.). Initially, LEDA was an academic project from Germany. LEDA sources was distributed for free under a specific academic license untill version 4.2 (with g++2.95). Then, in 2001 (when g++ changed to version 3), LEDA team changed the free academic license into a low-priced academic license. LEDA is a high level library greatly helping to implement complex algorithms in a quick, robust and modular way. According to our deep experience, a C++ code using LEDA looks like a high level algorithm, allowing to easily debug it without suffering from programming details. Furthermore, LEDA offers the largest set of implementation of well known algorithms in graph theory and data structures.

Code Example for Usage

int main(int argc, char *argv[])
{
        graph G;
        LEDA::string filename;
        set<node> MA; //maximal antichain
        node_array<int> C; //indices of chains
        node_list nl;
        h_array<int,node_list*> chain(nil);
        int i,status;
        int size_ma, // size of a maximal antichain
                size_mc; // size of a minimal chain decomposition
        node u;
        if(argc!=2){
                cerr << argv[0] << ": Dilworth decomposition." << endl;
                cerr << "Usage:"<<argv[0] << " graph_filename" << endl;
                cerr << "The filename extension should be .gw for a graph in leda/gw format, or in .gml for a graph in GML format."<< endl;
                return EXIT_FAILURE;
        }

        filename=LEDA::string(argv[1]);
        if (filename.contains(LEDA::string(".gw"))) {
                cout<<"Reading GW" <<filename<<endl;
                status=G.read(filename);
        }
        else if (filename.contains(LEDA::string(".gml"))) {
                cout<<"Reading GML "<< filename<<endl;
                status=G.read_gml(filename);
        }
        else {
                cerr << "Usage:"<<argv[0] << " graph_filename" << endl;
                cerr << "The filename extension should be .gw for a graph in leda/gw format, or in .gml for a graph in GML format."<< endl;
                return EXIT_FAILURE;
        }

        switch(status){
        case 0: 
        case 2: break;
        case 1: cerr<< filename << " does not exist."<<endl; break;
        case 3: cerr<<filename <<" does not contain a graph"<<endl; break;
        default: return EXIT_FAILURE;
        }
        
        size_mc=MINIMAL_CHAIN(G, C);
        cout<<"Minimal Chain Decomposition"<<endl;
        cout<<"---------------------------"<<endl;
        cout<<"There are "<<size_mc<<" chains"<<endl;
        forall_nodes(u,G){
                if ((chain[C[u]])==nil){
                        chain[C[u]]=new node_list;
                }
                (chain[C[u]])->append(u);
        }
        for(i=0;i<size_mc;i++){
                cout<<"chain "<<i<<": ";
                forall(u, *chain[i]){
                        G.print_node(u);
                }
                cout<<endl;
        }
        
        
        size_ma=MAXIMAL_ANTI_CHAIN(G, MA);
        cout<<"Maximal Antichain"<<endl;
        cout<<"---------------------------"<<endl;
        cout<<"Size of this maximal anctichain : "<<size_ma<<" nodes"<<endl;
        cout<<"Here are all these nodes:"<<endl;
        i=0;
        forall(u, MA){
                cout<<"node "<<i<<": ";
                G.print_node(u);
                cout<<endl;
                i++;
        }
        return EXIT_SUCCESS;
}

Download the Sources

This implementation has been done by Sid-Ahmed-Ali Touati and distributed under GPL. The first version is available here .
August 2007, by Sid-Ahmed-Ali Touati (Copyright INRIA and University of Versailles)