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
• Complete
• Tree
• Famous
• Bull
• Chvátal
• Cubic
• Diamond
• Dodecahedral
• Frucht
• Heawood
• House
• Icosahedral
• Krackhardt Kite
• Octahedral
• Petersen
• Tetrahedral
• Tutte
• Random
• Erdos-Rényi
• Watts-Strogatz
• Barabási–Albert
• Traversal
• Depth-first search
• Breadth-first search
• Isomorphism
• Connected components
• 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
• Cliques
• Maximal cliques
• Clique number
• Number of maximal cliques
• Flows and Cuts
• Maximum flow
• Maximum flow value
• Minimum cut
• Minimum cut value
• Shortest paths
• Shortest paths
• Dijkstra
• Bellman-Ford
• Johnson
• A*
• Distance measures
• Diameter
• Eccentricity
• Radius
• Centrality measures
• Closeness
• Betweenness
• Google PageRank
• Directed Acyclic Graphs (DAGs)
• DAG testing
• Topological sort
• Transitive closure
• Bipartite graphs
• Creation
• Testing
• Creation from adjacency matrix
• Conversion to adjacency matrix
• Projection
• Cores
• Core number
• Chordal graphs
• Chordal testing
• Maximum cardinality search
• Spanning trees
• Minimum spanning tree
• Clustering
• Transitivity
• Clustering coefficient (local transitivity)
• Average clustering (average local transitivity)
• Degree sequences
• Simple graph testing
• Pseudograph testing
• Spectral properties
• Laplacian matrix
• Reading and writing graphs
• Edge list
• GraphML
• GML
• Pajek
• GraphViz

Generators

Deterministic

Star

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_star
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.classic.star_graph.html#networkx.generators.classic.star_graph

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.

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_full
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.classic.complete_graph.html#networkx.generators.classic.complete_graph

Tree

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_tree
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.make_small_graph.html#networkx.generators.small.make_small_graph

Famous

Bull

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.bull_graph.html#networkx.generators.small.bull_graph

Chvátal

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.chvatal_graph.html#networkx.generators.small.chvatal_graph

Cubic

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.cubical_graph.html#networkx.generators.small.cubical_graph

Diamond

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.diamond_graph.html#networkx.generators.small.diamond_graph

Dodecahedral

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkXhttp://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.dodecahedral_graph.html#networkx.generators.small.dodecahedral_graph

Frucht

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.frucht_graph.html#networkx.generators.small.frucht_graph

Heawood

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.heawood_graph.html#networkx.generators.small.heawood_graph

House

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.house_graph.html#networkx.generators.small.house_graph

Icosahedral

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.icosahedral_graph.html#networkx.generators.small.icosahedral_graph

Krackhardt Kite

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.krackhardt_kite_graph.html#networkx.generators.small.krackhardt_kite_graph

Octahedral

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.octahedral_graph.html#networkx.generators.small.octahedral_graph

Petersen

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.petersen_graph.html#networkx.generators.small.petersen_graph

Tetrahedral

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.tetrahedral_graph.html#networkx.generators.small.tetrahedral_graph

Tutte

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_famous
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.small.tutte_graph.html#networkx.generators.small.tutte_graph

Random

Erdos-Rényi

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_erdos_renyi_game
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.random_graphs.erdos_renyi_graph.html#networkx.generators.random_graphs.erdos_renyi_graph
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/erdos_renyi_generator.html

Watts-Strogatz

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_watts_strogatz_game
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.random_graphs.watts_strogatz_graph.html#networkx.generators.random_graphs.watts_strogatz_graph

Barabási–Albert

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

• igraph: http://igraph.org/c/doc/igraph-Generators.html#igraph_barabasi_game
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.random_graphs.barabasi_albert_graph.html#networkx.generators.random_graphs.barabasi_albert_graph

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

• igraph: http://igraph.org/c/doc/igraph-Visitors.html#idm470930797936
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/algorithms.traversal.html#module-networkx.algorithms.traversal.depth_first_search
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/depth_first_search.html/

Breadth-first search

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

• igraph: http://igraph.org/c/doc/igraph-Visitors.html#idm470929187920
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/algorithms.traversal.html#module-networkx.algorithms.traversal.depth_first_search
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/breadth_first_search.html

Isomorphism

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

• igraph: http://igraph.org/c/doc/igraph-Isomorphism.html#igraph_isomorphic
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.isomorphism.is_isomorphic.html#networkx.algorithms.isomorphism.is_isomorphic
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/isomorphism.html

