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
Black-white image converter - Black-white photo colorization

Black-white image converter - Black-white photo colorization

1 Jan 02, 2022
Me cleaner - Tool for partial deblobbing of Intel ME/TXE firmware images

me_cleaner me_cleaner is a Python script able to modify an Intel ME firmware image with the final purpose of reducing its ability to interact with the

Nicola Corna 4.1k Jan 08, 2023
Image Processing HighPass Filter With Python

Image_Processing_HighPassFilter High Pass Filter take the high frequency and ignore the low frequency High Pass Filter can be use to sharpening an ima

Felix Pratamasan 1 Dec 27, 2021
Pyconvert is a python script that you can use to convert image files to another image format! (eg. PNG to ICO)

Pyconvert is a python script that you can use to convert image files to another image format! (eg. PNG to ICO)

1 Jan 16, 2022
Labelme is a graphical image annotation tool, It is written in Python and uses Qt for its graphical interface

Image Polygonal Annotation with Python (polygon, rectangle, circle, line, point and image-level flag annotation).

Kentaro Wada 9.6k Jan 09, 2023
Instagram-like image filters.

PyGram Instagram-like image filters. Usage First, import the client: from filters import * Instanciate a filter and apply it: f = Nashville("image.jp

Ajay Kumar Nagaraj 0 Oct 18, 2022
A utility for quickly cropping large collections of images.

Crop Tool A utility for quickly cropping large collections of images. Inspired by Derrick Schultz's dataset-tools. Setup It's suggested that you use A

dusk (they/them) 6 Nov 14, 2021
Vignette is a Python library to create and manage thumbnails following the FreeDesktop standard.

Vignette Vignette is a Python library to create and manage thumbnails following the FreeDesktop standard. Thumbnails are stored in a shared directory

3 Feb 06, 2022
Anaglyph 3D Converter - A python script that adds a 3D anaglyph style effect to an image using the Pillow image processing package.

Anaglyph 3D Converter - A python script that adds a 3D anaglyph style effect to an image using the Pillow image processing package.

Kizdude 2 Jan 22, 2022
Convert HDR photos taken by iPhone 12 (or later) to regular HDR images

heif-hdrgainmap-decode Convert HDR photos taken by iPhone 12 (or later) to regular HDR images. Installation First, make sure you have the following pa

Star Brilliant 5 Nov 13, 2022
A collection of python scripts which help you programatically create PNGs or GIFs

A collection of python scripts which help you programatically create PNGs or GIFs and their Metadata in bulk with custom rarity rates, upload them to OpenSea & list them for sale.

Tom 30 Dec 24, 2022
A Blender add-on to create interesting meshes using symmetry

Procedural Symmetries This Blender add-on automates the process of iteratively applying a set of reflection planes to a base mesh. The result will con

1 Dec 29, 2021
Manipulate EXIF and IFD metadata.

Tyf Copyright Distribution Support this project Buy Ѧ and: Send Ѧ to AUahWfkfr5J4tYakugRbfow7RWVTK35GPW Vote arky on Ark blockchain and earn Ѧ weekly

16 Jan 21, 2022
QR-code Generator with a basic GUI.

Qr_generator_python Qr code generator with a basic GUI. ❔ About the QR-Code-Generator This project Generates QR codes to sites, e-mails and plain text

Tecixck 2 Oct 11, 2021
Img-to-ascii-art - Converter of image to ascii art

img-to-ascii-art Converter of image to ascii art Latest Features. Intoducing Col

1 Dec 31, 2021
Python scripts for semi-automated morphometric analysis of atolls from Landsat satellite Imagery.

AtollGeoMorph Python scripts for semi-automated morphometric analysis of atolls from Landsat satellite Imagery. The python scripts included allow user

1 Dec 16, 2022
Simple to use image handler for python sqlite3.

SQLite Image Handler Simple to use image handler for python sqlite3. Functions Function Name Parameters Returns init databasePath : str tableName : st

Mustafa Ozan Çetin 7 Sep 16, 2022
Easily turn large sets of image urls to an image dataset. Can download, resize and package 100M urls in 20h on one machine.

img2dataset Easily turn large sets of image urls to an image dataset. Can download, resize and package 100M urls in 20h on one machine. Also supports

Romain Beaumont 1.4k Jan 01, 2023
Simple utility to tinker with OPlus images

OPlus image utilities Prerequisites Linux running kernel 5.4 or up (check with uname -r) Image rebuilding Used to rebuild read-only erofs images into

Wiley Lau 15 Dec 28, 2022
Pixel art as well as various sets for hand crafting

Pixel art as well as various sets for hand crafting

1 Nov 09, 2021