Graphs objects

Main Graph Class

class pygsp.graphs.Graph(W, gtype='unknown', lap_type='combinatorial', coords=None, plotting={}, **kwargs)[source]

Bases: object

The main graph object.

It is used to initialize by default every missing field of the subclass graphs. It can also be used alone to initialize customs graphs.

Parameters:

W : sparse matrix or ndarray (data is float)

Weight matrix. Mandatory.

gtype : string

Graph type (default is “unknown”)

lap_type : string

Laplacian type (default is ‘combinatorial’)

coords : ndarray

Coordinates of the vertices (default is None)

plotting : dict

Dictionnary containing the plotting parameters

Examples

>>> from pygsp import graphs
>>> import numpy as np
>>> W = np.arange(4).reshape(2, 2)
>>> G = graphs.Graph(W)
compute_fourier_basis(smallest_first=True, force_recompute=False, **kwargs)[source]

Compute the fourier basis of the graph.

Parameters:

smallest_first: bool

Define the order of the eigenvalues. Default is smallest first (True).

force_recompute: bool

Force to recompute the Fourier basis if already existing.

References

cite ´chung1997spectral´

copy_graph_attributes(Gn, ctype=True)[source]

Copy some parameters of the graph into a given one.

Parameters:

G : Graph structure

ctype : bool

Flag to select what to copy (Default is True)

Gn : Graph structure

The graph where the parameters will be copied

Returns:

Gn : Partial graph structure

Examples

>>> from pygsp import graphs
>>> Torus = graphs.Torus()
>>> G = graphs.TwoMoons()
>>> G.copy_graph_attributes(ctype=False, Gn=Torus);
create_laplacian(lap_type='combinatorial')[source]

Create a new graph laplacian.

Parameters:

lap_type : string

The laplacian type to use. Default is “combinatorial”.

estimate_lmax(force_recompute=False)[source]

Estimate the maximal eigenvalue.

Parameters:

force_recompute : boolean

Force to recompute the maximal eigenvalue. Default is false.

Examples

Just define a graph and apply the estimation on it.

>>> from pygsp import graphs
>>> import numpy as np
>>> W = np.arange(16).reshape(4, 4)
>>> G = graphs.Graph(W)
>>> G.estimate_lmax()
is_connected()[source]

Function to check the strong connectivity of the input graph.

It uses DFS travelling on graph to ensure that each node is visited. For undirected graphs, starting at any vertex and trying to access all others is enough. For directed graphs, one needs to check that a random vertex is accessible by all others and can access all others. Thus, we can transpose the adjacency matrix and compute again with the same starting point in both phases.

Returns:

connected : bool

A bool value telling if the graph is connected

Examples

>>> from scipy import sparse
>>> from pygsp import graphs
>>> W = sparse.rand(10, 10, 0.2)
>>> G = graphs.Graph(W=W)
>>> connected = G.is_connected()
is_directed()[source]

Define if the graph has directed edges.

Notes

Can also be used to check if a matrix is symmetrical

Examples

>>> from scipy import sparse
>>> from pygsp import graphs
>>> W = sparse.rand(10, 10, 0.2)
>>> G = graphs.Graph(W=W)
>>> directed = G.is_directed()
plot(**kwargs)[source]

Plot the graph.

See plotting doc.

set_coords(kind='ring2D', coords=None)[source]

Set coordinates for the vertices.

Parameters:

kind : string

The kind of display. Default is ‘ring2D’. Accepting [‘ring2D’, ‘community2D’, ‘manual’, ‘random2D’, ‘random3D’].

coords : np.ndarray

An array of coordinates in 2D or 3D. Used only if kind is manual. Set the coordinates to this array as is.

Examples

>>> from pygsp import graphs
>>> G = graphs.ErdosRenyi()
>>> G.set_coords()
>>> G.plot()
subgraph(ind)[source]

Create a subgraph from G.

Parameters:

G : Graph

Original graph

ind : list

Nodes to keep

Returns:

subG : Graph

Subgraph

Examples

>>> from pygsp import graphs
>>> import numpy as np
>>> W = np.arange(16).reshape(4, 4)
>>> G = graphs.Graph(W)
>>> ind = [3]
>>> subG = graphs.Graph.subgraph(G, ind)

This function create a subgraph from G taking only the nodes in ind.

