No, don't run away screaming!

Don't be afraid of the name "graph-theory", 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. Here is a sudoku, its encoding as a graph coloring instance and its solution, as computed by the Graph Coloring algorithm.

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: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 leastsome thing to do with graphtheory and maybe
you even have programmed graphtheoretic applications already without knowing it.

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.

Don't be afraid of the name "graph-theory", 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 -

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. Here is a sudoku, its encoding as a graph coloring instance and its solution, as computed by the Graph Coloring algorithm.

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:

- create a vertex for every city
- create an edge for every traffic link between two cities
- use Dijksta's Algorithm (that's how your satnav works)

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

### Let's see some areas where you (can) meet graphs in practice.

- Routing: Dijksta's Algorithm, Travelling Salesman Problem
- Logistics: see Network Theory
- Electrical circuits
- Chemistry
- Evolutionary Biology
- Parsers (e.g. compilers, file loaders): see Automata Theory
- Analysis of the stability of multithreading applications: see Petri Nets
Every program can be modelled as a Turing Machine- Flowcharts
- Artificial intelligence: Neural networks
- Databases: see this example of a relational database, modelled as a graph
- Probability theory: see Markov Chains and Bayesian Networks
- Google Page-Rank
- Social Networks
- Dating-Sites: see Matching problem
- Computer Networks, such as the Internet
- Mind-mapping
- class hierarchies

### 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 4 GHz per core - you need multithreading or your applications won't benefit from further CPU-developments (= more cores at 4 GHz each) since every thread can only run on one core at the same time.
- Some are not open source