5
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 6
    $\begingroup$ 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) $\endgroup$
    – Mariano Suárez-Álvarez
    Commented May 28, 2010 at 7:34
  • $\begingroup$ I've edited the description, hope that clears. Thanks. $\endgroup$
    – deleted
    Commented May 28, 2010 at 15:00
  • 1
    $\begingroup$ Honestly, you need a computer to suss out $K_n$ !? $\endgroup$
    – Jon Awbrey
    Commented May 28, 2010 at 16:50
  • $\begingroup$ @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! :'( $\endgroup$
    – deleted
    Commented May 30, 2010 at 8:32
  • 1
    $\begingroup$ Perfunctory joke based on re-associating terms in ostensibly amusing ways, to wit, (Complete Graph) Theory Package. $\endgroup$
    – Jon Awbrey
    Commented Jun 1, 2010 at 13:57

6 Answers 6

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for the share. sagemath.org includes this package too. but, as you wrote I have to be really good to do anything useful $\endgroup$
    – deleted
    Commented Jun 16, 2010 at 15:44
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – deleted
    Commented Jun 16, 2010 at 15:52
  • $\begingroup$ sagemath excels here. $\endgroup$
    – deleted
    Commented Jun 16, 2010 at 15:54
  • $\begingroup$ Boost is VERY hard to use. Unless you're a C++ wizard I wouldn't recommend using it. $\endgroup$
    – Michael Hoffman
    Commented Jun 16, 2010 at 17:33
  • $\begingroup$ 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. $\endgroup$
    – Ryan Budney
    Commented Sep 24, 2010 at 17:38
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – deleted
    Commented May 28, 2010 at 15:18
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well it seems promising! Specially, the accompanying free book. Let, me study more before I get you accepted. :P $\endgroup$
    – deleted
    Commented Jul 2, 2010 at 6:30
  • $\begingroup$ @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. $\endgroup$
    – deleted
    Commented Jul 5, 2010 at 10:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .