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()
-
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¶
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)
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¶
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)
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)