How do researchers carry out computational experiments in Graph Theory? - MathOverflow

How do researchers carry out computational experiments in Graph Theory?

2010-05-28T05:51:23Z

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.

Answer by supercooldave for How do researchers carry out computational experiments in Graph Theory?

2010-05-28T07:31:52Z

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

Answer by Adrien Friggeri for How do researchers carry out computational experiments in Graph Theory?

2010-06-16T03:00:34Z

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

Answer by Suresh Venkat for How do researchers carry out computational experiments in Graph Theory?

2010-06-16T04:43:10Z

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.

Answer by Noldorin for How do researchers carry out computational experiments in Graph Theory?

2010-06-16T17:16:50Z

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.

Answer by baudolino for How do researchers carry out computational experiments in Graph Theory?

2010-07-02T03:13:57Z

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.

Answer by Nathann Cohen for How do researchers carry out computational experiments in Graph Theory?

2010-09-24T19:36:42Z

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