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
Hacking github graph with a easy python script

Hacking-Github-Graph Hacking github graph with a easy python script Requirements git latest version installed. A text editor (eg: vs code, sublime tex

SENPAI LEGEND 1 Nov 1, 2021
Plots the graph of a function with ASCII characters.

ASCII Graph Plotter Plots the graph of a function with ASCII characters. See the change log here. Developed by InformaticFreak (c) 2021 How to use py

InformaticFreak 2 Apr 29, 2022
Glyph-graph - A simple, yet versatile, package for graphing equations on a 2-dimensional text canvas

Glyth Graph Revision for 0.01 A simple, yet versatile, package for graphing equations on a 2-dimensional text canvas List of contents: Brief Introduct

Ivan 2 Oct 21, 2022
DP2 graph edit codes.

必要なソフト・パッケージ Python3 Numpy JSON Matplotlib 動作確認環境 MacBook Air M1 Python 3.8.2 (arm64) Numpy 1.22.0 Matplotlib 3.5.1 JSON 2.0.9 使い方 draw_time_histgram(

null 1 Feb 19, 2022
The friendly PIL fork (Python Imaging Library)

Pillow Python Imaging Library (Fork) Pillow is the friendly PIL fork by Alex Clark and Contributors. PIL is the Python Imaging Library by Fredrik Lund

Pillow 10.4k Dec 31, 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 8, 2023
Pure Python bindings for the pure C++11/OpenCL Qrack quantum computer simulator library

pyqrack Pure Python bindings for the pure C++11/OpenCL Qrack quantum computer simulator library (PyQrack is just pure Qrack.) IMPORTANT: You must buil

vm6502q 6 Jul 21, 2022
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

null 3 Feb 6, 2022
impy is an all-in-one image analysis library, equipped with parallel processing, GPU support, GUI based tools and so on.

impy is All You Need in Image Analysis impy is an all-in-one image analysis library, equipped with parallel processing, GPU support, GUI based tools a

null 24 Dec 20, 2022
Python library for ascii graphics

Python library for ascii graphics

Anton 6 Oct 20, 2021
kikuchipy is an open-source Python library for processing and analysis of electron backscatter diffraction (EBSD) patterns

kikuchipy is an open-source Python library for processing and analysis of electron backscatter diffraction (EBSD) patterns. The library builds on the

pyxem 53 Dec 29, 2022
Seaborn-image is a Python image visualization library based on matplotlib and provides a high-level API to draw attractive and informative images quickly and effectively.

seaborn-image: image data visualization Description Seaborn-image is a Python image visualization library based on matplotlib and provides a high-leve

null 48 Jan 5, 2023
starfish is a Python library for processing images of image-based spatial transcriptomics.

starfish: scalable pipelines for image-based transcriptomics starfish is a Python library for processing images of image-based spatial transcriptomics

null 199 Dec 8, 2022
A python based library to help you create unique generative images based on Rarity for your next NFT Project

Generative-NFT Generate Unique Images based on Rarity A python based library to help you create unique generative images based on Rarity for your next

Kartikay Bhutani 8 Sep 21, 2022
A tool and a library for SVG path data transformations.

SVG path data transformation toolkit A tool and a library for SVG path data transformations. Currently it supports a translation and a scaling. Usage

Igor Mikushkin 2 Mar 7, 2022
A tool to maintain an archive/mirror of your Google Photos library for backup purposes.

Google Photos Archiver Updated Instructions 8/9/2021 Version 2.0.6 Instructions: Download the script (exe or python script listed below) Follow the in

Nick Dawson 116 Jan 3, 2023
A Python3 library to generate dynamic SVGs

The Python library for generating dynamic SVGs using Python3

null 1 Dec 23, 2021
A 3D structural engineering finite element library for Python.

An easy to use elastic 3D structural engineering finite element analysis library for Python.

Craig 220 Dec 27, 2022
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