# Dilworth Decomposition in C++ using the LEDA Graph library

## 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 , the following notations were used by Vincent Bouchitté and are usually used in lattices and orders algebra:

• is the set of successors of in the graph ;

• is the set of predecessors of in the graph ;

• . are called endpoints ;

• a path in ;

• . and are said to be parallel ;

• is the set of 's ascendants including . In other terms, a node is an ascendant of a node iff or if there exists a path from to ;

• is the set of 's descendants including . In other terms, a node is a descendant of a node iff or if there exists a path from to ;

• Two edges are adjacent iff they share an endpoint;

• is an antichain iff all nodes belonging to are parallel. Formally, is an antichain in iff ;

• is a maximal antichain iff its size in terms of number of nodes is maximal. Formally, is a maximal antichain ;

• The size of a maximal antichain is called the width of the DAG and is noted .

• is a chain iff all nodes belonging to are not parallel. Simply, all nodes of a chain belongs to the same path in the DAG. Formally, is a chain in iff ;

• is a chain partition of if any is a chain and: .

• A chain decomposition is minimal if its indice is minimal. Such minimal indice is noted .

• In 1950, Dilworth proved that , and each maximal antichain is equivalent to a minimal chain decomposition (and vice-versa).

## 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"))) {
}
else if (filename.contains(LEDA::string(".gml"))) {
}
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;
}