Connected components

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

Connectivity

Connectivity testing

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_connected
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.connected.is_connected.html#networkx.algorithms.components.connected.is_connected

Decomposition into connected components

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_decompose
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.connected.connected_components.html#networkx.algorithms.components.connected.connected_components
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/connected_components.html

Strong connectivity

Strong connectivity testing

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_connected
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.strongly_connected.is_strongly_connected.html#networkx.algorithms.components.strongly_connected.is_strongly_connected

Decomposition into strongly connected components

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_decompose
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.strongly_connected.strongly_connected_components.html#networkx.algorithms.components.strongly_connected.strongly_connected_components
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/strong_components.html

Weak connectivity

Weak connectivity testing

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_connected
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.weakly_connected.is_weakly_connected.html#networkx.algorithms.components.weakly_connected.is_weakly_connected

Decomposition into weakly connected components

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_connected
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.weakly_connected.weakly_connected_components.html#networkx.algorithms.components.weakly_connected.weakly_connected_components

Biconnectivity

Biconnected components

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_biconnected_components
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.biconnected.biconnected_components.html#networkx.algorithms.components.biconnected.biconnected_components
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/biconnected_components.html

Articulation points

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_articulation_points
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.biconnected.articulation_points.html#networkx.algorithms.components.biconnected.articulation_points
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/biconnected_components.html#sec:articulation_points

Cliques

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

Cliques

• igraph: http://igraph.org/c/doc/igraph-Cliques.html#igraph_cliques
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.clique.enumerate_all_cliques.html#networkx.algorithms.clique.enumerate_all_cliques

Maximal cliques

• igraph: http://igraph.org/c/doc/igraph-Cliques.html#igraph_maximal_cliques
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.clique.find_cliques.html#networkx.algorithms.clique.find_cliques

Clique number

• igraph: http://igraph.org/c/doc/igraph-Cliques.html#igraph_clique_number
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.clique.graph_clique_number.html#networkx.algorithms.clique.graph_clique_number

Number of maximal cliques

• igraph: http://igraph.org/c/doc/igraph-Cliques.html#igraph_maximal_cliques_count
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.clique.graph_number_of_cliques.html#networkx.algorithms.clique.graph_number_of_cliques

Flows and Cuts

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

Maximum flow

• igraph: http://igraph.org/c/doc/igraph-Flows.html#igraph_maxflow
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.maximum_flow.html#networkx.algorithms.flow.maximum_flow
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/edmonds_karp_max_flow.html

Maximum flow value

• igraph: http://igraph.org/c/doc/igraph-Flows.html#igraph_maxflow_value
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.maximum_flow_value.html#networkx.algorithms.flow.maximum_flow_value
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/push_relabel_max_flow.html

Minimum cut

• igraph: http://igraph.org/c/doc/igraph-Flows.html#igraph_st_mincut
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.minimum_cut.html#networkx.algorithms.flow.minimum_cut
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/stoer_wagner_min_cut.html

Minimum cut value

• igraph: http://igraph.org/c/doc/igraph-Flows.html#igraph_st_mincut_value
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.minimum_cut_value.html#networkx.algorithms.flow.minimum_cut_value

Shortest paths

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

Shortest paths

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_shortest_paths
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html#networkx.algorithms.shortest_paths.generic.shortest_path

Dijkstra

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_shortest_paths_dijkstra
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.weighted.dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.dijkstra_path
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/dijkstra_shortest_paths.html

Bellman-Ford

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_shortest_paths_bellman_ford
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford.html#networkx.algorithms.shortest_paths.weighted.bellman_ford
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/bellman_ford_shortest.html

Johnson

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_shortest_paths_johnson
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.weighted.johnson.html#networkx.algorithms.shortest_paths.weighted.johnson
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/johnson_all_pairs_shortest.html

A*

• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.astar.astar_path.html#networkx.algorithms.shortest_paths.astar.astar_path
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/astar_search.html

Distance measures

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

Diameter

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_diameter
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.distance_measures.diameter.html#networkx.algorithms.distance_measures.diameter

Eccentricity

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_eccentricity
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.distance_measures.eccentricity.html#networkx.algorithms.distance_measures.eccentricity

Radius

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_radius
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.distance_measures.radius.html#networkx.algorithms.distance_measures.radius

Centrality measures

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

Closeness

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_closeness
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.centrality.closeness_centrality.html#networkx.algorithms.centrality.closeness_centrality

