What is the fastest computational graph theory package?

Question

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.

Answer 1

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.

Answer 2

Answering my own question here to add some relevant information I've learned since asking it.

NAUTY turns out to be the fastest package for computing graph automorphisms. There are a few competing algorithms mentioned on the page, but they seem pretty neck and neck for most applications. NAUTY is what GAP calls when it computes automorphism groups, and it is also accessible through an apparatus called dreadnaut, for non-developer types.