EGlib Home Page

030623

Introduction

This is a joint project of Daniel Espinoza and Marcos Goycoolea where a number of people have contributed, including Renan Garcia, Deniz Dogan, Faram Engineer and Juan Pablo Vielma.

The problem that this project intend to solve (or at least help to solve) is that in any computer implementation there is a lot of overlap in the basic structures and utilities used, such as graph structures, linked lists, hash tables, heaps among others, as well as a number of algorithms wich are very useful as sub-routines for more complicated programs. We have used this library in a number of applied and research projects and have been in development since 2003. I am sure that it is not a perfect solution, and that there might be a lot of obscure features in here, but we think that it might be usefull for other people, at least as a place where to learn some of the tricks that are needed while trying to get efficient algorithms. And how to use some tools like unix sockets and memory managment. Most of the ideas in this code aren't new, and we have tried to give due credit where needed, but if you feel that we should aknlowledge something, please send me an e-mail and I will try to fix it as soon as posible.

Much of the ideas used here come from Concorde, from the Linux Kernel, and from a number of books like Data Structures and Network Algorithms, Network Flows: Theory, Algorithms, and Applications and Introduction to Algorithms and The Art of Computer Programming among others.

You can see the documentation or download the full source code for it.

We also have made available binaries for linux 32 bit and for linux 64 bit

Almost all the code is ISO-C99 compliant, with some GNU C-extensions, and thus compile with any recent version of gcc. (i.e. at least GCC-3.4.1). We haven't tested the code outside the Linux/Unix realm, and for sure some modules (like timers) won't run on other plataforms.

General Structures

This library provide some of the most common structures and some structures have been implemented in more than one form (depending on the coding philosophy to be used), here is a lists:

Parallel Support

We also provide a basic network interface EGnet (with a simple example) that we use on our parallel algorithms/implementations, it is simple enough to use, and also provide some details of how it works, We are not sure regarding portability of this library outside POSIX systems, it has been tested on 32 and 64 bit UNIX and LINUX systems.... but in the worst case it should provide a starting point to work with.

Basic Algorithms

Some common algorithms are implemented:

Memory Managment

For different reasons we have needed some type of memory managment, from macros to simplify memory allocation/free procedures, to actual pool mechanism. There is one general set of macros defined in EGmem, and a Slab-Allocator pool implementation that up to now is in testing phase EGmemSlab.

Simple Templates on C

Beyond the fact that Templates are implemented on C++, for those that like to stick with C, we developed a general way of programming templates for numbers in such a way as to implement at once different versions of the same code with different underlying number definitions, this arose as a necesity while porting QSopt to work on exact arithmetic, and also on multiple precision floating point numbers (as provided by GNUMP library) so that we have only one code for Minimum Global Cuts, but we get implementations for doubles, fixed point arithmetic, GMP's integers, floating points, rationals, and so on. This is done through the Makefile, utilities lake ctags and awk, but uses the general interface EGlpNum as a way to work with numbers.

Final Comments

This library hopes to be usefull in general both to teach some programming tricks, structures and algorithms, and also by providing (we think) usable code, in fact we allways test our code with valgrind (one of the best memory debugger available today in my opinion), and check for any memory leaks and illegal access to memory.