Skip to content

Tags: nahumsa/retworkx

Tags

0.8.0

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.8.0

0.7.2

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.7.2

0.7.1

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.7.1

This release includes a fix for an oversight in the previous 0.7.0 and
0.6.0 releases. Those releases both added custom return types
BFSSuccessors, NodeIndices, EdgeList, and WeightedEdgeList that
implemented the Python sequence protocol which were used in place of
lists for certain functions and methods. However, none of those classes
had support for being pickled, which was causing compatibility issues
for users that were using the return in a context where it would be
pickled (for example as an argument to or return of a function called
with multiprocessing). This release has a single change over 0.7.0 which
is to add the missing support for pickling BFSSuccessors, NodeIndices,
EdgeList, and WeightedEdgeList which fixes that issue.

0.7.0

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.7.0

This release includes several new features and bug fixes.

This release also dropped support for Python 3.5. If you want to use
retworkx with Python 3.5 that last version which supports Python 3.5
is 0.6.0.

Added
-----
- New generator functions for two new generator types, mesh and grid
  were added to retworkx.generators for generating all to all and grid
  graphs respectively.  These functions are:
  retworkx.generators.mesh_graph,
  retworkx.generators.directed_mesh_graph,
  retworkx.generators.grid_graph, and
  retworkx.generators.directed_grid_graph
- A new function, digraph_union, for taking the union between two
  PyDiGraph objects has been added.
- A new PyDiGraph method merge_nodes has been added. This method
- A new PyDiGraph method find_node_by_weight which can be used to lookup
  a node index by a given weight/data payload.
- A new return type NodeIndices has been added. This class is returned
  by functions and methods that return a list of node indices. It
  implements the Python sequence protocol and can be used as list.
- Two new return types EdgeList and WeightedEdgeList. These classes are
  returned from functions and methods that return a list of edge tuples
  and a list of edge tuples with weights. They both implement the Python
  sequence protocol and can be used as a list
- A new function collect_runs() has been added. This function is used to
  find linear paths of nodes that match a given condition.

Upgrade
-------
- Support for running retworkx on Python 3.5 has been dropped. The last
  release with support for Python 3.5 is 0.6.0.
- The PyDiGraph.node_indexes(), PyDiGraph.neighbors(),
  PyDiGraph.successor_indices(), PyDiGraph.predecessor_indices(),
  PyDiGraph.add_nodes_from(), PyGraph.node_indexes(),
  PyGraph.add_nodes_from(), and PyGraph.neighbors() methods and the
  dag_longest_path(), topological_sort(),
  graph_astar_shortest_path(), and digraph_astar_shortest_path()
  functions now return a NodeIndices object instead of a list of
  integers. This should not require any changes unless explicit type
  checking for a list was used.
- The PyDiGraph.edge_list() and PyGraph.edge_list() methods and
  digraph_dfs_edges(), graph_dfs_edges(), and digraph_find_cycle()
  functions now return an EdgeList object instead of a list of integers.
  This sholud not require any changes unless explict type checking
  for a list was used.
- The PyDiGraph.weighted_edge_list(), PyDiGraph.in_edges(),
  PyDiGraph.out_edges(), and PyGraph.weighted_edge_list() methods now
  return a WeightedEdgeList object instead of a list of integers. This
  should not require any changes unless explicit type checking for a
  list was used.

Fixes
-----
- BFSSuccessors objects now can be compared with == and != to any other
  python sequence type
- The built and published sdist packages for retworkx were previously
  not including the Cargo.lock file. This meant that the reproducible
  build versions of the rust dependencies were not passed through to
  source

0.6.0

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.6.0

This release includes a number of new features and bug fixes. The main
focus of this release was to expand the retworkx API functionality to
include some commonly needed functions that were missing.

This release is also the first release to provide full support for
running with Python 3.9. On previous releases Python 3.9 would likely
work, but it would require building retworkx from source. Also this will
likely be the final release that supports Python 3.5.

Added
-----
- Two new functions, digraph_k_shortest_path() and
  graph_k_shortest_path(), for finding the k shortest path lengths from
  a node in a PyDiGraph and PyGraph.
- A new method, is_symmetric(), to the PyDiGraph class. This method will
  check whether the graph is symmetric or not
- A new kwarg, as_undirected, was added to the
  digraph_floyd_warshall_numpy() function. This can be used to treat the
  input PyDiGraph object as if it was undirected for the generated output
  matrix.
