Red Black Graph
Project description
Red-Black Graph - A DAG of Multiple, Interleaved Binary Trees
Introduction
Red-Black Graphs are a specific type of graph, a directed acyclic graph of interleaved binary trees. This data structure resulted from exploration of efficient representations for family history. This package presents and implements the underlying linear algebra as well as discusses some interesting applications.
This python module extends both scipy and numpy and also conforms to dockerutils
conventions for building and running docker images used in module development. There is a script in the bin
directory that can be used to setup the project for development or to prep for reading the notebook.
(bin/setup-project.sh
). You will want to create an activate a virtual environment prior to running the script.
Reading the Notebook
A research paper describing the linear algebra underlying Red-Black graphs as well as examples of application can be found in the Jupyter notebook, "Red Black Graph - A DAG of Multiple, Interleaved Binary Trees.ipynb". To access the notebook after you've setup the project for development, simply:
run-image notebook
open http://localhost:8888/lab
If you'd prefer to read hard copy, simply run:
`bin/generate-pdf.sh notebooks/Red Black Graph - A DAG of Multiple, Interleaved Binary Trees.ipynb`
A pdf file will be generated into the build/latex-{datestamped}
directory.
To Try Things Out...
Run the following:
# use crawl-fs to extract a sample data set from FamilySearch
pip install fs-crawler
crawl-fs -i <FamilySearch Ids to seed crawl> -o <output-directory> -b <name portion of output file>
# this will generate a <name>.vertices.csv and <name>.edges.csv file which can be ingested into a RedBlackGraph
pip install RedBlackGraph
# use rbgcf to generate both a simple form and cannonical form of a Red Black Graph (xlsx files)
rbgcf -f <directory and base name of vertices and edges file> -o <output-directory>
# Use excel to view output
A Note on Implementations
redblackgraph.reference
- a pure python implementation. This simple implementation is intended primarily for illustrative purposes.redblackgraph.matrix
andredblackgrpah.array
- a Numpy C-API extension for efficient computation with the matrix multiplication operator, @, overloaded to support avos sum and product.redblackgraph.sparse_matrix
- an optimized implementation built on scipy's sparse matrix implementation.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for RedBlackGraph-0.3.17-cp310-cp310-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 32abcce5b500f95618c028b45a21eb95038e84d220355cfccbfc169d83863566 |
|
MD5 | 7db056d2715bdcc8c9618ae9240d3a1d |
|
BLAKE2b-256 | bc044356ff3aff095586c2d60b4602015a4386b1daf87a787f009e8d73e1a3ac |
Hashes for RedBlackGraph-0.3.17-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c801806ed17f08e569640b1265db2875e77b5488de7e772659dcfbf5c19cdf4f |
|
MD5 | dd4bd92d16698e891e8d8f4f43952758 |
|
BLAKE2b-256 | 122c3430fa39e19f9f8e79c48631a1d9dfe631bdeb368eb976fc5acef49ffc60 |
Hashes for RedBlackGraph-0.3.17-cp310-cp310-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4faa1da72c56abfd98b8de72fc0902f592e5eae116453b6419f3466d3711c0ce |
|
MD5 | 2108341835123024938d18fbe1ab076e |
|
BLAKE2b-256 | 3af52d72d09f4ad6ac24c6ecfbe6a667d6bf51ced1563de52fd8ba5b7f0c666a |
Hashes for RedBlackGraph-0.3.17-cp39-cp39-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7ab1b98fd5a7179e3a2f89b2ce30af8483c05afec7830dc8b56d657ff51e3652 |
|
MD5 | be075bd2bf18f4798961f09b0e5cadb1 |
|
BLAKE2b-256 | 5c3b8678041cfe913e4b1fe8c43b57f8dba8ec59d0458bc3c940659531776a40 |
Hashes for RedBlackGraph-0.3.17-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 86bf6f72c39f58cff533a8ceabb3acede45d7a35300f468a342d233a4fd60947 |
|
MD5 | 063ba136a63c39d7c3c884bdc3813d96 |
|
BLAKE2b-256 | 14c4b360a364b8e8bc10c44e6436424f0bee78e43ca23fa7f57ee759e6832f6a |
Hashes for RedBlackGraph-0.3.17-cp39-cp39-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 417c4841eca5bb934e5f47f645de1fb868d18f6768c2da654a172252456df1ed |
|
MD5 | 3a1b3de5ef2505bf5d5a79fea5111982 |
|
BLAKE2b-256 | 8d940ea33d3f94bf24c8ce1ce7aa7be281e47601936db613593af2713f92dfa4 |
Hashes for RedBlackGraph-0.3.17-cp38-cp38-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 530e3aedaac22ca939e3fdd9f5846c1abdf421cbd07f1c50858c03608b6fda6e |
|
MD5 | 96cd80b4aab948e35a9a4558636e0aa3 |
|
BLAKE2b-256 | 708088b08324224154284c38ea6722a9a8d91eac394edc8e604db397d1a75893 |
Hashes for RedBlackGraph-0.3.17-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ebe2b578058d3b9b225e4796ee9a055da2082b23b33d4abbbca24a3ecea4c75d |
|
MD5 | 1e60532b62d4e0d2ecbcaaad0b3b541f |
|
BLAKE2b-256 | 7c55f9a522b86b17a1e9c90ef1b7d5758c6c5423ec2110505d81bb7eec8c7972 |
Hashes for RedBlackGraph-0.3.17-cp38-cp38-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8b4a87d7d3ccfe6e084975726152441aef6cba9f198927f79b0ac3d9b1b3745c |
|
MD5 | 6307e37abfa1546b8506040f6583ca75 |
|
BLAKE2b-256 | a7ad3a9fe67712dfb2f587fe25d0a61809921adf99d9393f99376216aaa39948 |
Hashes for RedBlackGraph-0.3.17-cp37-cp37m-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 42bf47ea1b8cd7e4bee1da5900c6985e4311a0ef797b56c2e4eb28e6a904bf09 |
|
MD5 | d13f10105def14c401f24bd299e140d7 |
|
BLAKE2b-256 | c77711f9d36cfe5b5215c265d4e6979a2cb91bdf1b02df865c4b606ba1e037fb |
Hashes for RedBlackGraph-0.3.17-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6f9af5d68feabe0bf7dd8248b9b032807b4a849e24bf43ab39d041bb1af6b28f |
|
MD5 | 4d8f9e78df5ad4c0487aeaa042585581 |
|
BLAKE2b-256 | 25f8ea26c59b37c670e7dfeb7f5ca52ff07566d5d436fd60d81ef520e41b5eeb |
Hashes for RedBlackGraph-0.3.17-cp37-cp37m-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d44825328717f590338abbfb2b9bdfa02df390ac7204d9de10a6be918d555219 |
|
MD5 | 4ee5d4ef1176d0af2c9b61073747317f |
|
BLAKE2b-256 | 4384d29e23cbf2d646e6db5389b03ac2883eabdc38e03cd24407ff6d3fbc36ff |
Hashes for RedBlackGraph-0.3.17-cp36-cp36m-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aa26d2cb55a49eab7c8b50b5fbf2d26fd4b861dbfba0b068d50001a03088a9c7 |
|
MD5 | 0eff52efaf72f65bb9957420036f3a7e |
|
BLAKE2b-256 | f83153e8ff5bb6f3cd8ea75c389907da717cce5a103d99d0dc8773aa892a5005 |
Hashes for RedBlackGraph-0.3.17-cp36-cp36m-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9b99f17fc2fe37c97273bcdfee73aab6b542019a8880848911c54ce825756adc |
|
MD5 | 1774e208d327fe245a77767e4e3ee32b |
|
BLAKE2b-256 | 6e1c0f9320bfde7e15a0ee4f75226fca91edc5279be97dc1d1170c8700e96ac5 |