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()
-
extract_components
()[source]¶ Split the graph into several connected components.
See the doc of is_connected for the method used to determine connectedness.
Returns: graphs : list
A list of graph structures. Each having its own node list and weight matrix. If the graph is directed, add into the info parameter the information about the source nodes and the sink nodes.
Examples
>>> from scipy import sparse >>> from pygsp import graphs >>> W = sparse.rand(10, 10, 0.2) >>> G = graphs.Graph(W=W) >>> components = G.extract_components() >>> has_sinks = 'sink' in components[0].info >>> sinks_0 = components[0].info['sink'] if has_sinks else []
-
is_connected
(force_recompute=False)[source]¶ 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.
- force_recompute: bool
- Force to recompute the connectivity if already known.
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
(force_recompute=False)[source]¶ Define if the graph has directed edges.
- force_recompute: bool
- Force to recompute the directedness if already known.
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()
-
set_coords
(kind='ring2D', **kwargs)[source]¶ Set coordinates for the vertices.
Parameters: kind : string
The kind of display. Default is ‘ring2D’. Accepting [‘community2D’, ‘manual’, ‘random2D’, ‘random3D’, ‘ring2D’, ‘spring’].
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()
-
show_spectrogramm
(**kwargs)[source]¶ Plot the spectrogramm for the graph object.
See plotting doc on spectrogramm.
-
subgraph
(ind)[source]¶ Create a subgraph from G keeping only the given indices.
Parameters: ind : list
Nodes to keep
Returns: sub_G : Graph
Subgraph
Examples
>>> from pygsp import graphs >>> import numpy as np >>> W = np.arange(16).reshape(4, 4) >>> G = graphs.Graph(W) >>> ind = [1, 3] >>> sub_G = G.subgraph(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¶
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
-
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)
Nc : int (optional)
Number of communities (default = \(round(\sqrt{N}/2)\))
min_comm : int (optional)
Minimum size of the communities (default = round(N/Nc/3))
min_deg : int (optional)
Minimum degree of each node (default = 0, NOT IMPLEMENTED YET)
comm_sizes : int (optional)
Size of the communities (default = random)
size_ratio : float (optional)
Ratio between the radius of world and the radius of communities (default = 1)
world_density : float (optional)
Probability of a random edge between two different communities (default = 1/N)
comm_density : float (optional)
Probability of a random edge inside any community (default = None, not used if None)
k_neigh : int (optional)
Number of intra-community connections (default = None, not used if None or comm_density is defined)
epsilon : float (optional)
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¶
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 = 2)
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)
Airfoil¶
DavidSensorNet¶
FullConnected¶
Logo¶
Path¶
RandomRing¶
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()
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)