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
- Traversal
- Isomorphism
- Connected components
- Cliques
- Flows and Cuts
- Shortest paths
- Distance measures
- Centrality measures
- Directed Acyclic Graphs (DAGs)
- Bipartite graphs
- Cores
- Chordal graphs
- Spanning trees
- Clustering
- Transitivity
- Clustering coefficient (local transitivity)
- Average clustering (average local transitivity)
- Degree sequences
- Spectral properties
- Reading and writing graphs
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: 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