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
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
Typesheet is a tiny Python script for creating transparent PNG spritesheets from TrueType (.ttf) fonts.

typesheet typesheet is a tiny Python script for creating transparent PNG spritesheets from TrueType (.ttf) fonts. I made it because I couldn't find an

Grayson Chao 12 Dec 23, 2022
Make GIFs from time-stacked xarray.DataArrays (time, [optional band], y, x), dead-simple.

GeoGIF Make GIFs from time-stacked xarray.DataArrays (time, [optional band], y, x), dead-simple. from geogif import gif, dgif gif(data_array) dgif(das

Gabe Joseph 47 Dec 22, 2022
A Robust Avatar Generator with a huge number of templates

CoolAvatars Welcome to this repository of CoolAvatars. Using this project, you can generate cool avatars not only from the samples present in my image

RAVI PRAKASH 5 Oct 12, 2021
A minimal, standalone viewer for 3D animations stored as stop-motion sequences of individual .obj mesh files.

ObjSequenceViewer V0.5 A minimal, standalone viewer for 3D animations stored as stop-motion sequences of individual .obj mesh files. Installation: pip

csmailis 2 Aug 04, 2022
This is the official source code of FreeCAD, a free and opensource multiplatform 3D parametric modeler.

Freedom to build what you want FreeCAD is an open-source parametric 3D modeler made primarily to design real-life objects of any size. Parametric modeling allows you to easily modify your design by g

FreeCAD 12.9k Jan 07, 2023
New program to export a Blender model to the LBA2 model format.

LBA2 Blender to Model 2 This is a new program to export a Blender model to the LBA2 model format. This is also the first publicly released version of

2 Nov 30, 2022
DrawBot is a powerful, free application for macOS that invites you to write Python scripts to generate two-dimensional graphics

DrawBot is a powerful, free application for macOS that invites you to write Python scripts to generate two-dimensional graphics.

Frederik Berlaen 344 Jan 06, 2023
Alternate Python bindings for the Open Asset Import Library (ASSIMP)

Impasse A simple Python wrapper for assimp using cffi to access the library. Requires Python = 3.7. It's a fork of PyAssimp, Assimp's official Python

Salad Dais 3 Sep 26, 2022
PIX is an image processing library in JAX, for JAX.

PIX PIX is an image processing library in JAX, for JAX. Overview JAX is a library resulting from the union of Autograd and XLA for high-performance ma

DeepMind 294 Jan 08, 2023
Gbs-image-colorizer - A tool to convert colorful pictures to GB Studio-compatible colorized backgrounds.

GB Studio Image Colorizer A tool to convert colorful pictures to GB Studio-compatible colorized backgrounds. Made by NalaFala/Yousurname/Y0UR-U5ERNAME

Yousurname 8 Dec 08, 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
💯 Watermark your images with one line of command

Watermarker 💯 Watermark your images with one line of command 🧐 $ pip3 install

Orhan Emre Dikicigil 3 May 01, 2022
Fill holes in binary 2D & 3D images fast.

Fill holes in binary 2D & 3D images fast.

11 Dec 09, 2022
Script for the creation of metadatas and the randomization of images of MekaVerse

MekaVerse-random Script for the creation of metadata and the randomization of images of MekaVerse Step to replay the random : Create a folder : output

Miinded 8 Sep 07, 2022
A python program to generate ANSI art from images and videos

ANSI Art Generator A python program that creates ASCII art (with true color support if enabled) from images and videos Dependencies The program runs u

Pratyush Kumar 12 Nov 08, 2022
Imutils - A series of convenience functions to make basic image processing operations such as translation, rotation, resizing, skeletonization, and displaying Matplotlib images easier with OpenCV and Python.

imutils A series of convenience functions to make basic image processing functions such as translation, rotation, resizing, skeletonization, and displ

PyImageSearch 4.3k Jan 01, 2023
Nutrify - take a photo of food and learn about it

Nutrify - take a photo of food and learn about it Work in progress. To make this a thing, we're going to need lots of food images... Start uploading y

Daniel Bourke 93 Dec 30, 2022
Generative Art Synthesizer - a python program that generates python programs that generates generative art

GAS - Generative Art Synthesizer Generative Art Synthesizer - a python program that generates python programs that generates generative art. Examples

Alexey Borsky 43 Dec 03, 2022