Inheritance diagram for nipy.algorithms.graph.graph:
This module implements two graph classes:
Graph: basic topological graph, i.e. vertices and edges. This kind of object only has topological properties
WeightedGraph (Graph): also has a value associated with edges, called weights, that are used in some computational procedures (e.g. path length computation). Importantly these objects are equivalent to square sparse matrices, which is used to perform certain computations.
This module also provides several functions to instantiate WeightedGraphs from data: - k nearest neighbours (where samples are rows of a 2D-array) - epsilon-neighbors (where sample rows of a 2D-array) - representation of the neighbors on a 3d grid (6-, 18- and 26-neighbors) - Minimum Spanning Tree (where samples are rows of a 2D-array)
Author: Bertrand Thirion, 2006–2011
Bases: object
Basic topological (non-weighted) directed Graph class
Member variables:
Properties:
Methods
adjacency() | returns the adjacency matrix of the graph as a sparse coo matrix |
cc() | Compte the different connected components of the graph. |
degrees() | Returns the degree of the graph vertices. |
get_E() | To get the number of edges in the graph |
get_V() | To get the number of vertices in the graph |
get_edges() | To get the graph’s edges |
get_vertices() | To get the graph’s vertices (as id) |
main_cc() | Returns the indexes of the vertices within the main cc |
set_edges(edges) | Sets the graph’s edges |
show([ax]) | Shows the graph as a planar one. |
to_coo_matrix() | Return adjacency matrix as coo sparse |
Constructor
Parameters: | V : int
E : int, optional
edges : None or shape (E, 2) array, optional
|
---|
returns the adjacency matrix of the graph as a sparse coo matrix
Returns: | adj: scipy.sparse matrix instance, :
|
---|
Compte the different connected components of the graph.
Returns: | label: array of shape(self.V), labelling of the vertices : |
---|
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 : |
Return adjacency matrix as coo sparse
Returns: | sp: scipy.sparse matrix instance, :
|
---|
Bases: nipy.algorithms.graph.graph.Graph
Basic weighted, directed graph class
Member variables:
Methods
Methods
adjacency() | returns the adjacency matrix of the graph as a sparse coo matrix |
anti_symmeterize() | anti-symmeterize self, i.e. produces the graph |
cc() | Compte the different connected components of the graph. |
cliques() | Extraction of the graphe cliques |
compact_neighb() | returns a compact representation of self |
copy() | returns a copy of self |
cut_redundancies() | Returns a graph with redundant edges removed: ecah edge (ab) is present ony once in the edge matrix: the correspondng weights are added. |
degrees() | Returns the degree of the graph vertices. |
dijkstra([seed]) | Returns all the [graph] geodesic distances starting from seed |
floyd([seed]) | Compute all the geodesic distances starting from seeds |
from_3d_grid(xyz[, k]) | Sets the graph to be the topological neighbours graph |
get_E() | To get the number of edges in the graph |
get_V() | To get the number of vertices in the graph |
get_edges() | To get the graph’s edges |
get_vertices() | To get the graph’s vertices (as id) |
get_weights() | |
is_connected() | States whether self is connected or not |
kruskal() | Creates the Minimum Spanning Tree of self using Kruskal’s algo. |
left_incidence() | Return left incidence matrix |
list_of_neighbors() | returns the set of neighbors of self as a list of arrays |
main_cc() | Returns the indexes of the vertices within the main cc |
normalize([c]) | Normalize the graph according to the index c |
remove_edges(valid) | Removes all the edges for which valid==0 |
remove_trivial_edges() | Removes trivial edges, i.e. |
right_incidence() | Return right incidence matrix |
set_edges(edges) | Sets the graph’s edges |
set_euclidian(X) | Compute the weights of the graph as the distances between the |
set_gaussian(X[, sigma]) | Compute the weights of the graph as a gaussian function |
set_weights(weights) | Set edge weights |
show([X, ax]) | Plots the current graph in 2D |
subgraph(valid) | Creates a subgraph with the vertices for which valid>0 |
symmeterize() | Symmeterize self, modify edges and weights so that |
to_coo_matrix() | Return adjacency matrix as coo sparse |
voronoi_diagram(seeds, samples) | Defines the graph as the Voronoi diagram (VD) |
voronoi_labelling(seed) | Performs a voronoi labelling of the graph |
Constructor
Parameters: | V : int
edges : (E, 2) array, type int
weights : (E, 2) array, type=int
|
---|
returns the adjacency matrix of the graph as a sparse coo matrix
Returns: | adj: scipy.sparse matrix instance, :
|
---|
anti-symmeterize self, i.e. produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix
Compte the different connected 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 a compact representation of self
Returns: | idx: array of of shape(self.V + 1): :
neighb: array of shape(self.E), concatenated list of neighbors : weights: array of shape(self.E), concatenated list of weights : |
---|
returns a copy of self
Returns a graph with redundant edges removed: ecah edge (ab) is present ony once in the edge matrix: the correspondng weights are added.
Returns: | the resulting WeightedGraph : |
---|
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 x
- seed (int, >-1, <self.V) or array of shape(p)
- edge(s) from which the distances are computed
Returns: | dg: array of shape (self.V), :
|
---|
Notes
It is mandatory that the graph weights are non-negative
Compute all the geodesic distances starting from seeds
Parameters: | seed= None: array of shape (nbseed), type np.int :
|
---|---|
Returns: | dg array of shape (nbseed, self.V) :
|
Notes
It is mandatory that the graph weights are non-negative. The algorithm proceeds by repeating Dijkstra’s algo for each seed. Floyd’s algo is not used (O(self.V)^3 complexity...)
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 : |
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
Creates the Minimum Spanning Tree of self using Kruskal’s algo. efficient is self is sparse
Returns: | K, WeightedGraph instance: the resulting MST : |
---|
Notes
If self contains several connected components, will have the same number k of connected components
Return left incidence matrix
Returns: | left_incid: list :
|
---|
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) : |
---|
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 :
|
---|
Notes
Note that when sum_{edge[e, .] == a } D[e] = 0, nothing is performed
Removes all the edges for which valid==0
Parameters: | valid : (self.E,) array |
---|
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 : |
---|
Return right incidence matrix
Returns: | right_incid: list :
|
---|
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 distance 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 : |
---|
Notes
When sigma == 0, the following value is used: sigma = sqrt(mean(||X[self.edges[:, 0], :]-X[self.edges[:, 1], :]||^2))
Set edge weights
Parameters: | weights: array :
|
---|
Plots the current graph in 2D
Parameters: | X : None or array of shape (self.V, 2)
ax: None or int, optional :
|
---|---|
Returns: | ax: axis handle : |
Notes
This should be used only for small graphs.
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 : |
Notes
The vertices are renumbered as [1..p] where p = sum(valid>0) when sum(valid==0) then None is returned
Symmeterize self, modify edges and weights so that self.adjacency becomes the symmetric part of the current self.adjacency.
Return adjacency matrix as coo sparse
Returns: | sp: scipy.sparse matrix instance :
|
---|
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) : |
---|
Notes
By default, the weights are a Gaussian function of the distance The implementation is not optimal
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 : |
returns a complete graph with n vertices
Returns the concatenation of the graphs G1 and G2 It is thus assumed that the vertices of G1 and G2 represent disjoint sets
Parameters: | G1, G2: the two WeightedGraph instances to be concatenated : |
---|---|
Returns: | G, WeightedGraph, the concatenated graph : |
Notes
This implies that the vertices of G corresponding to G2 are labeled [G1.V .. G1.V+G2.V]
Returns the eps-nearest-neighbours graph of the data
Parameters: | X, array of shape (n_samples, n_features), input data : eps, float, optional: the neighborhood width : |
---|---|
Returns: | the resulting graph instance : |
Utility that computes the six neighbors on a 3d grid
Parameters: | xyz: array of shape (n_samples, 3); grid coordinates of the points : k: neighboring system, equal to 6, 18, or 26 : |
---|---|
Returns: | i, j, d 3 arrays of shape (E), :
|
returns the k-nearest-neighbours graph of the data
Parameters: | X, array of shape (n_samples, n_features): the input data : k, int, optional: is the number of neighbours considered : |
---|---|
Returns: | the corresponding WeightedGraph instance : |
Notes
The knn system is symmeterized: if (ab) is one of the edges then (ba) is also included
Returns the connected comonents of a graph represented as a list of lists
Parameters: | lil: a list of list representing the graph neighbors : |
---|---|
Returns: | label a vector of shape len(lil): connected components labelling : |
Notes
Dramatically slow for non-sparse graphs
Returns the WeightedGraph that is the minimum Spanning Tree of X
Parameters: | X: data array, of shape(n_samples, n_features) : |
---|---|
Returns: | the corresponding WeightedGraph instance : |
Create graph as the set of topological neighbours of the three-dimensional coordinates set xyz, in the k-connectivity scheme
Parameters: | xyz: array of shape (nsamples, 3) and type np.int, : k = 18: the number of neighbours considered. (6, 18 or 26) : |
---|---|
Returns: | the WeightedGraph instance : |
Instantiates a weighted graph from a square 2D array
Parameters: | x: 2D array instance, the input array : |
---|---|
Returns: | wg: WeightedGraph instance : |
Instantiates a weighted graph from a (sparse) coo_matrix
Parameters: | x: scipy.sparse.coo_matrix instance, the input matrix : |
---|---|
Returns: | wg: WeightedGraph instance : |