- A new function, digraph_find_cycle(), which will return the first
  cycle during a depth first search of a PyDiGraph object.
- Two new functions, directed_gnm_random_graph() and
  undirected_gnm_random_graph(), for generating random G(n, m) graphs.
- A new method, remove_edges_from(), was added to PyDiGraph and PyGraph.
  This can be used to remove muliple edges from a graph object in a
  single call.
- A new method, subgraph(), was added to PyDiGraph and PyGraph which
  takes in a list of node indices and will return a new object of the
  same type representing a subgraph containing the node indices in that
  list.
- Added support for running with Python 3.9
- A new method, to_undirected(), was added to PyDiGraph. This method
  will generate an undirected PyGraph object from the PyDiGraph object.
- A new kwarg, bidirectional, was added to the directed generator
  functions directed_cycle_graph(), directed_path_graph(), and
  directed_star_graph(). When set to True the directed graphs generated
  by these functions will add edges in both directions.
- Added two new functions, is_weakly_connected() and
  weakly_connected_components(), which will either check if a PyDiGraph
  object is weakly connected or return the list of the weakly connected
  components of an input PyDiGraph.
- The weight_fn kwarg for graph_adjacency_matrix(),
  digraph_adjacency_matrix(), graph_floyd_warshall_numpy(),
  and digraph_floyd_warshall_numpy() is now optional. Previously it
  always had to be specified when calling these function. But instead
  you can now rely on a default weight float (which defaults to 1.0) to be
  used for all the edges in the graph.
- Add a neighbors() method to PyGraph and PyDiGraph. This function will
  return the node inidices of the neighbor nodes for a given input node.
- Two new methods, successor_indices() and predecessor_indices(), were
  added to PyDiGraph. These methods will return the node indicies for
  the successor and predecessor nodes of a given input node.
- Two new functions, graph_distance_matrix() and
  digraph_distance_matrix(), were added for generating a distance matrix
  from an input PyGraph and PyDiGraph.
- Two new functions, digraph_dijkstra_shortest_paths() and
  graph_dijkstra_shortest_path(), were added for returning the shortest
  paths from a node in a PyDiGraph and a PyGraph object.
- Two new methods, insert_node_on_in_edges() and
  insert_node_on_out_edges(), were added to PyDiGraph. These functions
  are used to insert an existing node in between an reference node and
  all it's predecessors or successors.
- Two new functions, graph_dfs_edges() and digraph_dfs_edges(), were
  added to get an edge list in depth first order from a PyGraph and
  PyDiGraph.

Upgrade
-------
- The numpy arrays returned by graph_floyd_warshall_numpy(),
  digraph_floyd_warshall_numpy(), digraph_adjacency_matrix(),
  and graph_adjacency_matrix() will now be in a contiguous C array
  memory layout. Previously they would return arrays in a column-major
  fortran layout. This was change was made to make it easier to
  interface the arrays returned by these functions with other C
  Python extensions. There should be no change when interacting with the
  numpy arrays via numpy's API.
- The bfs_successors method now returns an object of a custom type
  BFSSuccessors instead of a list. The BFSSuccessors type implements the
  Python sequence protocol so it can be used in place like a list
  (except for where explicit type checking is used). This was done to
  defer the type conversion between Rust and Python since doing it all
  at once can be a performance bottleneck especially for large graphs.
  The BFSSuccessors class will only do the type conversion when an
  element is accessed.

Fixes
-----
- When pickling PyDiGraph objects the original node indices will be
  preserved across the pickle.
- The random gnp functions, directed_gnp_random_graph() and
  undirected_gnp_random_graph(), will now also handle exact 0 or 1
  probabilities. Previously it would fail in these cases. Fixes Qiskit#172

0.5.0

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.5.0

This release include a number of new features and bug fixes. The main
focus of the improvements of this release was to increase the ease of interacting with graph objects. This includes adding support for generating dot
output which can be used with graphviz (or similar tools) for visualizing
graphs adding more methods to query the state of graph, adding a generator
module for easily creating graphs of certain shape, and implementing the
mapping protocol so you can directly interact with graph objects.

Added
-----
- A new method, to_dot(), was added to PyGraph and PyDiGraph. It will
  generate a dot format representation of the object which can be used
  with Graphivz (or similar tooling) to generate visualizations of the
  graph.
- Added a new function, strongly_connected_components(), to get the list
  of strongly connected components of a PyDiGraph object.
