# How do researchers carry out computational experiments in Graph Theory?

There are packages like, Combinatorica in Mathematica, GA, SA, PSO can be comparatively easily done in MATLAB, C++ has boost, Java has JGraphT and so on and on. My question is,

1. How do Graph Theorists carry out large computational experiments?
2. What languages or packages or libraries do they usually use? Is their any general preferences?
3. Do they use a combination of many sporadic resources? Like use something that is good at plotting, then use some other thing that is good for numerical solutions etc?
4. Where from you get Hard-Instances ?

Background: I'm assigned to work on a GT problem named 'Degree Constrained Minimum Spanning Tree'. I want to study, implement and compare current algorithms. As I've been studying, I come to observe most of the algorithms are : Heuristics, Distributed Algorithms, Genetic Algorithms, Linear Programming (Narula-Ho) etc. Some uses methods called 'Particle Swarm Optimization', 'Simulated Annealing' and 'Ant Colony Optimization'. As far as I know MATLAB has built in routines for GA, SA, PSO, ACO etc but don't have any graph theory package. Combinatorica seems very good package but I don't have any access to it's accompanying book 'Computational Discrete Mathematics'. I don't know MATLAB or Mathematica.

Update: A comprehensive list on GT packages/systems can be found here: http://wiki.sagemath.org/graph_survey

Update It seems Mathematica 7 has all the above, mostly as built in functions/Commands.

-
Since you do not tell us what you need, it is impossible to answer! (The question in the title, on the other hand, has surely only the possible answer "No", for trivial reasons) –  Mariano Suárez-Alvarez May 28 '10 at 7:34
I've edited the description, hope that clears. Thanks. –  deleted May 28 '10 at 15:00
Honestly, you need a computer to suss out $K_n$ !? –  Jon Awbrey May 28 '10 at 16:50
@Jon : Nope! I need to experiment theorems with a sufficient enough tool, that will not boggle me down to it's acronyms. :) Update: Sagemath is free and has GT packages. But, again, my internet is too slow to download all that 2 GB! :'( –  deleted May 30 '10 at 8:32
Perfunctory joke based on re-associating terms in ostensibly amusing ways, to wit, (Complete Graph) Theory Package. –  Jon Awbrey Jun 1 '10 at 13:57

As TheMadman mentionned in a comment, Sagemath has an impressive Graph library. I have been working on it for quite a while, and I expect you wouldn't find anywhere else the list of methods it has.

I don't think I already wrote a solver for a degree-constrained spanning tree, but I definitely implemented a degree-constrained subgraph there. As Mixed Integer Linear Programming is easily available, something like 20 lines of code are enough to get an exact solver for the min degree spanning tree problem anyway.

You will find help of its methods (and so the list of them) at this address :

http://www.sagemath.org/doc/reference/graphs.html

be sure to check both "generic graphs" and "Graph" :-)

Nathann

-
Hey, thanks for the link! Sage is very good except that it's not windows native. :( –  deleted Sep 24 '10 at 23:57

If you are not limited to java/c++/matlab and know python, you should take a look at networkx, it's pretty complete.

-
thanks for the share. sagemath.org includes this package too. but, as you wrote I have to be really good to do anything useful –  deleted Jun 16 '10 at 15:44

Boost has an extensive graph library. If you're more of a python maven, then David Eppstein's PADS library is quite extensive. But from your description, and the choice of heuristics you're looking at, not clear why you want a graph theory package, as opposed to a general set of heuristics and some adjacency list representation.

-
well, i'm a newbie. and i really don't know what to do! i just know there are several existing solutions to the problem i'm dealing with. and i need to implement and compare them. how? i don't know. i saw a book on all those optimization algos using MATLAB. and found mathematica have combinatorica as a special graph theory package consisting 450 function. like it a random graph generator function. so i can create random graphs with it and then run those optimization algos on these graphs and see what happen. but creation and visualization of user defined graphs in combinatorica is hard. –  deleted Jun 16 '10 at 15:52
sagemath excels here. –  deleted Jun 16 '10 at 15:54
Boost is VERY hard to use. Unless you're a C++ wizard I wouldn't recommend using it. –  Michael Hoffman Jun 16 '10 at 17:33
Boost itself isn't tricky -- I'd say it makes programming in C++ far more pleasant than if it wasn't there. The complexity is with C++, not Boost. –  Ryan Budney Sep 24 '10 at 17:38

JUNG is quite extensive, though I wouldn't claim that it's complete.

-
Thanks. jGraphT is good too. But, I'm too newbie to use it. They use generics and all sort of java acronyms. I wish I could have some tool, that would let me keep my concentration on GT, not on it's implementation. –  deleted May 28 '10 at 15:18

I wouldn't claim that it's complete, as I've only used parts of it, but QuickGraph is an excellent package for .NET/C#. Besides a wide range of mathematical/algorithmic tools, it also has layout algorithms and imports/exporters for various formats.

-

I've used LEDA with really good results. There's also a pretty good book on LEDA and combinatorial geometry in general (available for free download now) from the linked website.

For a good open-source alternative, see GOBLIN.

-
Well it seems promising! Specially, the accompanying free book. Let, me study more before I get you accepted. :P –  deleted Jul 2 '10 at 6:30
@baudolino : The book's free. But the software is not. They don't provide Graph Algorithms in the free edition. ;( Advanced graph related tools are included in 'Researcher' edition. –  deleted Jul 5 '10 at 10:02