Release date: 2 August 2015
Support for Python 2.6 is dropped in this release.
Connected components now return generators
new functions including
enumerate_all_cliques, greedy_coloring, edge_dfs, find_cycle immediate_dominators, harmonic_centrality
Hopcraft–Karp algorithm for maximum matchings
optimum branchings and arborescences.
pyparsing dependence removed from GML reader/parser
improve flow algorithms
new generators related to expander graphs.
new generators for multipartite graphs, nonisomorphic trees, circulant graphs
allow graph subclasses to use dict-like objects in place of dicts
added ordered graph subclasses
pandas dataframe read/write added.
data keyword in G.edges() allows requesting edge attribute directly
expanded layout flexibility for node subsets
Kanesky’s algorithm for cut sets and k_components
power function for graphs
approximation of node connectivity
transitive closure, triadic census and antichains
quotient graphs and minors
longest_path for DAGS
modularity matrix routines
strongly_connected_componentsreturn now a generator of sets of nodes. Previously the generator was of lists of nodes. This PR also refactored the
weakly_connected_componentsimplementations making them faster, especially for large graphs.
func_iterfunctions in Di/Multi/Graphs classes are slated for removal in NetworkX 2.0 release.
funcwill behave like
func_iterand return an iterator instead of list. These functions are deprecated in NetworkX 1.10 release.
enumerate_all_cliquesfunction is added in the clique package (
networkx.algorithms.clique) for enumerating all cliques (including nonmaximal ones) of undirected graphs.
[#1105] A coloring package (
networkx.algorithms.coloring) is created for graph coloring algorithms. Initially, a
greedy_colorfunction is provided for coloring graphs using various greedy heuristics.
[#1193] A new generator
edge_dfs, added to
networkx.algorithms.traversal, implements a depth-first traversal of the edges in a graph. This complements functionality provided by a depth-first traversal of the nodes in a graph. For multigraphs, it allows the user to know precisely which edges were followed in a traversal. All NetworkX graph types are supported. A traversal can also reverse edge orientations or ignore them.
find_cyclefunction is added to the
networkx.algorithms.cyclespackage to find a cycle in a graph. Edge orientations can be optionally reversed or ignored.
[#1210] Add a random generator for the duplication-divergence model.
[#1241] A new
networkx.algorithms.dominancepackage is added for dominance/dominator algorithms on directed graphs. It contains a
immediate_dominatorsfunction for computing immediate dominators/dominator trees and a
dominance_frontiersfunction for computing dominance frontiers.
[#1269] The GML reader/parser and writer/generator are rewritten to remove the dependence on pyparsing and enable handling of arbitrary graph data.
[#1280] The network simplex method in the
networkx.algorithms.flowpackage is rewritten to improve its performance and support multi- and disconnected networks. For some cases, the new implementation is two or three orders of magnitude faster than the old implementation.
[#1286] Added the Margulis–Gabber–Galil graph to
[#1306] Added the chordal p-cycle graph, a mildly explicit algebraic construction of a family of 3-regular expander graphs. Also, moves both the existing expander graph generator function (for the Margulis-Gabber-Galil expander) and the new chordal cycle graph function to a new module,
[#1314] Allow overwriting of base class dict with dict-like: OrderedGraph, ThinGraph, PrintGraph, etc.
[#1322] Added the Hopcroft–Karp algorithm for finding a maximum cardinality matching in bipartite graphs.
[#1336] Expanded data keyword in G.edges and added default keyword.
[#1338] Added support for finding optimum branchings and arborescences.
[#1340] Added a
from_pandas_dataframefunction that accepts Pandas DataFrames and returns a new graph object. At a minimum, the DataFrame must have two columns, which define the nodes that make up an edge. However, the function can also process an arbitrary number of additional columns as edge attributes, such as ‘weight’.
[#1354] Expanded layout functions to add flexibility for drawing subsets of nodes with distinct layouts and for centering each layout around given coordinates.
[#1356] Added ordered variants of default graph class.
[#1360] Added harmonic centrality to
generators.bipartitehave been moved to
algorithms.bipartite.generators. The functions are not imported in the main namespace, so to use it, the bipartite package has to be imported.
[#1391] Added Kanevsky’s algorithm for finding all minimum-size separating node sets in an undirected graph. It is implemented as a generator of node cut sets.
[#1399] Added power function for simple graphs
[#1405] Added fast approximation for node connectivity based on White and Newman’s approximation algorithm for finding node independent paths between two nodes.
[#1413] Added transitive closure and antichains function for directed acyclic graphs in
algorithms.dag. The antichains function was contributed by Peter Jipsen and Franco Saliola and originally developed for the SAGE project.
[#1425] Added generator function for the complete multipartite graph.
[#1427] Added nonisomorphic trees generator.
[#1436] Added a generator function for circulant graphs to the
[#1437] Added function for computing quotient graphs; also created a new module,
[#1438] Added longest_path and longest_path_length for DAG.
[#1439] Added node and edge contraction functions to
[#1445] Added a new modularity matrix module to
networkx.linalg, and associated spectrum functions to the
[#1447] Added function to generate all simple paths starting with the shortest ones based on Yen’s algorithm for finding k shortest paths at
[#1455] Added the directed modularity matrix to the
triadic_censusfunction; also creates a new module,
[#1476] Adds functions for testing if a graph has weighted or negatively weighted edges. Also adds a function for testing if a graph is empty. These are
[#1481] Added Johnson’s algorithm; one more algorithm for shortest paths. It solves all pairs shortest path problem. This is
[#1414] Added Moody and White algorithm for identifying
k_componentsin a graph, which is based on Kanevsky’s algorithm for finding all minimum-size node cut-sets (implemented in
[#1415] Added fast approximation for
networkx.approximationpackage. This is based on White and Newman approximation algorithm for finding node independent paths between two nodes (see #1405).
[#1236] The legacy
ford_fulkersonmaximum flow function is removed. Use
[#1192] Support for Python 2.6 is dropped.