SGTL - Spectral Graph Theory Library

Overview

SGTL - Spectral Graph Theory Library

Documentation Status

SGTL is a python library of spectral graph theory methods. The library is still very new and so there are many features and algorithms missing.

You can install the library with pip install sgtl.

Features

  • Lightweight and flexible graph object which can be extended as needed.
  • Graph matrices including the Laplacian and Normalised Laplacian
  • Spectral clustering method
  • Generate graphs from the stochastic block model

Documentation

The full documentation is available here.

Contributing

Please feel free to contribute to this project by opening issues, reporting bugs, and submitting pull requests.

The library is currently maintained by Peter Macgregor ([email protected]) and you are welcome to get in touch with any questions.

Comments
  • Graph methods should give meaningful errors when vertices out of range

    Graph methods should give meaningful errors when vertices out of range

    Currently, if you ask for the volume of a set of vertices, but the set includes indices which are greater than the number of vertices in the graph, the code throws an IndexError from somewhere inside the graph code.

    This is not totally unreasonable, but it would help debugging this kind of error if it gave a clear error message. Something like: "Vertex set includes indices larger than number of vertices".

    enhancement good first issue 
    opened by pmacg 6
  • Added graph._check_vert_num method and updated class tests accordingly

    Added graph._check_vert_num method and updated class tests accordingly

    @pmacg I've fixed all of your comments. Unfortunately I made a little bit of a mess of my local repository so I've created a new pull request. Hope this isn't too much trouble for you. If you have any more comments please let me know

    opened by yonMaor 5
  • Add tools for visualising the spectrum of a graph.

    Add tools for visualising the spectrum of a graph.

    There should be tools available to visualise the spectrum of a graph - both the eigenvalues themselves and the spectral embedding of the eigenvectors.

    enhancement 
    opened by pmacg 3
  • Construct graph as kronecker product of two existing graphs

    Construct graph as kronecker product of two existing graphs

    It would be useful to construct a graph from the kronecker product of two existing graphs. That is, the adjacency matrix of the new graph is the kronecker product of the adjacency matrices of the input graphs.

    enhancement 
    opened by pmacg 1
  • The weight function on the Graph object should return a float

    The weight function on the Graph object should return a float

    At the moment, the weight function on sgtl.graph.Graph() rounds the weight to the nearest integer and returns an int.

    This should return a float to allow fractionally weighted edges.

    bug good first issue 
    opened by pmacg 1
  • Graph matrices are not symmetric for an undirected graph

    Graph matrices are not symmetric for an undirected graph

    For a large undirected graph generated from the stochastic block model, the generated graph matrices are not always symmetric. For example:

    >>> big_graph = sgtl.random.ssbm(1000, 5, 0.8, 0.2)
    >>> lap_mat = big_graph.normalised_laplacian_matrix()
    >>> lap_mat_dense = lap_mat.toarray()
    >>> np.allclose(lap_mat_dense, lap_mat_dense.T)
    False
    

    I haven't debugged this yet, but we should certainly be able to assume that the graph matrices are symmetric for an undirected graph.

    bug 
    opened by pmacg 1
  • The num_edges member of the Graph object is incorrect when graph is weighted

    The num_edges member of the Graph object is incorrect when graph is weighted

    Given a weighted graph object, the graph.num_edges gives half of the total volume of the graph, rather than the actual number of weighted edges.

    This should be replaced with two methods on the object, a num_edges method which gives the number of non-zero elements of the adjacency matrix (corrected for the symmetry) and a graph_volume method which returns the total weight of all the edges in the graph.

    bug good first issue 
    opened by pmacg 1
  • Combine graphs by adding their edges

    Combine graphs by adding their edges

    Add a method to add two graphs together, equivalent to adding their adjacency matrices.

    If the graphs do not have the same number of vertices, then this method should throw a suitable exception.

    Consider overloading the '+' operator so that you can write graph3 = graph1 + graph2.

    enhancement good first issue 
    opened by pmacg 0
  • Add spectrum method to graph

    Add spectrum method to graph

    Add the methods

    • adjacency_spectrum()
    • laplacian_spectrum()
    • normalised_laplacian_spectrum()

    To the graph object for returning the eigenvalues of the corresponding graph matrices.

    enhancement 
    opened by pmacg 0
  • Typo in return value of bipartiteness method

    Typo in return value of bipartiteness method

    The return value of the Graph.bipartiteness() method should display a beta in math mode in the rendered documentation. See the return value of the conductance method for how to do this.

    documentation good first issue 
    opened by pmacg 0
  • Update to work with sparse arrays

    Update to work with sparse arrays

    The scipy sparse linear algebra library has recently introduced sparse arrays rather than matrices and is encouraging their use over the matrix types.

    This enhancement covers updating SGTL to allow use of either the sparse array or sparse matrix types.

    enhancement 
    opened by pmacg 0
  • Look into behaviour of methods on graphs with negative weights

    Look into behaviour of methods on graphs with negative weights

    It may be sometimes useful to use graphs with negative weights. The library is not currently designed with this in mind, but many things might 'just work'. This issue covers investigating formally the behaviour of the library on graphs with negative weights.

    bug documentation enhancement 
    opened by pmacg 0
  • Add weighted graph example to the Getting Started guide in the documentation

    Add weighted graph example to the Getting Started guide in the documentation

    The 'Getting Started' page of the documentation currently only gives examples of unweighted graphs. It would be nice to also include a weighted example, or at least mention that this is possible.

    documentation enhancement 
    opened by pmacg 0
  • Generating SBM with different cluster sizes can fail

    Generating SBM with different cluster sizes can fail

    The following code for generating a graph from the stochastic block model fails with out-of-bounds errors.

    import sgtl.random
    import numpy as np
    
    
    def main():
        cluster_sizes = [100, 50, 20, 20, 20]
        p = 0.8
        prob_mat_q = np.asarray([[p,   0.2, 0.5, 0.1, 0.1],
                                 [0.2, p,   0.1, 0.6, 0.2],
                                 [0.5, 0.1, p,   0.2, 0.1],
                                 [0.1, 0.6, 0.2, p,   0.5],
                                 [0.1, 0.2, 0.1, 0.5, p]])
        graph = sgtl.random.sbm(cluster_sizes, prob_mat_q)
    
    
    if __name__ == '__main__':
        main()
    
    Traceback (most recent call last):
      File ".../main.py", line 17, in <module>
        main()
      File ".../main.py", line 13, in main
        graph = sgtl.random.sbm(cluster_sizes, prob_mat_q)
      File ".../venv/lib/python3.8/site-packages/sgtl/random.py", line 179, in sbm
        adj_mat[vertex_1, vertex_2] = 1
      File ".../venv/lib/python3.8/site-packages/scipy/sparse/_lil.py", line 330, in __setitem__
        return self._set_intXint(key[0], key[1], x)
      File ".../venv/lib/python3.8/site-packages/scipy/sparse/_lil.py", line 299, in _set_intXint
        _csparsetools.lil_insert(self.shape[0], self.shape[1], self.rows,
      File "_csparsetools.pyx", line 61, in scipy.sparse._csparsetools.lil_insert
      File "_csparsetools.pyx", line 87, in scipy.sparse._csparsetools.lil_insert
    IndexError: column index (240) out of bounds
    
    bug 
    opened by pmacg 0
Releases(v0.4.6)
  • v0.4.6(Jan 11, 2022)

    What's Changed

    • Single efficiency update - computing weight between vertex sets by @pmacg in https://github.com/pmacg/py-sgtl/pull/47

    Full Changelog: https://github.com/pmacg/py-sgtl/compare/v0.4.5...v0.4.6

    Source code(tar.gz)
    Source code(zip)
  • v0.4.5(Jan 9, 2022)

    What's Changed

    • Issue 32 - add tensor product method by @pmacg in https://github.com/pmacg/py-sgtl/pull/43
    • Issue #27 - add option to plot eigenvalues in spectrum methods by @pmacg in https://github.com/pmacg/py-sgtl/pull/44
    • Overload plus operator to add graphs together by @pmacg in https://github.com/pmacg/py-sgtl/pull/45

    Full Changelog: https://github.com/pmacg/py-sgtl/compare/v0.4.4...v0.4.5

    Source code(tar.gz)
    Source code(zip)
  • v0.4.4(Jan 7, 2022)

    What's Changed

    • Issue #41 - Add gaussian kernel graph constructor. by @pmacg in https://github.com/pmacg/py-sgtl/pull/42

    Full Changelog: https://github.com/pmacg/py-sgtl/compare/v0.4.3...v0.4.4

    Source code(tar.gz)
    Source code(zip)
  • v0.4.3(Jan 6, 2022)

    What's Changed

    • Issue #39 - KNN construction with sparse data matrix by @pmacg in https://github.com/pmacg/py-sgtl/pull/40

    Full Changelog: https://github.com/pmacg/py-sgtl/compare/v0.4.2...v0.4.3

    Source code(tar.gz)
    Source code(zip)
  • v0.4.2(Jan 6, 2022)

    What's Changed

    • Add methods for converting to and from edgelist files by @pmacg in https://github.com/pmacg/py-sgtl/pull/38

    Full Changelog: https://github.com/pmacg/py-sgtl/compare/v0.4.1...v0.4.2

    Source code(tar.gz)
    Source code(zip)
  • v0.4.1(Jan 5, 2022)

    What's Changed

    • Iss29 add spectrum methods by @pmacg in https://github.com/pmacg/py-sgtl/pull/34
    • Add method for constructing k-nearest neighbours graph by @pmacg in https://github.com/pmacg/py-sgtl/pull/36

    Full Changelog: https://github.com/pmacg/py-sgtl/compare/v0.4...v0.4.1

    Source code(tar.gz)
    Source code(zip)
  • v0.4(Dec 14, 2021)

    What's Changed

    • Add workflow by @pmacg in https://github.com/pmacg/py-sgtl/pull/7
    • Issue #3 - Fix the num_edges member on the graph object. by @pmacg in https://github.com/pmacg/py-sgtl/pull/11
    • Fix weight function when graph has floating point weights, or self-loops by @pmacg in https://github.com/pmacg/py-sgtl/pull/13
    • Added graph._check_vert_num method and updated class tests accordingly by @yonMaor in https://github.com/pmacg/py-sgtl/pull/12
    • Update bipartiteness documentation by @pmacg in https://github.com/pmacg/py-sgtl/pull/15
    • Add methods to convert to and from networkx graphs by @pmacg in https://github.com/pmacg/py-sgtl/pull/16
    • Return error when computing conductance of empty set by @pmacg in https://github.com/pmacg/py-sgtl/pull/17
    • Add the cheeger cut algorithms by @pmacg in https://github.com/pmacg/py-sgtl/pull/18

    New Contributors

    • @pmacg made their first contribution in https://github.com/pmacg/py-sgtl/pull/7
    • @yonMaor made their first contribution in https://github.com/pmacg/py-sgtl/pull/12

    Full Changelog: https://github.com/pmacg/py-sgtl/compare/v0.3.3...v0.4

    Source code(tar.gz)
    Source code(zip)
Owner
Peter Macgregor
Computer Science PhD Student, University of Edinburgh.
Peter Macgregor
QR code python application which can read(decode) and generate(encode) QR codes.

QR Code Application This is a basic QR Code application. Using this application you can generate QR code for you text/links. Using this application yo

Atharva Parkhe 1 Aug 09, 2022
Python script to generate vector graphics of an oriented lattice unit cell

unitcell Python script to generate vector graphics of an oriented lattice unit cell Examples unitcell --type hexagonal --eulers 12 23 34 --axes --crys

Philip Eisenlohr 2 Dec 10, 2021
3D Model files and source code for rotating turntable. Raspberry Pi, DC servo and PWM modulator required.

3DSimpleTurntable 3D Model files and source code for rotating turntable. Raspberry Pi, DC servo and PWM modulator required. Preview Construction Print

Thomas Boyle 1 Feb 13, 2022
Python library that finds the size / type of an image given its URI by fetching as little as needed

FastImage This is an implementation of the excellent Ruby library FastImage - but for Python. FastImage finds the size or type of an image given its u

Brian Muller 28 Mar 01, 2022
A Icon Maker GUI Made - Convert your image into icon ( .ico format ).

Icon-Maker-GUI A Icon Maker GUI Made Using Python 3.9.0 . It will take any image and convert it to ICO file, for web site favicon or Windows applicati

Insanecodes 12 Dec 15, 2021
A scalable implementation of WobblyStitcher for 3D microscopy images

WobblyStitcher Introduction A scalable implementation of WobblyStitcher Dependencies $ python -m pip install numpy scikit-image Visualization ImageJ

CSE Lab, ETH Zurich 7 Jul 25, 2022
A minimal python script for generating bip39 seed phrases, and corresponding Seed Signer Seed seed phrase qr code ready for offline printing.

A minimal python script for generating bip39 seed phrases, and corresponding Seed Signer Seed seed phrase qr code ready for offline printing.

CypherToad 8 Sep 12, 2022
Cat avatars for adult independent users

Cat avatars for adult independent users Samples (Natasha, wake up!) Usage Check values from https://shantichat.github.io/avacats/index.json: { "sizes"

4 Nov 05, 2021
QR Generator using GUI with Tinker

BinCat Token System Very simple python script with GUI that generates QR codes. It don't include a QR "decription" tool. It only generate-it and thats

Hipotesi 1 Nov 06, 2021
Simplest QRGenerator with a cool feature (-sh=True :D)

Simple QR-Codes Generator :D Generates QR-codes, nothing more and nothing less . How to use Just run ./install.sh to set all the dependencies up, th

RENNAARENATA 1 Dec 11, 2021
Raven is a tool written in Python3 allowing you to generate an unique image with some text.

🐦 Raven is a tool written in Python3 allowing you to generate an unique image with some text. It does it by searching the text on Google, do

Billy 39 Dec 20, 2022
Image Compression GUI APP Python: PyQt5

Image Compression GUI APP Image Compression GUI APP Python: PyQt5 Use : f5 or debug or simply run it on your ids(vscode , pycham, anaconda etc.) socia

Sourabh Dhalia 1 May 21, 2022
QSIprep: Preprocessing and analysis of q-space images

QSIprep: Preprocessing and analysis of q-space images Full documentation at https://qsiprep.readthedocs.io About qsiprep configures pipelines for proc

Lifespan Informatics and Neuroimaging Center 88 Dec 15, 2022
3D printer / slicing GUI built on top of the Uranium framework

Cura Ultimaker Cura is a state-of-the-art slicer application to prepare your 3D models for printing with a 3D printer. With hundreds of settings and h

Ultimaker 4.4k Jan 02, 2023
An open source image editor which can manipulate an image in many ways!

Image Editor - An open source image editor which can manipulate an image in many ways! If you need any more modes in repo or I

TroJanzHEX 44 Nov 17, 2022
FrostedGlass is a translucent frosted glass effect widget, that creates a context with the background behind it.

FrostedGlass FrostedGlass is a translucent frosted glass effect widget, that creates a context with the background behind it. The effect is drawn on t

Kivy Garden 24 Dec 10, 2022
A SIXEL encoder/decoder implementation derived from kmiya's sixel

libsixel What is this? This package provides encoder/decoder implementation for DEC SIXEL graphics, and some converter programs. (https://youtu.be/0Sa

Hayaki Saito 2k Jan 09, 2023
Extracts dominating colors from an image and presents them as a palette.

ColorPalette A simple web app to extract dominant colors from an image. Demo Live View it live at : https://colorpalettedemo.herokuapp.com/ You can de

Mayank Nader 214 Dec 29, 2022
Fixes 500+ mislabeled MURA images

In this repository, new csv files are provided that fixes 500+ mislabeled MURA x-rays for all categories. The mislabeled x-rays mainly had hardware in them. This project only fixes the false negative

Pieter Zeilstra 4 May 18, 2022
Python framework for creating and scaling up production of vector graphics assets.

Board Game Factory Contributors are welcome here! See the end of readme. This is a vector-graphics framework intended for creating and scaling up prod

Adam Volný 5 Jul 13, 2022