Graphs

[Eray Ozkural]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I used graphs in haskell, but I don't think you'll get anywhere the kind of
efficiency of a language like C++ where you have exact control over 
operations and structures....

There is the graph code in "functional algorithms" book....

            Algorithms: a functional programming approach
               Fethi A. Rabhi, University of Hull, UK
               Guy Lapalme, Université de Montréal, Canada

The code is available online.

I recommend you to start with that one. Stay away from finite map stuff in 
edison if you can. (Although you can get it to implement graphs/hypergraphs 
after some amount of work)

If you're going to prototype an algorithm, you will eventually have to use 
monads which will be harder to write than the final C++/C implementation.

Why is that so? Because if you're writing the graph code in haskell, the 
really easier/better way is to use things like substitution, infinite graphs, 
etc. for an elegant and short code, in that it reflects the theoretical 
construction. But an algorithm designed for a serial machine is so much 
different. I've written graph algorithms from multilevel graph partitioning 
to graph clustering, so I think I know what I'm talking about :)

If you're using C++, you can prototype an algorithm fairly easily.

Here is how you can implement it.

use list< vector<int> > to store adjacency lists.
use a vector< vector<int>* > to index the adjacency lists.
use separate vectors to hold labels. I won't go into the reasons why those 
are the ones to start with, eventually your super-optimized code will be 
similar to the above.

Don't use a graph library. It will make your job harder! Avoid template 
libraries if you can (except stdlib...), and resist the temptation to 
templatize your code.

You will find that it's much more easier to write graph algorithms that way. 
And yes, although it would be in theory be a good idea to be able to 
prototype your algorithm in an easier-to-use language, such a language does 
not exist. Unless you can show me graph code side-by-side and prove it to me 
I will never believe it :)

For a start one would have to show me the implementation of non-trivial 
algorithms such as graph coarsening, all-to-all shortest paths, maximal 
cliques, etc. in the easier-than-C++ language contrasted with (good) C++ 
implementation.

I'm thinking maybe it would be more-possible in ocaml, but I'm a beginner in 
ocaml and I don't think I'm enough of a ocaml-hacker to talk about it.

Thanks,

On Thursday 21 February 2002 18:01, Wojciech Fraczak wrote:
> Hi everybody,
>
> I would like to ask you, if you do not know any graph library for
> haskell. I would like to use haskell for prototyping some of
> algorithms on graphs and finite state automata/transducers. In fact
> what I'm looking for is a good (efficient and easy readable) data type
> definition for labeled graphs.
>
> Thanks,

- -- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE8dSjSfAeuFodNU5wRAk8rAJ9CIwZUmEKHpttK2IwTXO0fnk8/egCeOV/A
y3yq4cDFx1mZQPC6SbK19JU=
=QoPG
-----END PGP SIGNATURE-----