Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add weighted graph types #32

Closed
mtreinish opened this issue Feb 26, 2020 · 2 comments
Closed

Add weighted graph types #32

mtreinish opened this issue Feb 26, 2020 · 2 comments
Labels
enhancement New feature or request

Comments

@mtreinish
Copy link
Member

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.

@mtreinish mtreinish added the enhancement New feature or request label Feb 26, 2020
@mtreinish
Copy link
Member Author

I'm not sure there is going to actually be a need for this moving forward. We can use a python callback to return a fixed type that has a built in pyo3 conversion to a rust type for algorithms that need a weight. For example, what I did with the weight_fn in #75. This lets us keep the usage of the weight to rust and just have the python code return a known type which can minimize the python side overhead so something like just an attribute return of a cast. While not as fast as a pure rust implementation this should be a fair tradeoff with flexibility.

@mtreinish
Copy link
Member Author

Based on my earlier comment, I'm going to close this. We can reopen and revisit if there is a need for a statically typed (from the python perspective) weighted graph, but for right now the callback approach works well and the overhead doesn't seem to be a huge deal especially if a sane callback is used.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant