Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the fastest computational graph theory package with respect to executing algorithms and computing graph theoretic data?

I am aware of this related question, which requests graph theory software geared towards drawing graphs and getting data on them. I don't care about graph drawing, or user interface in general, so much as the speed of the analysis and the variety of algorithms available. Basically, I'm trying to find the graph theoretic analog of MAGMA. (Note: I do know magma has some graph theory, but it is very limited.)

I would prefer the software be free if possible, but I may be able to pay depending on the price of a student license.

share|cite|improve this question
Maybe a review of Sage Graph Survey might provide some leads. This posting might also provide some items of interest. I am curious about the answer to this question as I am ignorant on this topic. I also recall a package for Mathematica called Combinatoria. – Amzoti Apr 16 '13 at 4:18
@Amzoti Thanks. I'll take a look at those. Combinatorica sucks, though, actually that is what I currently use which leads me to seek an alternative. – Alexander Gruber Apr 16 '13 at 4:23
@Amzoti Sage is more academic-oriented. It is not very good for graph with large data sets. – Shuhao Cao Apr 16 '13 at 5:01

Alex, this might not be an answer, but hope it will help somehow. As a computational scientist, I always attend those seminar where CS people talking about optimization, etc. Based on what I heard, I think instead of looking for graph theory packages most of which mainly focus on visualization, I suggest try to look for some packages that do discrete optimization/parallel optimization/optimization in combinatorics. And then implement something that caters your need.

IBM has a super high performance package which you might be interested in: CPlex Optimizer, and CPlex has a MATLAB API too.

I have seen people using OpenMP helping the optimization and parallelization for discrete problems.

Some google-fu leads me to CHiPPS and TSPLIB.

I don't know if there is anything open-source like LAPACK or MAGMA for graphy optimization problems, if there is one, I would like to get my hands on it too.

share|cite|improve this answer
Thanks for the input. Yes I definitely agree on not looking for visualization. I am more looking to solve problems like "test all graphs on less than 1000 vertices which satisfy hypothesis X, find their eigenvalues, write to a file." This sort of thing. Optimization in enumeration algorithms would probably be especially useful to me. – Alexander Gruber Apr 16 '13 at 5:40

I've been using open source library LEMON (

I have compared it to other libraries for my application and this is the fastest one.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.