Home  RSS       Getting Started  Video-Tutorials  Documentation  GXL Format  FAQ        Download  SVN        Wiki  Forum  Bugtracker         Links 




  Free Software Foundation

GPLv3
LGPL

Electronic Frontier Foundation

Mozilla.org OpenOffice.org Linux.com

No, don't run away screaming!
Don't be afraid of the word "graphtheory", it's not about function-graphs (that you probably remember from highschool) and it's not as theoretical as it sounds. Many areas of graphtheory are more like puzzle-games and once you are into it, graphtheory becomes intriguing and fun.

But first things first - what is a graph? A graph consists of a couple of dots (such a dot is called a "vertex" or "node") and some of these dots are connected by lines (which are called "edges"). Graphtheory mostly deals with finding sets or orderings of these dots or lines, which have some special property. Sounds boring? So does Sudoku!

Speaking of Sudoku - Sudoku is actually a graphtheoretic problem and we have a sudoku solver that uses our Graph Coloring algorihtm. Here

is the graph-representation of a sudoku.

Most graphtheoretic problems are somehow like sudoku. There are many properties that allow you to find a solution without trying all combinations. You also don't try all combinations to solve a sudoku, right? Searching these properties is the fun in graptheory.

Imagine you want to travel through some country and visit several cities, but you want to spend as little money as possible. Finding the cheapest route between two cities is easy: 1. create a vertex for every city 2. create an edge for every traffic link between two cities 3. use Dijksta's Algorithm (that's how your satnav works). Finding the cheapest route through many cities in contrast is one of the hardest problems imaginable (Travelling Salesman Problem). You are probably thinking right now "A hard problem? Hah! Computers are so fast nowadays - let a computer do the work!", but you'd be surprised how bad even supercomputers are at solving such problems.

The issue here is that the Travelling Salesman Problem, like most other graphtheoretic problems, is NP-Hard. Let's not go too much into detail on this subject - all you need to know for now is that there are problems, which are very hard to solve. Theoretical computer science mostly deals with finding faster and faster algorithms for these problems - and rightfully so, as they usually have important practical applications. Nearly every field of programming has at least something to do with graphtheory and maybe you even have programmed graphtheoretic applications already without knowing it.

Let's see some areas where you (can) meet graphs in practice.
You have to admit:
graphs are everywhere! To be a really good programmer, you should be familiar with graphs and the standard-operations on them. Sadly, graphtheory is not part of programming apprenticeship and most programming books. This leaves you writing programs in a very graph-like way, not reallizing that you could just model your problems as graphs and use graph-algorithms.

The situation however is not as good as it sounds. You can hardly "just use" the existing algorithms for a number of reasons. The main reason is probably that the inventors of graphtheoretic algorithms have no incentive to actually program their algorithms, because the programs can hardly interface with other graphtheoretic programs, so programming the algorithms would be futile. This is why one of the main purposes of this project is trying to establish an open standard for a graph-filetype. See the documentation of the GXL Fileformat

Usually you have to write many of the algorithms for yourself (if you even understand them), but you don't have the time to go deep enough into the subjects to come up with the powerful optimizations that are possible. This is where the Open-Graphtheory project comes in.
We make the best known graph-algorithms easily accessible with simple interfaces!

There already are several graphtheory frameworks, but all that are known to us have major dealbreakers.
  • They are very incomplete. Most have only the default algorithms for spanning trees, shortest paths or maximum flows but they don't have algorithms for many other, very important problems
  • They are not versatile enough. Many are written specifically for a special purpose, like graph-drawing
  • Most graphtheory programs only support directed or only undirected graphs. Open-Graphtheory supports mixed graphs and hypergraphs, including half-edges and loose edges
  • They are not thread-safe, so you can't use them (decently) in multithreaded programs. CPU-Cores have reached a maximum around 3.5 GHz per core - you need multithreading or your applications won't benefit from further CPU-developments (= more cores at 3.5 GHz each) since every thread can only run on one core at the same time.
  • Some are not open source
None the less, as open source advocates we support freedom of choice and actively fight vendor lock-ins, so here are links to other graphtheory libraries and we have export filters for all graph-filetypes we know about. (tell us if you know of more C++ graphtheory libraries). For help on interfacing with open-graphtheory, see the documentation of the GXL Fileformat.




Staff   Disclaimer   Openness Guarantee