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.

Contents

Generators

Deterministic

Star

Wikipedia: https://en.wikipedia.org/wiki/Star_%28graph_theory%29

Complete

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

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

Tree

Famous

Bull

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

Chvátal

Wikipedia: https://en.wikipedia.org/wiki/Chv%C3%A1tal_graph

Cubic

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

Diamond

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

Dodecahedral

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

Frucht

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

Heawood

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

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

Tutte

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

Random

Erdos-Rényi

Wikipedia: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model

Watts-Strogatz

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

Barabási–Albert

Wikipedia: https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model

Traversal

Lecture notes: http://web.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch14.html

Depth-first search

Wikipedia: https://en.wikipedia.org/wiki/Depth-first_search

Breadth-first search

Wikipedia: https://en.wikipedia.org/wiki/Breadth-first_search

Isomorphism

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

Connected components

Wikipedia: https://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29

Connectivity

Connectivity testing

Decomposition into connected components

Strong connectivity

Strong connectivity testing

Decomposition into strongly connected components

Weak connectivity

Weak connectivity testing

Decomposition into weakly connected components

Biconnectivity

Biconnected components

Articulation points

Cliques

Wikipedia: https://en.wikipedia.org/wiki/Clique_%28graph_theory%29

Cliques

Maximal cliques

Clique number

Number of maximal cliques

Flows and Cuts

Lecture notes: http://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf

Maximum flow

Maximum flow value

Minimum cut

Minimum cut value

Shortest paths

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

Shortest paths

Dijkstra

Bellman-Ford

Johnson

A*

Distance measures

Wikipedia: https://en.wikipedia.org/wiki/Distance_%28graph_theory%29

Diameter

Eccentricity

Radius

Centrality measures

Lecture notes: http://cs.brynmawr.edu/Courses/cs380/spring2013/section02/slides/05_Centrality.pdf

Closeness

Betweenness

Google PageRank

Paper: http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

Directed Acyclic Graphs (DAGs)

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

DAG testing

Topological sort

Transitive closure

Bipartite graphs

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

Creation

Testing

Creation from adjacency matrix

Note that the igraph documentation calls this an incidence matrix.

Conversion to adjacency matrix

Note that the igraph documentation calls this an incidence matrix.

Projection

Cores

Paper: http://arxiv.org/abs/cs.DS/0310049

Core number

Chordal graphs

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

Chordal testing

Maximum cardinality search

Spanning trees

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

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

Minimum spanning tree

Clustering

Article: http://dollar.biz.uiowa.edu/~street/graphClustering.pdf

Transitivity

Clustering coefficient (local transitivity)

Average clustering (average local transitivity)

Degree sequences

http://mathworld.wolfram.com/DegreeSequence.html

Simple graph testing

Pseudograph testing

Spectral properties

Book chapter: http://www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf

Laplacian matrix

Reading and writing graphs

Edge list

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/