Stochastic Matching provides tools to analyze the behavior of stochastic matching problems.
Project description
Stochastic Matching
Stochastic Matching provides tools to analyze the behavior of stochastic matching problems.
Free software: GNU General Public License v3
Documentation: https://balouf.github.io/stochastic_matching/.
Features
Compatibility graph creation (from scratch, from one of the provided generator, or by some combination).
Theoretical analysis: * Injectivity/surjectivity of the graph, kernel description. * Polytope description of positive solutions.
Fast simulator. * Provided with a large set of greedy / non-greedy policies. * Adding new policies is feasible out-of-the-box.
Lot of display features, including Vis JS Network.
Acknowledging package
If you publish results based on Stochastic Matching, please acknowledge the usage of the package by quoting the following paper.
Céline Comte, Fabien Mathieu, Ana Bušić. Stochastic dynamic matching: A mixed graph-theory and linear-algebra approach. 2022.
Credits
This package was created with Cookiecutter and the francois-durand/package_helper_2 project template.
History
0.1.0 (2022-01-13): First release
First release on PyPI.
Refactoring: the package name for the public release is Stochastic Matching.
The graph submodule has been revamped a bit: * Obtaining graphs by concatenation of other graphs is now more systematic and optimized. * Names of generators have been changes to comply with offical terminology from Wolfram. * A few more generators have been added (e.g. complete, lollipop, barbell).
Current compatibility: 3.6 -> 3.9
0.0.4 (2021-09-30): Misc. improvements
Add possibility to specify node names. The names are used for all display operations
New simulator method compute_ccdf to allow access outside show_ccdf
Simulator method show_ccdf has two new options: indices (only show some nodes), sort
New simulator method compute_average_queues
New simulator method show_average_queues with three options: indices (only show some nodes), sort, and as_time (divide by arrival rates)
New Getting started notebook.
Doctests parameters adjusted for faster test suite execution
0.0.3 (2021-08-24): Simulators are back!
This update reintroduces simulators, fully revamped
- All simulators are built as a hierarchy of classes
Simulator is the mother abstract class
QueueSizeSimulator is dedicated to greedy simulators that only use the queue sizes: RandomNode, RandomItem, and LongestQueue.
QueueStateSimulator is dedicated to greedy simulators that use the age of items: FCFM.
VQSimulator is a fast implementation of the virtual queue algorithm.
All non-abstract simulators have a string name. The new get_simulator_classes() gives a dict of them that can be used to easily select a given simulator.
- Lots of refactoring
nodes and edges attributes from graph renamed as incidence and co_incidence respectively. Older incidence attribute (plain matrix) removed.
spectral.py moved up to main module
New simulator module
simulator.py split into classes.py and a few other files inside the simulator module.
Jit is disabled for the testing (allows for inner coverage inspection).
Tutorials revamped to cope with 0.0.3.
Old files removed from git for cleanliness
0.0.2 (2021-07-22): Hyper-graph release
Lots of changes in this update.
- Graph API has been fully revamped. There is now a GenericGraph class from which SimpleGraph and HyperGraph are derived.
Hypergraphs don’t have any adjacency attribute, only incidence. They are displayed as bipartite graphs between nodes and edges, with an option to explicitly separate nodes from edges.
Simple graphs are mostly similar but not compatible with previous Graph class.
Hovering on edge now show edge id and description, e.g. edge 6 between nodes 1 and 4 will show “6: (1, 4)”
- TWO HYPERGRAPHS GENERATORS have been added to the mix:
hyper_dumbbells can create the candy and larger sweets with trivial kernel.
fan can create hypergraphs with more complex kernels, possibly with bipartite-like degenerescence
- The old gramian module is now called spectral.
All internals have switched from gramian-based computation to incidence-based computation, which makes it fully hypergraph ready (multiplicity / loops should work, but are not tested yet).
NEW MAXIMIN FLOW COMPUTATION! No need to optimize each edge, one single linear optimization is enough and the result maximizes the minimal edge flow.
is_stable method checks the graph kernel dimension and existence of a positive solution.
- Main class as been revamped as well
Class name is now MQ (could be changed later).
When displayed, flows are checked by default. Conservation law issues gives red nodes, negative edges are red, null edges are orange (can be disabled).
SIMULATION ENGINE NOT AVAILABLE IN 0.0.2, as there are a lot of things to change. It will return in 0.0.3.
- Misc:
Tutorials (simulation apart) have been updated. Enjoy the double degenerated fan!
Local coverage computation. Enforcing 100% coverage on all 0.0.2+ code.
Minor changes in the display module to cope with the new graph API.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for stochastic_matching-0.1.0.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | ca527a6048376b0cb12ba4134f2eba9ee3d09d29480a76a111b76967adce087c |
|
MD5 | 61176f197b1615c8b7a697d1eaff731f |
|
BLAKE2b-256 | 338ff17b82058ca29811443c94455ef8acf16adbb56079b9f82021ad4fb0eea2 |
Hashes for stochastic_matching-0.1.0-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 73b50b78014855fe494768ad8d985b19d9b2e577c73875e6db2a106f6cd3bde6 |
|
MD5 | bf603fecf1c98c8cde2a0aa402a4d6bc |
|
BLAKE2b-256 | 790d2bbe60d1ec7a3f6e7682fd62596318b45ffd60edceb45e1019a461dc32e7 |