- A new method, compose(), for combing another graph object of the same
  type was added to PyGraph and PyDiGraph.
- The PyGraph and PyDigraph classes now implement the Python mapping
  protocol for interacting with graph nodes. You can now access and
  interact with node data directly by using standard map access patterns
  in python. For example, running 'graph[1]' will return the data for the
  index at node 1.
- A new module, retworkx.generators, has been added. Functions in this
  module can be used for quickly generating graphs of certain shape.
- A new method, remove_node_retain_edges(), has been added to the
  PyDiGraph class. This method can be used to remove a node and add
  edges from its predecesors to its successors.
- Two new methods, edge_list() and weighted_edge_list(), for getting a
  list of tuples with the edge source and target (with or without edge
  weights) have been added to PyGraph and PyDigraph.
- A new function, cycle_basis(), for getting a list of cycles which form
  a basis for cycles of a PyGraph object.
- Two new functions, graph_floyd_warshall_numpy() and
  digraph_floyd_warshall_numpy(), were added for running the Floyd Warshall
  algorithm and returning all the shortest path lengths as a distance
  matrix.
- A new constructor method, read_edge_list(), has been added to PyGraph and
  PyDigraph. This method will take in a path to an edge list file and
  will read that file and generate a new object from the contents.
- A new method, extend_from_edge_list(), has been added to PyGraph and
  PyDiGraph. This method takes in an edge list and will add both the edges and
  nodes (if a node index used doesn't exist yet) in the list to the graph.

Fixes
-----

- The limitation with is_isomorphic() and is_isomorphic_node_match() functions
  that would cause segfaults when comparing graphs with node removals
  has been fixed. You can now run either function with any
  PyDiGraph/PyDAG objects, even if there are node removals. Fixes Qiskit#27
- If an invalid node index was passed as part of the first_layer
  argument to the layers() function

0.4.0

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.4.0

This release includes many new features and fixes, included improved
performance and better documentation. But, the biggest change for this
release is that this is the first release of retworkx that supports
compilation with a stable released version of rust. This was made
possible thanks to all the hard work of the PyO3 maintainers and
contributors in the PyO3 0.11.0 release.

Added
-----

- A new class for undirected graphs, PyGraph, was added.
- 2 new functions graph_adjacency_matrix() and
  digraph_adjacency_matrix() to get the adjacency matrix of a PyGraph
  and PyDiGraph object.
- A new PyDiGraph method, find_adjacent_node_by_edge(), was added. This is
  used to locate
- New methods, add_nodes_from(), add_edges_from(),
  add_edges_from_no_data(), and remove_nodes_from() were added to PyDiGraph
  (and PyGraph). These methods allow for the addition (and removal) of
  multiple nodes or edges from a graph in a single call.
- A new function, graph_greedy_coloring(), which is used to return a
  coloring map from the
- 2 new functions, graph_astar_shortest_path and digraph_astar_shortest_path(),
  to find the shortest path from a node to a specified goal using the A*
  search algorithm.
- 2 new functions, graph_all_simple_paths() and
  digraph_all_simple_paths(), to return a list of all the simple paths
  between 2 nodes in a PyGraph or PyDiGraph object.
- 2 new functions, directed_gnp_random_graph() and
  undirected_gnp_random_graph(), to generate Gnp random PyDiGraph and
  PyGraph objects.
- 2 new functions, graph_dijkstra_shortest_path and
  digraph_dijkstra_shortest_path, were added for find the shortest paths
  between nodes in PyGraph or PyDiGraph object using Dijkstra's
  algorithm.

Changed
-------

- The PyDAG class was renamed PyDiGraph to better reflect it's
  functionality. For backwards compatibility PyDAG still exists as a python
  subclass of PyDiGraph. No changes should be required for existing
  users.
- numpy is now a dependency of retworkx. This is used for the adjacency
  matrix functions to return numpy arrays. The minimum version of numpy
  supported is 1.16.0.

Fixes
-----

- The retworkx exception classes are now properly exported from the
  retworkx module. In prior releases it was not possible to import the
  exception classes (normally to catch one being raised) requiring users
  to catch the base Exception class. This has been fixed so a
  specialized retworkx exception class can be used.

0.3.4

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.3.4

0.3.3

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.3.3

0.3.2

Verified

This tag was signed with the committer’s verified signature.
mtreinish Matthew Treinish
Release 0.3.2

This release includes a performance fix on the ancestors() and
descendants() functions. It also changes the return type from those
functions to be a set instead of a list.