Metadata-Version: 2.1
Name: sparse-graphs
Version: 0.0.2
Summary: Efficient Implementation of Sparse Graphs with Numpy
Home-page: https://github.com/geyang/sparse-graphs
Author: Ge Yang
Author-email: ge.ike.yang@gmail.com
License: UNKNOWN
Platform: UNKNOWN
Requires-Dist: numpy

Dynamic Graphical Memory Implementation
=======================================

-  `planning.py <https://github.com/geyang/sparse_graph/blob/master/sg_specs/planning.md>`__ shows how to use this graph
   with graph_search.
-  `graph_sparsification.py <https://github.com/geyang/sparse_graph/blob/master/sg_specs/graph_sparsification.md>`__
   shows how to sparsify a graph
-  `batch_sparsification.py <https://github.com/geyang/sparse_graph/blob/master/sg_specs/batch_sparsification.md>`__
   efficiently sparsify a graph with as a batch
-  `incremental_api.py <https://github.com/geyang/sparse_graph/blob/master/specs/incremental_api.md>`__ shows how to
   extend with sparsity

Usage
-----

To instantiate a graph:

.. code-block:: python

   graph = AsymMesh(n=10_000, k=6, dim=2, img_dim=[2], kernel_fn=l2, embed_fn=id2D, d_max=20)

   graph.extend(xys, images=xys, meta=xys)
   graph.update_zs()
   graph.update_edges()

Most of the time it is better to enforce sparsity of the graph by only
adding new vertices when there is no existing vertex that is close-by.
The new dedupe API allows us to do this in a batch fashion:

.. code-block:: python

   spots = graph.dedupe(images=xys, r_min=r_min)
   xys = xys[spots]
   ds = graph.to_goal(zs_2=xys)
   if ds.size == 0:
       graph.extend(xys, images=xys, meta=xys)
   else:
       m = ds.min(axis=-1) >= r_min
       if m.sum() > 0:
           graph.extend(xys[m], images=xys[m], meta=xys[m])
       graph.update_edges()

+---------------------+--------------+--------------------------------+
| Dense               | Sparse       | Details                        |
+=====================+==============+================================+
| |dense_graph|       | |image1|     | 10x more edges in the dense    |
|                     |              | graph in comparison to the     |
|                     |              | sparse graph.                  |
+---------------------+--------------+--------------------------------+

To Experiment
-------------

Import this module in the method module.

.. |dense_graph| image:: figures/random_graph.png?raw=true
.. |image1| image:: figures/batch_graph.png?raw=true