Betweenness

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_closeness
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.centrality.betweenness_centrality.html#networkx.algorithms.centrality.betweenness_centrality
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/betweenness_centrality.html

Google PageRank

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

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_pagerank
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.html#networkx.algorithms.link_analysis.pagerank_alg.pagerank

Directed Acyclic Graphs (DAGs)

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

DAG testing

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_dag
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.dag.is_directed_acyclic_graph.html#networkx.algorithms.dag.is_directed_acyclic_graph

Topological sort

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_topological_sorting
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.dag.topological_sort.html#networkx.algorithms.dag.topological_sort
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/topological_sort.html

Transitive closure

• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.dag.transitive_closure.html
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/transitive_closure.html

Bipartite graphs

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

Creation

• igraph: http://igraph.org/c/doc/igraph-Bipartite.html#idm470928641808
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/algorithms.bipartite.html#module-networkx.algorithms.bipartite

Testing

• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.bipartite.basic.is_bipartite.html#networkx.algorithms.bipartite.basic.is_bipartite
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/is_bipartite.html

Creation from adjacency matrix

Note that the igraph documentation calls this an incidence matrix.

• igraph: http://igraph.org/c/doc/igraph-Bipartite.html#igraph_incidence
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.bipartite.matrix.from_biadjacency_matrix.html#networkx.algorithms.bipartite.matrix.from_biadjacency_matrix

Conversion to adjacency matrix

Note that the igraph documentation calls this an incidence matrix.

• igraph: http://igraph.org/c/doc/igraph-Bipartite.html#igraph_get_incidence
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.bipartite.matrix.biadjacency_matrix.html#networkx.algorithms.bipartite.matrix.biadjacency_matrix

Projection

• igraph: http://igraph.org/c/doc/igraph-Bipartite.html#igraph_bipartite_projection
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.bipartite.projection.projected_graph.html#networkx.algorithms.bipartite.projection.projected_graph

Cores

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

Core number

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_coreness
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.core.core_number.html#networkx.algorithms.core.core_number

Chordal graphs

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

Chordal testing

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_chordal
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/algorithms.chordal.html

Maximum cardinality search

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_maximum_cardinality_search
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.chordal.chordal_alg.chordal_graph_cliques.html#networkx.algorithms.chordal.chordal_alg.chordal_graph_cliques
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/maximum_matching.html

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

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_minimum_spanning_tree
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.tree.branchings.minimum_spanning_arborescence.html#networkx.algorithms.tree.branchings.minimum_spanning_arborescence
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/kruskal_min_spanning_tree.html
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/prim_minimum_spanning_tree.html

Clustering

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

Transitivity

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_transitivity_undirected
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.cluster.transitivity.html#networkx.algorithms.cluster.transitivity

Clustering coefficient (local transitivity)

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_transitivity_local_undirected
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.cluster.clustering.html#networkx.algorithms.cluster.clustering

Average clustering (average local transitivity)

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_transitivity_avglocal_undirected
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.cluster.average_clustering.html#networkx.algorithms.cluster.average_clustering

Degree sequences

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

Simple graph testing

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_graphical_degree_sequence
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.graphical.is_digraphical.html

Pseudograph testing

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_is_degree_sequence
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.graphical.is_pseudographical.html

Spectral properties

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

Laplacian matrix

• igraph: http://igraph.org/c/doc/igraph-Structural.html#igraph_laplacian
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.linalg.laplacianmatrix.laplacian_matrix.html#networkx.linalg.laplacianmatrix.laplacian_matrix

Reading and writing graphs

Edge list

• igraph: http://igraph.org/c/doc/igraph-Foreign.html#idm470920995840
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/readwrite.edgelist.html

GraphML

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

• igraph: http://igraph.org/c/doc/igraph-Foreign.html#idm470938012912
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/readwrite.graphml.html
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/read_graphml.html
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/write_graphml.html

GML

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

• igraph: http://igraph.org/c/doc/igraph-Foreign.html#idm470940295952
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/readwrite.gml.html

Pajek

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

• igraph: http://igraph.org/c/doc/igraph-Foreign.html#idm470940255440
• NetworkX: http://networkx.github.io/documentation/networkx-1.10/reference/readwrite.pajek.html

GraphViz

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

• igraph: http://igraph.org/c/doc/igraph-Foreign.html#idm470945985360
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/read_graphviz.html
• Boost: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/write-graphviz.html
• NetworkX: https://networkx.github.io/documentation/networkx-1.10/examples/pygraphviz/write_dotfile.html