Inheritance diagram for nipy.neurospin.graph.graph:
Graph routines. Author: Bertrand Thirion (INRIA Futurs, Orsay, France), 2004-2008.
Bases: nipy.neurospin.graph.graph.WeightedGraph
This is a bipartite graph structure, i.e. a graph there are two types of nodes, such that edges can exist only between nodes of type 1 and type 2 (not within) fields of this class: V (int,>0) the number of type 1 vertices W (int,>0) the number of type 2 vertices E : (int) the number of edges edges: array of shape (self.E,2) reprensenting pairwise neighbors weights, array of shape (self.E), +1/-1 for scending/descending links
Methods
Parameters : | V (int), the number of vertices of subset 1 : W (int), the number of vertices of subset 2 : edges=None: array of shape (self.E,2) :
weights=None: array of shape (self.E) :
|
---|
Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse
Returns : | K: WeightedGraph instance :
|
---|
Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse
Returns : | K: WeightedGraph instance :
|
---|
label = self.Voronoi_Labelling(seed) performs a voronoi labelling of the graph
Parameters : | seed array of shape (nseeds), type (np.int), :
|
---|---|
Returns : | - labels : array of shape (self.V) the labelling of the vertices fixme: how is dealt the case of diconnected graph ? : |
Defines the graph as the Voronoi diagram (VD) that links the seeds. The VD is defined using the sample points.
Parameters : | seeds: array of shape (self.V,dim) : samples: array of shape (nsamples,dim) : |
---|
returns the sum of weighted degree of graph self
Parameters : | c (int): side selection :
|
---|---|
Returns : | wd : array of shape (self.V),
|
Create the adjacency matrix of self
Returns : | A : an ((self.V*self.V),np.double) array
|
---|
self.anti_symmeterize() anti-symmeterize the self , ie produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix
Returns an array of labels corresponding to the different connex components of the graph.
Returns : | label: array of shape(self.V), labelling of the vertices : |
---|
checks wether the dismension of X and Y is coherent with self and possibly reshape it
Parameters : | X,Y arrays of shape (self.V) or (self.V,p) :
|
---|
Extraction of the graphe cliques these are defined using replicator dynamics equations
Returns : | - cliques: array of shape (self.V), type (np.int) :
|
---|
Returns the index of the edge (j,i) for each edge (i,j) Note: a C implementation might be necessary
returns a copy of self
set the graph to be the eps-neighbours graph of from X to Y
Parameters : | X,Y arrays of shape (self.V) or (self.V,p) :
eps=1, float : the neighbourhood size considered |
---|---|
Returns : | self.E (int) the number of edges of the resulting graph : |
Set the graph to be the eps-neighbours graph of from X to Y this procedure is robust in the sense that for each row of X at least one matching row Y is found, even though the distance is greater than eps.
Parameters : | X,Y: arrays of shape (self.V) or (self.V,p) :
eps=1, float, the neighbourhood size considered : |
---|---|
Returns : | self.E (int) the number of edges of the resulting graph : |
set the graph to be the k-nearest-neighbours graph of from X to Y
Parameters : | X,Y arrays of shape (self.V) or (self.V,p) :
k=1, int is the number of neighbours considered : |
---|---|
Returns : | self.E, int the number of edges of the resulting graph : |
self.cut_redudancies() Remove possibly redundant edges: if an edge (ab) is present twice in the edge matrix, only the first instance in kept. The weights are processed accordingly
Returns : | - E(int): the number of edges, self.E : |
---|
Returns the degree of the graph vertices.
Returns : | rdegree: (array, type=int, shape=(self.V,)), the right degrees : ldegree: (array, type=int, shape=(self.V,)), the left degrees : |
---|
returns all the [graph] geodesic distances starting from seed it is mandatory that the graph weights are non-negative
Parameters : | seed (int, >-1,<self.V) or array of shape(p) :
|
---|---|
Returns : | dg: array of shape (self.V) , :
|
Sets the graph to be the eps-nearest-neighbours graph of the data
Parameters : | X: array of shape (self.V) or (self.V,p) :
eps=1. (float), the neighborhood width : |
---|---|
Returns : | self.E the number of edges of the resulting graph : |
Compute all the geodesic distances starting from seeds it is mandatory that the graph weights are non-negative
Parameters : | seed= None: array of shape (nbseed), type np.int :
|
---|---|
Returns : | dg array of shape (nbseed,self.V) :
|
Sets the graph to be the topological neighbours graph of the three-dimensional coordinates set xyz, in the k-connectivity scheme
Parameters : | xyz: array of shape (self.V, 3) and type np.int, : k = 18: the number of neighbours considered. (6, 18 or 26) : |
---|---|
Returns : | E(int): the number of edges of self : |
sets the edges of self according to the adjacency matrix M
Parameters : | M: array of shape(sef.V, self.V) : |
---|
To get the number of edges in the graph
To get the number of vertices in the graph
To get the graph’s edges
To get the graph’s vertices (as id)
States whether self is connected or not
E = knn(X, k) set the graph to be the k-nearest-neighbours graph of the data
Parameters : | X array of shape (self.V) or (self.V,p) :
k=1 : is the number of neighbours considered |
---|---|
Returns : | - self.E (int): the number of edges of the resulting graph : |
Returns : | the left incidence matrix of self :
|
---|
returns the set of neighbors of self as a list of arrays
Returns the indexes of the vertices within the main cc
Returns : | idx: array of shape (sizeof main cc) : |
---|
makes self the MST of the array X
Parameters : | X: an array of shape (self.V,dim) :
|
---|---|
Returns : | tl (float) the total length of the mst : |
Normalize the graph according to the index c Normalization means that the sum of the edges values that go into or out each vertex must sum to 1
Parameters : | c=0 in {0,1,2}, optional: index that designates the way :
|
---|
Removes all the edges for which valid==0
Parameters : | valid, an array of shape (self.E) : |
---|
Removes trivial edges, i.e. edges that are (vv)-like self.weights and self.E are corrected accordingly
Returns : | - self.E (int): The number of edges : |
---|
Reorder the graph according to the index c
Parameters : | c=0 in {0,1,2}, index that designates the array :
|
---|
Returns : | the right incidence matrix of self :
|
---|
Parameters : | edges: array of shape(self.E,2): set of candidate edges : |
---|
Compute the weights of the graph as the distances between the corresponding rows of X, which represents an embdedding of self
Parameters : | X array of shape (self.V, edim), :
|
---|
Compute the weights of the graph as a gaussian function of the dinstance between the corresponding rows of X, which represents an embdedding of self
Parameters : | X array of shape (self.V,dim) :
sigma=0, float : the parameter of the gaussian function |
---|
Parameters : | weights : an array of shape(self.V), edges weights |
---|
a = self.show(X=None) plots the current graph in 2D
Parameters : | X=None, array of shape (self.V,2) :
ax: ax handle, optional : |
---|---|
Returns : | ax: axis handle : |
returns a MST that based on self.weights Note: self must be connected
Creates a subgraph with the vertices for which valid>0 and with the correponding set of edges
Parameters : | valid array of shape (self.V): nonzero for vertices to be retained : |
---|---|
Returns : | G WeightedGraph instance, the desired subgraph of self : |
Extraction of a subgraph
Parameters : | valid, boolean array of shape self.V : renumb, boolean: renumbering of the (left) edges : |
---|
Extraction of a subgraph
Parameters : | valid, boolean array of shape self.V : renumb, boolean: renumbering of the (right) edges : |
---|
symmeterize the graphself , ie produces the graph whose adjacency matrix would be the symmetric part of its current adjacency matrix
Returns : | sp: scipy.sparse matrix instance, :
|
---|
converts the graph to a neighboring system The neighboring system is nothing but a (sparser) representation of the edge matrix
Returns : | ci, ne, we: arrays of shape (self.V+1), (self.E), (self.E) :
|
---|
Bases: object
This is the basic topological (non-weighted) directed Graph class fields:
Methods
adjacency | |
cc | |
complete | |
degrees | |
get_E | |
get_V | |
get_edges | |
get_vertices | |
main_cc | |
set_edges | |
show |
Constructor
Parameters : | - V (int): the number of vertices : - E (int): the number of edges : |
---|
Builds the adjacency matrix of the graph
Returns an array of labels corresponding to the different connex components of the graph.
Returns : | label: array of shape(self.V), labelling of the vertices : |
---|
Transforms the graph into a complete one.
Returns the degree of the graph vertices.
Returns : | rdegree: (array, type=int, shape=(self.V,)), the right degrees : ldegree: (array, type=int, shape=(self.V,)), the left degrees : |
---|
To get the number of edges in the graph
To get the number of vertices in the graph
To get the graph’s edges
To get the graph’s vertices (as id)
Returns the indexes of the vertices within the main cc
Returns : | idx: array of shape (sizeof main cc) : |
---|
Sets the graph’s edges
Shows the graph as a planar one.
Parameters : | ax, axis handle : |
---|---|
Returns : | ax, axis handle : |
Bases: nipy.neurospin.graph.graph.Graph
This is the basic weighted, directed graph class implemented in fff fields:
Methods
Constructor
Parameters : | - V (int > 0): the number of vertices : - edges (array, type=int, shape=(E,2)): edges of the graph : - weights (array, type=int, shape=(E,)): weights/lenghts of the edges : |
---|
Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse
Returns : | K: WeightedGraph instance :
|
---|
Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse
Returns : | K: WeightedGraph instance :
|
---|
label = self.Voronoi_Labelling(seed) performs a voronoi labelling of the graph
Parameters : | seed array of shape (nseeds), type (np.int), :
|
---|---|
Returns : | - labels : array of shape (self.V) the labelling of the vertices fixme: how is dealt the case of diconnected graph ? : |
Defines the graph as the Voronoi diagram (VD) that links the seeds. The VD is defined using the sample points.
Parameters : | seeds: array of shape (self.V,dim) : samples: array of shape (nsamples,dim) : |
---|
returns the sum of weighted degree of graph self
Parameters : | c (int): side selection :
|
---|---|
Returns : | wd : array of shape (self.V),
|
Create the adjacency matrix of self
Returns : | A : an ((self.V*self.V),np.double) array
|
---|
self.anti_symmeterize() anti-symmeterize the self , ie produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix
Returns an array of labels corresponding to the different connex components of the graph.
Returns : | label: array of shape(self.V), labelling of the vertices : |
---|
Extraction of the graphe cliques these are defined using replicator dynamics equations
Returns : | - cliques: array of shape (self.V), type (np.int) :
|
---|
Returns the index of the edge (j,i) for each edge (i,j) Note: a C implementation might be necessary
returns a copy of self
self.cut_redudancies() Remove possibly redundant edges: if an edge (ab) is present twice in the edge matrix, only the first instance in kept. The weights are processed accordingly
Returns : | - E(int): the number of edges, self.E : |
---|
Returns the degree of the graph vertices.
Returns : | rdegree: (array, type=int, shape=(self.V,)), the right degrees : ldegree: (array, type=int, shape=(self.V,)), the left degrees : |
---|
returns all the [graph] geodesic distances starting from seed it is mandatory that the graph weights are non-negative
Parameters : | seed (int, >-1,<self.V) or array of shape(p) :
|
---|---|
Returns : | dg: array of shape (self.V) , :
|
Sets the graph to be the eps-nearest-neighbours graph of the data
Parameters : | X: array of shape (self.V) or (self.V,p) :
eps=1. (float), the neighborhood width : |
---|---|
Returns : | self.E the number of edges of the resulting graph : |
Compute all the geodesic distances starting from seeds it is mandatory that the graph weights are non-negative
Parameters : | seed= None: array of shape (nbseed), type np.int :
|
---|---|
Returns : | dg array of shape (nbseed,self.V) :
|
Sets the graph to be the topological neighbours graph of the three-dimensional coordinates set xyz, in the k-connectivity scheme
Parameters : | xyz: array of shape (self.V, 3) and type np.int, : k = 18: the number of neighbours considered. (6, 18 or 26) : |
---|---|
Returns : | E(int): the number of edges of self : |
sets the edges of self according to the adjacency matrix M
Parameters : | M: array of shape(sef.V, self.V) : |
---|
To get the number of edges in the graph
To get the number of vertices in the graph
To get the graph’s edges
To get the graph’s vertices (as id)
States whether self is connected or not
E = knn(X, k) set the graph to be the k-nearest-neighbours graph of the data
Parameters : | X array of shape (self.V) or (self.V,p) :
k=1 : is the number of neighbours considered |
---|---|
Returns : | - self.E (int): the number of edges of the resulting graph : |
Returns : | the left incidence matrix of self :
|
---|
returns the set of neighbors of self as a list of arrays
Returns the indexes of the vertices within the main cc
Returns : | idx: array of shape (sizeof main cc) : |
---|
makes self the MST of the array X
Parameters : | X: an array of shape (self.V,dim) :
|
---|---|
Returns : | tl (float) the total length of the mst : |
Normalize the graph according to the index c Normalization means that the sum of the edges values that go into or out each vertex must sum to 1
Parameters : | c=0 in {0,1,2}, optional: index that designates the way :
|
---|
Removes all the edges for which valid==0
Parameters : | valid, an array of shape (self.E) : |
---|
Removes trivial edges, i.e. edges that are (vv)-like self.weights and self.E are corrected accordingly
Returns : | - self.E (int): The number of edges : |
---|
Reorder the graph according to the index c
Parameters : | c=0 in {0,1,2}, index that designates the array :
|
---|
Returns : | the right incidence matrix of self :
|
---|
Sets the graph’s edges
Compute the weights of the graph as the distances between the corresponding rows of X, which represents an embdedding of self
Parameters : | X array of shape (self.V, edim), :
|
---|
Compute the weights of the graph as a gaussian function of the dinstance between the corresponding rows of X, which represents an embdedding of self
Parameters : | X array of shape (self.V,dim) :
sigma=0, float : the parameter of the gaussian function |
---|
Parameters : | weights : an array of shape(self.V), edges weights |
---|
a = self.show(X=None) plots the current graph in 2D
Parameters : | X=None, array of shape (self.V,2) :
ax: ax handle, optional : |
---|---|
Returns : | ax: axis handle : |
returns a MST that based on self.weights Note: self must be connected
Creates a subgraph with the vertices for which valid>0 and with the correponding set of edges
Parameters : | valid array of shape (self.V): nonzero for vertices to be retained : |
---|---|
Returns : | G WeightedGraph instance, the desired subgraph of self : |
symmeterize the graphself , ie produces the graph whose adjacency matrix would be the symmetric part of its current adjacency matrix
Returns : | sp: scipy.sparse matrix instance, :
|
---|
converts the graph to a neighboring system The neighboring system is nothing but a (sparser) representation of the edge matrix
Returns : | ci, ne, we: arrays of shape (self.V+1), (self.E), (self.E) :
|
---|
Sets G as the concatenation of the graphs G1 and G2 It is thus assumed that the vertices of G1 and G2 are disjoint sets
Parameters : | G1,G2: the two WeightedGraph instances to be concatenated : |
---|---|
Returns : | G, WeightedGraph, the concatenated graph : |
Instantiates a weighted graph from a square 2D array
Parameters : | x: 2D array instance, :
|
---|---|
Returns : | wg: WeightedGraph instance : |
Instantiates a weighted graph from a (sparse) coo_matrix
Parameters : | x: scipy.sparse.coo_matrix instance, :
|
---|---|
Returns : | wg: WeightedGraph instance : |