# Graph algorithms

## Introduction

This is a list of graph algorithms with links to references and implementations.
The graph libraries included are igraph, NetworkX, and Boost Graph Library.

## Generators

### Deterministic

#### Complete

Note that the igraph function can produce directed complete graphs, as well as those containing 1 or more self-loops.

#### Famous

##### Bull

Wikipedia: https://en.wikipedia.org/wiki/Bull_graph

##### Dodecahedral

Wolfram MathWorld: http://mathworld.wolfram.com/DodecahedralGraph.html

##### House

Wolfram MathWorld: http://mathworld.wolfram.com/HouseGraph.html

##### Icosahedral

Wolfram MathWorld: http://mathworld.wolfram.com/IcosahedralGraph.html

##### Krackhardt Kite

Wolfram MathWorld: http://mathworld.wolfram.com/KrackhardtKite.html

##### Octahedral

Wolfram MathWorld: http://mathworld.wolfram.com/OctahedralGraph.html

##### Petersen

Wolfram MathWorld: http://mathworld.wolfram.com/PetersenGraph.html

##### Tetrahedral

Wolfram MathWorld: http://mathworld.wolfram.com/TetrahedralGraph.html

## Bipartite graphs

Wolfram Mathworld: http://mathworld.wolfram.com/BipartiteGraph.html

### Testing

Note that the igraph documentation calls this an incidence matrix.

Note that the igraph documentation calls this an incidence matrix.

## Chordal graphs

Wolfram Mathworld: http://mathworld.wolfram.com/ChordalGraph.html

## Spanning trees

Note that in NetworkX they are called arborescences (http://networkx.github.io/documentation/networkx-1.10/reference/algorithms.tree.html#recognition-tests).

## Spectral properties

### GraphML

The GraphML File Format: http://graphml.graphdrawing.org/

GML

GML: a portable Graph File Format: http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/brandenburg/projekte/gml/gml-technical-report.pdf

### Pajek

Pajek / Pajek-XXL: http://mrvar.fdv.uni-lj.si/pajek/

### GraphViz

GraphViz: http://www.graphviz.org/