Graphs
Eray Ozkural
erayo@cs.bilkent.edu.tr
Thu, 21 Feb 2002 19:05:18 +0200
-----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-----