Graph Theory Algorithms Please read if you've done graph theory with CUDA

As I’ve written about a few times before, I’m currently working on a free .NET numerical/math library that will also feature CUDA acceleration wherever possible. As of right now, I’m still implementing the underlying C# code to do calculations on the CPU (which is the fallback when the GPU is not available, or not needed). I’m about to start implementing the graph theory part of the library, and I was curious to know which graph theory algorithms or problems you found CUDA useful for – this way I can make sure to add useful features to the library that will also (eventually) have the benefit of seamless CUDA acceleration, which I think will be a great way to get developers to use the library in their projects.

Also, are there any graph-theoretical algorithms/problems that you would like to see implemented in a free library (and possibly, accelerated with CUDA)? No promises here, but I’ll see what I can do ^_^. I also don’t mind re-implementing something that is already available in a free library, since sometimes they can be difficult to “shoehorn” into your own program.

Rather than implementing CPU code from scratch, you could use the LEDA library (http://www.algorithmic-solutions.com/leda/), which has data structures and implementations for many popular graph algorithms. I think LEDA would also serve as a decent basis for speedup comparisons.

Paulius

Thanks paulius, I’ll check it out. I’m still going to have to implement the host-side code myself though, since I’m writing the library in C# and the motivation for it is that the library is 99% managed C# (the other 1% being the calls to the CUDA driver for launching the kernels); I’m also planning to release the entire library (C# code and CUDA kernels) under the BSD license, so I’m trying to be careful not to include any outside code or library references (in case their licenses are non-compatible). However, when I get the library completed (or at least the graph theory part), LEDA will serve as a nice benchmark measure the speed and accuracy of my library (especially to see how much the CUDA part helps!)

EDIT: I’m also trying to make sure that the library can be compiled with Mono, for all you linux types out there ;)

hello;
Hello;
I am a student and I need a Luck’s algorithm, witch finds isomorphim between two graphs with bouded valence, his paper is untitled “Isomorphism of graphs of bounded valence can be tested in polynomial time”.
thanks

Do you know if this is a parallel algorithm (or a sequential algorithm that could be parallelized)? If not, porting it to CUDA isn’t going to give any speed-up.

Hello;

But my problem is that I don’t know algorithm be ccause the article doesn’t contain algorithm but only mathemtical proof, witch I don’t anderstand because I havn’t the mathematical background, if you know someone who imlemented this algorithm I am very interesting because it is fondamental in my work.

Thanks

Well, I can take a look at the full paper later, but if anyone else is interested, here is the abstract:

http://www.sciencedirect.com/science?_ob=A…57c972927bb8be6

It looks like it might be a candidate for CUDA acceleration since it states that parts of the algorithm use divide-and-conquer techniques.

Unfortunately bddtn, I’m not quite ready to start work on the CUDA implementations of the graphing algorithms in my library (in fact, I’ve really just gotten started on the graph classes). I’ll keep the Luks algorithm in mind though, since I planned to implement an isomorphism testing function in the library anyway.

hi, do you have any progress about your project, please? I am very interested in your project. I may be ready to implement a GPU-based graph algorithm library, however I know there are quite a few issues need to solve.

Hi mianlu…I never quite got around to finishing this project, but it is still on my ‘to-do’ list. I’ve been caught up with a project at work for a few months that has been keeping me busy, but I should be finished with that in a few days, so then I’ll have some time to work on the graph theory library again. I got most of the bases classes implemented in .NET, but not much of the CUDA work, so that’s probably what I’ll focus on when I get back to things.

If you go ahead with your own library, keep us posted – I would be interested to hear about what algorithms you are implementing and what kind of performance you are able to get out of them.

Hello profquail, I am an student and I´m also working with graph algorithms, specifically the floyd algorithm, I implemented a parallel version of it, but somehow I am not getting right results, I was wondering if you could see what am I missing, here is the link to the topic I posted [topic=“95970”]Floyd algorithm problem[/topic], thanks a lot for any help!