update_graph_attr(*args, **kwargs)[source]

Recompute some attribute of the graph.

Parameters:

args: list of string

the arguments that will be not changed and not re-compute.

kwargs: Dictionnary

The arguments with their new value.

Examples

>>> from pygsp import graphs
>>> G = graphs.Ring(N=10)
>>> newW = G.W
>>> newW[1] = 1
>>> G.update_graph_attr('N', 'd', W=newW)

Updates all attributes of G excepted ‘N’ and ‘d’

Grid2d

class pygsp.graphs.Grid2d(Nv=16, Mv=None, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a 2 dimensional grid graph.

Parameters:

Nv : int

Number of vertices along the first dimension (default is 16)

Mv : int

Number of vertices along the second dimension (default is Nv)

Examples

>>> from pygsp import graphs
>>> G = graphs.Grid2d(Nv=32)

Torus

class pygsp.graphs.Torus(Nv=16, Mv=None, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a Torus graph.

Parameters:

Nv : int

Number of vertices along the first dimension (default is 16)

Mv : int

Number of vertices along the second dimension (default is Nv)

References

See [Str99] for more informations.

Examples

>>> from pygsp import graphs
>>> Nv = 32
>>> G = graphs.Torus(Nv=Nv)

Comet

class pygsp.graphs.Comet(Nv=32, k=12, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a Comet graph.

Parameters:

Nv : int

Number of vertices along the first dimension (default is 16)

Mv : int

Number of vertices along the second dimension (default is Nv)

Examples

>>> from pygsp import graphs
>>> G = graphs.Comet() # (== graphs.Comet(Nv=32, k=12))

LowStretchTree

class pygsp.graphs.LowStretchTree(k=6, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a low stretch tree graph.

Parameters:

k : int

2^k points on each side of the grid of vertices (default 6)

Examples

>>> from pygsp import graphs, plotting
>>> G = graphs.LowStretchTree(k=3)
>>> G.plot()

RandomRegular

class pygsp.graphs.RandomRegular(N=64, k=6, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a random regular graphs

The random regular graph has the property that every nodes is connected to ‘k’ other nodes.

Parameters:

N : int

Number of nodes (default is 64)

k : int

Number of connections of each nodes (default is 6)

Examples

>>> from pygsp import graphs
>>> G = graphs.RandomRegular()
createRandRegGraph(vertNum, deg, maxIter=10)[source]

Create a simple d-regular undirected graph.

simple = without loops or double edges d-reglar = each vertex is adjecent to d edges

Parameters:

vertNum : int

Number of vertices

deg : int

The degree of each vertex

maxIter : int

The maximum number of iterations

Returns:

A : sparse

Representation of the graph

isRegularGraph(A)[source]

Troubleshoot a given regular graph.

Parameters:A : sparse matrix

Ring

class pygsp.graphs.Ring(N=64, k=1, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a ring graph.

Parameters:

N : int

Number of vertices (default is 64)

k : int

Number of neighbors in each directions (default is 1)

Examples

>>> from pygsp import graphs
>>> G = graphs.Ring()

Community

class pygsp.graphs.Community(N=256, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a community graph.

Parameters:

N : int

Number of nodes (default = 256)

kwargs : Dict

Optional parameters for the construction of the Community graph

Nc : int

Number of communities (default = \(round(\sqrt{N}/2)\))

min_comm : int

Minimum size of the communities (default = round(N/Nc/3))

min_deg : int

Minimum degree of each node (default = 0, NOT IMPLEMENTED YET)

comm_sizes : int

Size of the communities (default = random)

size_ratio : float

Ratio between the radius of world and the radius of communities (default = 1)

world_density : float

Probability of a random edge between two different communities (default = 1/N)

comm_density : float

Probability of a random edge inside any community (default = None, not used if None)

k_neigh : int

Number of intra-community connections (default = None, not used if None or comm_density is defined)

epsilon : float

Max distance at which two nodes sharing a community are connected (default = \(sqrt(2\sqrt{N})/2\), not used if k_neigh or comm_density is defined)

Examples

>>> from pygsp import graphs
>>> G = graphs.Community()

Minnesota

class pygsp.graphs.Minnesota(connect=True)[source]

Bases: pygsp.graphs.graph.Graph

Create a community graph.

Parameters:

connect : bool

Change the graph to be connected. (default = True)

References

See [Gle]

Examples

>>> from pygsp import graphs
>>> G = graphs.Minnesota()

Sensor

class pygsp.graphs.Sensor(N=64, Nc=2, regular=False, n_try=50, distribute=False, connected=True, **kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create a random sensor graph.

Parameters:

N : int

Number of nodes (default = 64)

Nc : int

Minimum number of connections (default = 1)

regular : bool

Flag to fix the number of connections to nc (default = False)

n_try : int

Number of attempt to create the graph (default = 50)

distribute : bool

To distribute the points more evenly (default = False)

connected : bool

To force the graph to be connected (default = True)

Examples

>>> from pygsp import graphs
>>> G = graphs.Sensor(N=300)
create_weight_matrix(N, param_distribute, param_regular, param_Nc)[source]
get_nc_connection(W, param_nc)[source]

Airfoil

class pygsp.graphs.Airfoil(**kwargs)[source]

Bases: pygsp.graphs.graph.Graph

Create the airfoil graph.

Examples

>>> from pygsp import graphs
>>> G = graphs.Airfoil()

DavidSensorNet

class pygsp.graphs.DavidSensorNet(N=64)[source]

Bases: pygsp.graphs.graph.Graph

Create a sensor network.

Parameters:

N : int

Number of vertices (default = 64)

Examples

>>> from pygsp import graphs
>>> G = graphs.DavidSensorNet(N=500)

FullConnected

class pygsp.graphs.FullConnected(N=10)[source]

Bases: pygsp.graphs.graph.Graph

Create a fully connected graph.

Parameters:

N : int

Number of vertices (default = 10)

Examples

>>> from pygsp import graphs
>>> G = graphs.FullConnected(N=5)

Path

class pygsp.graphs.Path(N=16)[source]

Bases: pygsp.graphs.graph.Graph

Create a path graph.

Parameters:

N : int

Number of vertices (default = 32)

Examples

>>> from pygsp import graphs
>>> G = graphs.Path(N=16)

RandomRing

class pygsp.graphs.RandomRing(N=64)[source]

Bases: pygsp.graphs.graph.Graph

Create a ring graph.

Parameters:

N : int

Number of vertices (default = 64)

Examples

>>> from pygsp import graphs
>>> G = graphs.RandomRing(N=16)

SwissRoll

class pygsp.graphs.SwissRoll(N=400, a=1, b=4, dim=3, thresh=1e-06, s=None, noise=False, srtype='uniform')[source]

Bases: pygsp.graphs.graph.Graph

Create a swiss roll graph.

Parameters:

N : int

Number of vertices (default = 400)

a : int

(default = 1)

b : int

(default = 4)

dim : int

(default = 3)

thresh : float

(default = 1e-6)

s : float

sigma (default = sqrt(2./N))

noise : bool

Wether to add noise or not (default = False)

srtype : str

Swiss roll Type, possible arguments are ‘uniform’ or ‘classic’ (default = ‘uniform’)

Examples

>>> from pygsp import graphs
>>> G = graphs.SwissRoll()
rescale_center(x)[source]

Rescaling the dataset.

Rescaling the dataset, previously and mainly used in the SwissRoll graph.

Parameters:

x : ndarray

Dataset to be rescaled.

Returns:

r : ndarray

Rescaled dataset.

Examples

>>> from pygsp import utils
>>> utils.dummy(0, [1, 2, 3], True)
array([1, 2, 3])

Check Connectivity

Check Weights

pygsp.graphs.check_weights(W)[source]

Check the characteristics of the weights matrix.

Parameters:

W : weights matrix

The weights matrix to check

Returns:

A dict of bools containing informations about the matrix

has_inf_val : bool

True if the matrix has infinite values else false

has_nan_value : bool

True if the matrix has a not a number value else false

is_not_square : bool

True if the matrix is not square else false

diag_is_not_zero : bool

True if the matrix diagonal has not only zero value else false

Examples

>>> from scipy import sparse
>>> from pygsp.graphs import gutils
>>> np.random.seed(42)
>>> W = sparse.rand(10,10,0.2)
>>> weights_chara = gutils.check_weights(W)

Compute Fourier Basis

Create Laplacian

Estimate Lmax

Is directed

Symetrize