qiskit / rustworkx Goto Github PK
View Code? Open in Web Editor NEWA high performance Python graph library implemented in Rust.
Home Page: https://www.rustworkx.org
License: Apache License 2.0
A high performance Python graph library implemented in Rust.
Home Page: https://www.rustworkx.org
License: Apache License 2.0
Just like in #20 it would be good to have an undirected graph class so that we have coverage for use cases that require undirected graphs.
All the docs reference this as a replacement for the python networkx library. Is there a pure Rust interface available free of Python dependencies? If so some documentation about it would be helpful. If not, then this would be semi-related to #33 to add a native Rust interface.
There's a weird API in Terra that dag.bfs_successors(node)
returns a tuple of (node, node_successors)
. I don't know why this was introduced but the first element of the tuple is never used (it's the function argument itself). I tried to fix this but this has now been baked into retworkx, so it needs to be fixed in retworkx first.
As a general rule I think retworkx API should mirror networkx, not how terra's dagcircuit happens to use it.. This allows us to write the same shim to interface both.
Right now retworkx doesn't have an is_weakly_connected()
function, there is a number_weakly_connected_components
function which returns the number of weakly connected components in a PyDiGraph, but we don't have a function to return whether the entire graph is weakly connected or not. As part of this it will probably be necessary to add a function to actually get the weakly connected components too, since the petgraph function number_weakly_connected_components
uses only returns a count.
Subclassing fails the PyDiGraph
fails. A minimal example:
from retworkx import PyDiGraph
class A(DiGraph):
def __init__(self, ):
super().__init__()
a=A('s')
One should be able to subclass the PyDiGraph
See the minimal example above
This is to add new functions to retworkx's algorithm library to get a k-core number dictionary from a graph. This is similar to networkx's core_number
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.core.core_number.html or graph_tool's kcore_decomposition
: https://graph-tool.skewed.de/static/doc/topology.html?highlight=kcore_decomposition#graph_tool.topology.kcore_decomposition
In #121 we added a new module for graph generators which will create graphs of with a certain layout easily. #121 only added a few different types of graphs with the intention of adding more in the future. We should add more generators to the graph to offer more options for quickly creating graphs. Networkx has a long list of generators that can be used for inspiration on different types of generators to add:
https://networkx.github.io/documentation/stable/reference/generators.html
Also, specifically for a qiskit use case we should make sure that we have generators to cover (this was handled by #191)qiskit.transpiler.CouplingMap.from_line
, qiskit.transpiler.CouplingMap.from_ring
, qiskit.transpiler.CouplingMap.from_grid
, and qiskit.transpiler.CouplingMap.from_full
After #267 fixes the issues we had the stable graph and vf2 we should expand the isomorphism apis to cover a wider use case. Right now retworkx has 2 functions is_isomorphism
and is_isomorphism_node_match
which only works with the PyDiGraph
class. We should expand these to include functions for PyGraph
and also for edge matching too. This will require updating the dag isomorphism module to work with petgraph traits instead of fixed type PyDiGraph.
It might make sense to combine the functions and just make 2 is_isomorphic functions (one for PyGraph the other for PyDiGraph) that have optional kwargs for node and edge matching functions. The one thing we'll need to keep in mind is backwards compatibility because we can't break existing users passing PyDiGraph
objects to retworkx.is_isomorphic
and retworkx.is_isomorphic_node_matching
so if we change the python functions exposed by rust we'll likely need compatibility wrapper functions in the python to adapt existing users to the new way.
As retworkx continues to grow the number of algorithm functions we offer has grown substantially. Right now we have been putting standalone functions just in lib.rs
except where the implementation was either forked from petgraph and modified (and done in a separate module to provide attribution) or when the implementation was large enough that it justified it's own file. But this has led the lib.rs file getting quite large and a bit disorderly. To make it easier to find the code for the different functions we probably should start looking at splitting lib.rs into separate modules.
This is to start a discussion around what structure we should pick (ie function by type of algorithm, by graph type, by type of algorithm and graph type, etc) and start to organize things a bit into rust submodules (and also update the docs accordingly). Ideally I think that we still want to have the root retworkx
python namespace still have all the functions present so lib.rs would probably just just contain the pymodule and be where we export the various pieces to python.
Right now qiskit-terra is still using networkx for its CouplingMap
class This issue is to track all the work necessary in retworkx until qiskit-terra can convert its CouplingMap
class to use retworkx. The following functionality is missing:
While retworkx has a random G_n,p graph functions there are some use cases for a random G_n,m graphs. Specifically: https://github.com/Qiskit/qiskit-terra/blob/01ded73d1ded2342e39bc22d994ba0b50ffc8de7/test/python/transpiler/test_token_swapper.py#L105 We should add this to retworkx too. This could be part of #150 but opening as a a separate issue since it's a feature gap for terra (well terra's tests at least).
Add functions to calculate PageRank and HITS to expand the retworkx's link analysis capabilities.
These algorithms are popular among users of graph libraries, and also appear frequently in benchmarks. The hope by adding those algorithms is to make retworkx appeal to more users and become more popular.
For inspiration, our functions couls have an API that is similar to networkx's Link Analysis API:
Networkx has a robust function to draw graphs using matplotlib
We should add an equivalent tool for retworkx, but this function should be an optional extra.
Add functions that make a random walk on a graph, which could be both a biased or an unbiased random walk.
This may be important for some network science applications.
In my opinion, this would be done by two functions:
random_walk
for the unbiased random walk;biased_random_walk
for the biased random walk.The existing directed_* generator functions in https://github.com/Qiskit/retworkx/blob/master/src/generators.rs only have an option to add a single edge. But it could be useful to add edges in both directions. While this is essentially the same as a undirected version of the function there are use cases where you could want bidirectional edges added to a directed graph generatore. For example a bidirectional path graph: a <-> b <-> c
instead of just a -> b -> c
that exists now. This would be to add a new boolean kwarg to the existing (and potential future) directed generator functions to set adding bidirectional edges.
This is related to #150 but self contained enhancement for the existing generator functions rather than adding new functions.
A method will be added to the PyGraph class which can simultaneously remove multiple edges.
The PyGraph class has the method remove_nodes_from
which accepts multiple indices to remove in a single call. However, there is no corresponding remove_edges_from
to remove multiple edges. Are there any implementation details preventing this method from existing?
I don't think retworkx uses iterators, the same way networkx does? This might lead to very large memory usage for large graphs (and possibly hurt time too).
For example often you want a shallow view into the immediate successors of a node, not all the nodes that may succeed it until the end. Same for layers of a dag.
Networkx implements this an an iterator. Terra also uses this as an iterator.
But I think retworkx constructs the full list, and only artificially returns an iterator in terra.
For an example of how this can be problematic for large circuits, see this PR in terra: Qiskit/qiskit#371
Networkx has a spring_layout
function which returns a layout for nodes in the graph (which can be used for drawing):
and the code for this networkx function is:
We should add an equivalent function to retworkx. (it might also be good to add simpler layout functions first)
Add function(s) to retworkx's algorithm library for calculating the betweenness centrality for nodes and edges. This is similar to networkx's betweenness_centrality
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.betweenness_centrality.html and edge_betweenness_centrality
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.edge_betweenness_centrality.html
or graph-tool's betweenness
https://graph-tool.skewed.de/static/doc/centrality.html#graph_tool.centrality.betweenness
Add functions to get the transitivity of a graph. Similar to networkx's transitivity
method: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cluster.transitivity.html or graph-tool's global_clustering
: https://graph-tool.skewed.de/static/doc/clustering.html?highlight=global_clustering#graph_tool.clustering.global_clustering
Add an equivalent of networkx's random_geometric_graph
function to be added to retworkx:
This is needed for converting qiskit-optimization to use retworkx internally, for example:
Currently the Python unittests for retworkx lack a cohesive organizational structure. As pointed out in #144 there is a mix of some tests splitting across tests/
and tests/graph
for tests using PyDiGraph
/PyDAG
and PyGraph
, while others just put all the tests in the same file under tests/
normally using 2 test classes. We really should make these consistent, so either split all tests into subdirectories by the class being tested or have a single module per function and test both classes in that module with a separate test classes. Which pattern we adopt doesn't matter so much as long as its consistent for all tests.
In #78 we changed the hashmap implementation to use hashbrown for performance, but also to get
potential access to parallel iterators. In general though using rayon https://github.com/rayon-rs/rayon could provide a speed-up for places where we're in pure rust code. Especially for things like sorts where there are drop in parallel replacements from rayon (ie replace .sort_by_key()
with .par_sort_by_key
https://docs.rs/rayon/1.3.0/rayon/slice/trait.ParallelSliceMut.html#method.par_sort_by_key. We should investigate using rayon to speed up execution where it makes sense.
Retworkx is missing functionality equivalent to networkx's find_cycle
method: https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles.find_cycle.html
while retworkx does have cycle_basis
functions it doesn't have a method to find cycles from arbitrary nodes. However, to start the retworkx functions added don't need to have the same level of flexibility as networkx's. The immediate use case for this is: https://github.com/Qiskit/qiskit-terra/blob/779fa14d4452e35306ca849d98e56f8aa40d14be/qiskit/transpiler/passes/routing/algorithms/token_swapper.py#L160 which only cares about finding a cycle from a source node without an orientation. If the need arises after that is added we can always expand it later.
When the project was first started it made sense to try and use a DAG library implementation to get something out fast. But using the daggy project wasn't necessarily the best choice since it lags behind petraph and hasn't had a release in ~2 years. With the new release of petgraph 0.5 it would be better to just use a directed stable_graph from that and add our own cycle detection on modifier operations. This will also give us more flexibility in the future since we control more of the underlying data structure.
In the tests added for #229 two utility functions, is_matching
and is_maximal_matching
were ported from networkx to work with retworkx (in python) and validate the result. We should include these functions to be native retworkx functions (in rust) and expose them through the retworkx api (and also update the tests to use that version instead).
qiskit-terra is the primary users of retworkx at this point. It'd be good to verify that any changes made to repo don't cause any breakages for them (or at least without proper deprecation so that they can have time to adjust) as we add them. So it would probably be valuable to set up a CI job that runs qiskit-terra's unittests so we can ensure this.
Add an equivalent function to networkx.complement()
to retworkx.
This is needed for converting qiskit-optimization to use retworkx internally:
retworkx is missing a max_weight_matching()
function, similar to networkx's function: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.max_weight_matching.html?highlight=max_weight_matching#networkx.algorithms.matching.max_weight_matching
This is currently a blocker from removing the last networkx usage from qiskit in qiskit-ignis. Specifically this function is used here:: https://github.com/Qiskit/qiskit-ignis/blob/master/qiskit/ignis/verification/topological_codes/fitters.py#L298
Add a retworkx algorithm function for the PatternMatch
algorithm from: https://arxiv.org/pdf/1909.05270.pdf
In qiskit terra there is a python implementation of this algorithm built using an inner retworkx PyDiGraph
. Specifically it uses a DAGDependency
data structure: https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/dagcircuit/dagdependency.py which is built on a PyDiGraph
and uses that to run the algorithm here: https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/passes/optimization/template_matching/template_matching.py ideally we'd be able to replace most of terra implementation with a retworkx function.
For places in the algorithm that look at the attributes of a vertex we'll need to rely on python callback functions that will be passed the vertex object and return the data in a format retworkx can use (you can refer to other algorithm functions like max_weight_matching
, floyd_warshall_numpy
, etc for examples of this), but we might need multiple different functions passed to retworkx.
Right now I can't use this library since the class names are different from NetworkX and there's no reason they should be.
If the rest of the API matches, I can offer this as an extra in my package.
Currently, many methods require prefixing the name with the type of the graph (i.e. digraph_
). Would it be possible to dispatch the right method based on the type of the graph automatically? This arose in a discussion on a prior PR (Qiskit/qiskit#5471 (comment)).
One pythonic way to implement this would be to switch on the type, if implementing this in Rust is a problem. Then the right Rust method may be called by the Python code.
I was helping someone install this library and realized that they had macOS 10.12 + Conda Python 3.7, and couldn't pull the wheels since they are 10.13+ (intel) and 10.15+ (normal). Could the MACOSX_DEPLOYMENT_TARGET
be set to 10.12 or 10.9? I'm guessing it is not set at all, due to the 10.15 in the wheel. If not, is there a reason it can't be lowered?
Implement all_pairs_dijkstra_path
and all_pairs_dijkstra_path_length
The equivalent functions in networkx are: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path.html and https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path_length.html
These functions are basically a for loop over all nodes in the dijkstra_shortest_paths
and dijkstra_shortest_path_lengths
functions. Ideally we should implement these for loops in parallel using rayon but the complication will be in getting the edge weights since we will need a python callback function. I'm thinking we can just graph all the edge weights once up front to a Vec
and then use a parallel for loop with rayon calling dijkstra's on each iteration and for weights just do a lookup.
Add a minimum spanning tree function to retworkx's algorithm library. Something like networkx's minimum_spanning_tree
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_tree.html
Right now we only have the PyDAG class. This was written with qiskit-terra's DAGCircuit class in mind which doesn't assign a numeric weight to anything in the graph. However, there are potential use cases which might require traversal that factors in weight. Technically you could do this today by just making the data for nodes and edges integers, but because the data is treated as an opaque python object in most places this won't work for algorithms which are dependent on the weight since it would slow things down signifcantly to call out to python for integer comparisons.
The compromise I'm thinking of drawing here is to add alternative classes for example PyDAGWeighted
that enables setting a weight integer. For this implementation we either track the node/edge data or weights in a couple of HashMaps in the structs so that for algorithms can look either up by ids when needed. This should any minimize performance impact and enable using weights as part of traversal algorithms.
In #304 we're adding a matplotlib based drawer to retworkx, which is standalone python code that just builds on the retworkx functionality and matplotlib is an optional dependency. Since retworkx has had a graphviz dot generator since #103 we should expand the built in visualizers to have pydot_draw()
function in the new retworkx.visualization
module (after #304 merges).
This would basically just be a prebuilt function version of the docstring we have on all the generator functions. Something like:
import os
import tempfile
import pydot
from PIL import Image
import retworkx.generators
def pydot_draw(graph):
graph = retworkx.generators.directed_cycle_graph(5)
dot_str = graph.to_dot(
lambda node: dict(
color='black', fillcolor='lightblue', style='filled'))
dot = pydot.graph_from_dot_data(dot_str)[0]
with tempfile.TemporaryDirectory() as tmpdirname:
tmp_path = os.path.join(tmpdirname, 'dag.png')
dot.write_png(tmp_path)
image = Image.open(tmp_path)
os.remove(tmp_path)
return image
where obviously we either options for callback functions passed to to_dot()
and different io options (like filename, file type, etc). Then we'll also need to add pydot and pillow as optional dependencies.
There is no method (short of going over the edge list manually in python) to take a PyDiGraph
object with directed edges and generating a PyGraph
object from it with undirected edges. We should have a to_undirected
method for a PyDiGraph
that will treat every edge in the graph as undirected and generate a new PyGraph
object from it.
Function neighbors()
returns an iterator producing repeated indices in multigraphs.
Function neighbors()
should return an iterator generating unique indices.
Issue Qiskit/qiskit#5530 illustrates the problem.
There are some networkx uses cases in qiskit-terra that are outside of the DAGCircuit
class. Mainly the coupling map and the noise aware layout class. Exposing a PyDiGraph
class will be straightforward because it's essentially identical to PyDAG
except we don't need or want any cycle checks as part of adding new nodes (and a few places in the logic where things are shortcut because we assume no cycles).
This should be achievable by making the inner graph struct on PyDAG
a PyDiGraph
and then for the method impl just call the method on the inner PyDiGraph
and return that. The exception being where we need dag specifics.
Several methods on terra's DAGCircuit
implement some variant of graph composition by topologically sorting one of the input graphs and appending its nodes to the other, one by one. (See e.g. DAGCircuit.compose
). The downside of this approach is that the number of operations grows as the number of nodes in the sorted graph. If the sorted DAGCircuit
is shorter than it is wide, this is probably actually preferable. Another option for implementing DAG composition is removing output nodes from one circuit, input nodes from the other, and directly adding edges between them. This will scale as the number of qubits, not the number of nodes, which would be preferable if both graphs are longer than they are wide.
In networkx, implementing this style of composition is difficult because each graph is implemented on top of its own dictionary, so there is no way easy way to add edges between the graphs. (There are a handful of ways this might actually be possible, e.g. a globally unique node_id and hacking a dictionary merge on _multi_graph._adj
, or if all of our DAGCircuits live as disjoint subgroups inside a single networkx graph, ... but each of these approaches sound likely to cause more problems than they solve.) Is implementing a more efficient composition any simpler in retworkx?
To enable interfacing retworkx python objects with other languages directly instead of going through python for better performance we should add a foreign function interface and publish header files.
Calling either undirected_gnp_random_graph(num_nodes, probability)
or directed_gnp_random_graph(num_nodes, probability)
for probability= 0 or 1 throws an error.
The expected behavior is to match that of networkx, where passing 0 for the probability returns an empty graph and passing 1 for the probability returns a full graph
Call either retworkx.undirected_gnp_random_graph(n,p)
or retworkx.directed_gnp_random_graph(n,p)
with p=0 or p=1.
The VF2 implementation in dag_isomorphism.rs
was forked from the upstream petgraph project and modified to handle PyDiGraph
. As was previously reported in #27 and worked around in #115 that implementation didn't work with the petgraph StableGraph
type used in retworkx on node removals because there could be holes in the list of node ids (so that node_bound()
on 2 isomorphic graphs aren't the same) which isn't possible in the petgraph Graph
type but is in StableGraph
. This was causing a hard failure in the isomorphism functions if a node was removed from a PyDiGraph
obejct and was worked around in #115. However, this workaround introduces overhead in the case of node removals because it is cloning and reindexing the graph to not have holes in the index list. The next step here is to reimplement the vf2 algorithm to natively handle holes in the node index so that we don't need this cloning and reindexing step.
It also would probably be good to push an improved vf2 back upstream to petgraph after it is implemented here. We'll still need the local fork in retworkx, but if we fix VF2 support for StableGraph we should make sure to contribute that back to petgraph too.
retworkx::dag_isomorphism::is_isomorphic_matching was written by copy and pasting petgraph's isomorphism functions and changing the input type to be PyDAG instead of petgraph's Graph
. However, the code wasn't 100% compatible as originally assumed because of node removals. The function assumes that an isomorphic graph will always have the same number of node indexes, however in the case of petgraph's StableGraph
(which PyDAG uses internally) this is not the case. A stable graph's number of indexes increases on each node add, and if a node is removed the old index is not used again, unlike Graph
. This will cause a panic like: thread '<unnamed>' panicked at 'index out of bounds: the len is 4 but the index is 4'
when trying to compare a graph with removals to a graph without any.
A temporary workaround for this is to use deepcopy (or pickle and unpickle) the pydags. This will reset the index counters so they'll be the same. This is not a great answer, it's just a workaround until the function is updated.
In qiskit-terra there is a transpiler pass collect2q blocks which primarily consists of a graph traversal. Doing the actual graph traversal and search will be much faster in retworkx, so we should add a function that can be used in place of terra's python version. The terra function code is:
This is similar to collect_runs which already has a native retworkx version:
and will operate in a similar manner with a filter function argument except it will collect 2q blocks instead of 1q runs.
$ RUST_BACKTRACE=full python -m unittest test.python.transpiler.test_dag_fixed_point_pass.TestFixedPointPass.test_empty_dag_true
thread '<unnamed>' panicked at 'called `Option::unwrap()` on a `None` value', src/digraph.rs:379:33
stack backtrace:
0: 0x1239f089f - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h87f791d1934b5da0
1: 0x123a086de - core::fmt::write::h23c8f27116676cdf
2: 0x1239eeb17 - std::io::Write::write_fmt::h1f00d7a43839acf0
3: 0x1239f271a - std::panicking::default_hook::{{closure}}::hf26168ecfd2fc8c1
4: 0x1239f245c - std::panicking::default_hook::hf7eb684688e3f257
5: 0x1239f2dc8 - std::panicking::rust_panic_with_hook::hba1377a258e49bd5
6: 0x1239f2962 - rust_begin_unwind
7: 0x123a079ff - core::panicking::panic_fmt::h0d0a3efb6be37d9e
8: 0x123a07957 - core::panicking::panic::hf3ac1465281c1515
9: 0x1239a2f3c - retworkx::digraph::PyDiGraph::__setstate__::h00a802b2ce6e3b2a
10: 0x123972776 - std::panicking::try::do_call::h5df5eab4fe64c6c6
11: 0x1239f43ab - __rust_maybe_catch_panic
12: 0x1239aa3e1 - retworkx::digraph::__init9430999800510378281::__init9430999800510378281::__wrap::h02b791606df91a8c
13: 0x1046a740b - _PyCFunction_FastCallDict
14: 0x10473832a - call_function
15: 0x1047352c2 - _PyEval_EvalFrameDefault
16: 0x104738f13 - _PyEval_EvalCodeWithName
17: 0x10472ef07 - PyEval_EvalCodeEx
18: 0x104684bff - function_call
19: 0x1046592b5 - PyObject_Call
20: 0x1047354bb - _PyEval_EvalFrameDefault
21: 0x104738f13 - _PyEval_EvalCodeWithName
22: 0x10473972b - fast_function
23: 0x1047382f9 - call_function
24: 0x1047352c2 - _PyEval_EvalFrameDefault
25: 0x104738f13 - _PyEval_EvalCodeWithName
26: 0x10473972b - fast_function
27: 0x1047382f9 - call_function
28: 0x1047352c2 - _PyEval_EvalFrameDefault
29: 0x104738f13 - _PyEval_EvalCodeWithName
30: 0x10473972b - fast_function
31: 0x1047382f9 - call_function
32: 0x1047352c2 - _PyEval_EvalFrameDefault
33: 0x104738f13 - _PyEval_EvalCodeWithName
34: 0x10472ef07 - PyEval_EvalCodeEx
35: 0x104684bff - function_call
36: 0x1046592b5 - PyObject_Call
37: 0x1047354bb - _PyEval_EvalFrameDefault
38: 0x104738f13 - _PyEval_EvalCodeWithName
39: 0x10473972b - fast_function
40: 0x1047382f9 - call_function
41: 0x1047352c2 - _PyEval_EvalFrameDefault
42: 0x1047397c9 - fast_function
43: 0x1047382f9 - call_function
44: 0x1047352c2 - _PyEval_EvalFrameDefault
45: 0x1047397c9 - fast_function
46: 0x1047382f9 - call_function
47: 0x1047352c2 - _PyEval_EvalFrameDefault
48: 0x104739ca6 - _PyFunction_FastCallDict
49: 0x104659476 - _PyObject_FastCallDict
50: 0x10465960c - _PyObject_Call_Prepend
51: 0x1046592b5 - PyObject_Call
52: 0x1047354bb - _PyEval_EvalFrameDefault
53: 0x104738f13 - _PyEval_EvalCodeWithName
54: 0x10473972b - fast_function
55: 0x1047382f9 - call_function
56: 0x1047352c2 - _PyEval_EvalFrameDefault
57: 0x1047397c9 - fast_function
58: 0x1047382f9 - call_function
59: 0x1047352c2 - _PyEval_EvalFrameDefault
60: 0x1047397c9 - fast_function
61: 0x1047382f9 - call_function
62: 0x1047352c2 - _PyEval_EvalFrameDefault
63: 0x1047397c9 - fast_function
64: 0x1047382f9 - call_function
65: 0x1047352c2 - _PyEval_EvalFrameDefault
66: 0x104738f13 - _PyEval_EvalCodeWithName
67: 0x10473972b - fast_function
68: 0x1047382f9 - call_function
69: 0x1047352c2 - _PyEval_EvalFrameDefault
70: 0x104738f13 - _PyEval_EvalCodeWithName
71: 0x104739b1b - _PyFunction_FastCallDict
72: 0x104659476 - _PyObject_FastCallDict
73: 0x10465960c - _PyObject_Call_Prepend
74: 0x1046592b5 - PyObject_Call
75: 0x1047354bb - _PyEval_EvalFrameDefault
76: 0x104738f13 - _PyEval_EvalCodeWithName
77: 0x104739b1b - _PyFunction_FastCallDict
78: 0x104659476 - _PyObject_FastCallDict
79: 0x10465960c - _PyObject_Call_Prepend
80: 0x1046592b5 - PyObject_Call
81: 0x1046bf969 - slot_tp_call
82: 0x104659501 - _PyObject_FastCallDict
83: 0x1047382a2 - call_function
84: 0x1047352c2 - _PyEval_EvalFrameDefault
85: 0x104738f13 - _PyEval_EvalCodeWithName
86: 0x104739b1b - _PyFunction_FastCallDict
87: 0x104659476 - _PyObject_FastCallDict
88: 0x10465960c - _PyObject_Call_Prepend
89: 0x1046592b5 - PyObject_Call
90: 0x1047354bb - _PyEval_EvalFrameDefault
91: 0x104738f13 - _PyEval_EvalCodeWithName
92: 0x104739b1b - _PyFunction_FastCallDict
93: 0x104659476 - _PyObject_FastCallDict
94: 0x10465960c - _PyObject_Call_Prepend
95: 0x1046592b5 - PyObject_Call
96: 0x1046bf969 - slot_tp_call
97: 0x104659501 - _PyObject_FastCallDict
98: 0x1047382a2 - call_function
99: 0x1047352c2 - _PyEval_EvalFrameDefault
100: 0x104738f13 - _PyEval_EvalCodeWithName
101: 0x104739b1b - _PyFunction_FastCallDict
102: 0x104659476 - _PyObject_FastCallDict
103: 0x10465960c - _PyObject_Call_Prepend
104: 0x1046592b5 - PyObject_Call
105: 0x1047354bb - _PyEval_EvalFrameDefault
106: 0x104738f13 - _PyEval_EvalCodeWithName
107: 0x104739b1b - _PyFunction_FastCallDict
108: 0x104659476 - _PyObject_FastCallDict
109: 0x10465960c - _PyObject_Call_Prepend
110: 0x1046592b5 - PyObject_Call
111: 0x1046bf969 - slot_tp_call
112: 0x104659501 - _PyObject_FastCallDict
113: 0x1047382a2 - call_function
114: 0x1047352c2 - _PyEval_EvalFrameDefault
115: 0x1047397c9 - fast_function
116: 0x1047382f9 - call_function
117: 0x1047352c2 - _PyEval_EvalFrameDefault
118: 0x1047397c9 - fast_function
119: 0x1047382f9 - call_function
120: 0x1047352c2 - _PyEval_EvalFrameDefault
121: 0x104738f13 - _PyEval_EvalCodeWithName
122: 0x104739b1b - _PyFunction_FastCallDict
123: 0x104659476 - _PyObject_FastCallDict
124: 0x10465960c - _PyObject_Call_Prepend
125: 0x1046592b5 - PyObject_Call
126: 0x1046c088f - slot_tp_init
127: 0x1046bc884 - type_call
128: 0x104659501 - _PyObject_FastCallDict
129: 0x1046598f5 - _PyObject_FastCallKeywords
130: 0x1047382a2 - call_function
131: 0x104735355 - _PyEval_EvalFrameDefault
132: 0x104738f13 - _PyEval_EvalCodeWithName
133: 0x10472eec0 - PyEval_EvalCode
134: 0x10472c5e7 - builtin_exec
135: 0x1046a72d6 - _PyCFunction_FastCallDict
136: 0x10473832a - call_function
137: 0x1047352c2 - _PyEval_EvalFrameDefault
138: 0x104738f13 - _PyEval_EvalCodeWithName
139: 0x10473972b - fast_function
140: 0x1047382f9 - call_function
141: 0x1047352c2 - _PyEval_EvalFrameDefault
142: 0x104738f13 - _PyEval_EvalCodeWithName
143: 0x10472ef07 - PyEval_EvalCodeEx
144: 0x104684bff - function_call
145: 0x1046592b5 - PyObject_Call
146: 0x104784993 - RunModule
147: 0x1047841aa - Py_Main
148: 0x10464df78 - main
.Traceback (most recent call last):
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/runpy.py", line 193, in _run_module_as_main
"__main__", mod_spec)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/runpy.py", line 85, in _run_code
exec(code, run_globals)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/__main__.py", line 18, in <module>
main(module=None)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/main.py", line 95, in __init__
self.runTests()
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/main.py", line 256, in runTests
self.result = testRunner.run(self.test)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/runner.py", line 176, in run
test(result)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/suite.py", line 84, in __call__
return self.run(*args, **kwds)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/suite.py", line 122, in run
test(result)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/suite.py", line 84, in __call__
return self.run(*args, **kwds)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/suite.py", line 122, in run
test(result)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/unittest/case.py", line 653, in __call__
return self.run(*args, **kwds)
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/test/base.py", line 342, in run
return run_test.run(result)
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/test/runtest.py", line 106, in run
return self._run_one(actual_result)
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/test/runtest.py", line 119, in _run_one
return self._run_prepared_result(ExtendedToOriginalDecorator(result))
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/test/runtest.py", line 132, in _run_prepared_result
self._run_core()
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/test/runtest.py", line 170, in _run_core
self.case._run_test_method, self.result):
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/test/runtest.py", line 213, in _run_user
return fn(*args, **kwargs)
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/test/base.py", line 225, in _run_test_method
return self._get_test_method()()
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/test/python/transpiler/test_dag_fixed_point_pass.py", line 32, in test_empty_dag_true
pass_.run(dag)
File "/Users/kevin.krsulichibm.com/q/qiskit-terra/qiskit/transpiler/passes/utils/dag_fixed_point.py", line 36, in run
self.property_set['_dag_fixed_point_previous_dag'] = deepcopy(dag)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/copy.py", line 180, in deepcopy
y = _reconstruct(x, memo, *rv)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/copy.py", line 280, in _reconstruct
state = deepcopy(state, memo)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/copy.py", line 150, in deepcopy
y = copier(x, memo)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/copy.py", line 240, in _deepcopy_dict
y[deepcopy(key, memo)] = deepcopy(value, memo)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/copy.py", line 180, in deepcopy
y = _reconstruct(x, memo, *rv)
File "/Users/kevin.krsulichibm.com/.pyenv/versions/3.6.10/lib/python3.6/copy.py", line 282, in _reconstruct
y.__setstate__(state)
pyo3_runtime.PanicException: called `Option::unwrap()` on a `None` value
Publish a version of retworkx which supports Apple's new M1 chip so it can be installed via pip.
Right now retworkx doesn't have a shortest_path
function to return the shortest path between 2 nodes in a graph. There a several shortest path length functions that return the shortest path length between nodes. We should add a retworkx.graph_shortest_path
and retworkx.digraph_shortest_path
functions that will return the path as node indices from a source to the target node. One thing to mention here is that for the directed graph function there should be an option to treat edges as undirected/bidirectional so that a user can find the undirected shortest path between nodes.
We have 2 implementations of the floyd warshall algorithm, one using ndarray/numpy and the other using dictionaries and looping over the graph objects.Right now they're both serially executed and as the graphs grow hit some scaling limits. We should look at adding parallel implementations of these algorithms, especially for the ndarray/numpy based one using:
https://en.wikipedia.org/wiki/Parallel_all-pairs_shortest_path_algorithm#Floyd_algorithm
since after we get the initial adjacency matrix there is no python involvement so we can easily parallelize the function.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.