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,


*

*How do Graph Theorists carry out large computational experiments?

*What languages or packages or libraries do they usually use? Is their any general preferences?

*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?

*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.
 A: 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
A: If you are not limited to java/c++/matlab and know python, you should take a look at networkx, it's pretty complete.
A: 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. 
A: JUNG is quite extensive, though I wouldn't claim that it's complete.
A: 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.
A: 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.
