algorithms.graph.graph¶
Module: algorithms.graph.graph¶
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
Classes¶
Graph¶
-
class
nipy.algorithms.graph.graph.Graph(V, E=0, edges=None)[source]¶ Bases:
objectBasic topological (non-weighted) directed Graph class
Member variables:
V (int > 0): the number of vertices
E (int >= 0): the number of edges
Properties:
vertices (list, type=int, shape=(V,)) vertices id
edges (list, type=int, shape=(E,2)): edges as vertices id tuples
-
__init__(V, E=0, edges=None)[source]¶ Constructor
- Parameters
V : int
the number of vertices
E : int, optional
the number of edges
edges : None or shape (E, 2) array, optional
edges of graph
-
set_edges(edges)[source]¶ Sets the graph’s edges
Preconditions:
edges has a correct size
edges take values in [1..V]
-
adjacency()[source]¶ returns the adjacency matrix of the graph as a sparse coo matrix
- Returns
adj: scipy.sparse matrix instance,
that encodes the adjacency matrix of self
-
cc()[source]¶ Compte the different connected components of the graph.
- Returns
label: array of shape(self.V), labelling of the vertices
-
degrees()[source]¶ 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
-
main_cc()[source]¶ Returns the indexes of the vertices within the main cc
- Returns
idx: array of shape (sizeof main cc)
WeightedGraph¶
-
class
nipy.algorithms.graph.graph.WeightedGraph(V, edges=None, weights=None)[source]¶ Bases:
nipy.algorithms.graph.graph.GraphBasic weighted, directed graph class
Member variables:
V (int): the number of vertices
E (int): the number of edges
Methods
vertices (list, type=int, shape=(V,)): vertices id
edges (list, type=int, shape=(E,2)): edges as vertices id tuples
weights (list, type=int, shape=(E,)): weights / lengths of the graph’s edges
-
__init__(V, edges=None, weights=None)[source]¶ Constructor
- Parameters
V : int
(int > 0) the number of vertices
edges : (E, 2) array, type int
edges of the graph
weights : (E, 2) array, type=int
weights/lenghts of the edges
-
set_weights(weights)[source]¶ Set edge weights
- Parameters
weights: array
array shape(self.V): edges weights
-
from_3d_grid(xyz, k=18)[source]¶ 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
-
cut_redundancies()[source]¶ 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
-
dijkstra(seed=0)[source]¶ 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),
the graph distance dg from ant vertex to the nearest seed
Notes
It is mandatory that the graph weights are non-negative
-
compact_neighb()[source]¶ returns a compact representation of self
- Returns
idx: array of of shape(self.V + 1):
the positions where to find the neighors of each node within neighb and weights
neighb: array of shape(self.E), concatenated list of neighbors
weights: array of shape(self.E), concatenated list of weights
-
floyd(seed=None)[source]¶ Compute all the geodesic distances starting from seeds
- Parameters
seed= None: array of shape (nbseed), type np.int
vertex indexes from which the distances are computed if seed==None, then every edge is a seed point
- Returns
dg array of shape (nbseed, self.V)
the graph distance dg from each seed to any vertex
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…)
-
normalize(c=0)[source]¶ 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
according to which D is normalized c == 0 => for each vertex a, sum{edge[e, 0]=a} D[e]=1 c == 1 => for each vertex b, sum{edge[e, 1]=b} D[e]=1 c == 2 => symmetric (‘l2’) normalization
Notes
Note that when sum_{edge[e, .] == a } D[e] = 0, nothing is performed
-
set_euclidian(X)[source]¶ 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),
the coordinate matrix of the embedding
-
set_gaussian(X, sigma=0)[source]¶ 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)
the coordinate matrix of the embedding
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))
-
symmeterize()[source]¶ Symmeterize self, modify edges and weights so that self.adjacency becomes the symmetric part of the current self.adjacency.
-
anti_symmeterize()[source]¶ anti-symmeterize self, i.e. produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix
-
voronoi_labelling(seed)[source]¶ Performs a voronoi labelling of the graph
- Parameters
seed: array of shape (nseeds), type (np.int),
vertices from which the cells are built
- Returns
labels: array of shape (self.V) the labelling of the vertices
-
cliques()[source]¶ Extraction of the graphe cliques these are defined using replicator dynamics equations
- Returns
cliques: array of shape (self.V), type (np.int)
labelling of the vertices according to the clique they belong to
-
remove_trivial_edges()[source]¶ 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
-
subgraph(valid)[source]¶ 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
-
kruskal()[source]¶ 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
-
voronoi_diagram(seeds, samples)[source]¶ 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
-
show(X=None, ax=None)[source]¶ Plots the current graph in 2D
- Parameters
X : None or array of shape (self.V, 2)
a set of coordinates that can be used to embed the vertices in 2D. If X.shape[1]>2, a svd reduces X for display. By default, the graph is presented on a circle
ax: None or int, optional
ax handle
- Returns
ax: axis handle
Notes
This should be used only for small graphs.
-
remove_edges(valid)[source]¶ Removes all the edges for which valid==0
- Parameters
valid : (self.E,) array
-
left_incidence()[source]¶ Return left incidence matrix
- Returns
left_incid: list
the left incidence matrix of self as a list of lists: i.e. the list[[e.0.0, .., e.0.i(0)], .., [e.V.0, E.V.i(V)]] where e.i.j is the set of edge indexes so that e.i.j[0] = i
-
right_incidence()[source]¶ Return right incidence matrix
- Returns
right_incid: list
the right incidence matrix of self as a list of lists: i.e. the list[[e.0.0, .., e.0.i(0)], .., [e.V.0, E.V.i(V)]] where e.i.j is the set of edge indexes so that e.i.j[1] = i
-
to_coo_matrix()[source]¶ Return adjacency matrix as coo sparse
- Returns
sp: scipy.sparse matrix instance
that encodes the adjacency matrix of self
-
adjacency()¶ returns the adjacency matrix of the graph as a sparse coo matrix
- Returns
adj: scipy.sparse matrix instance,
that encodes the adjacency matrix of self
-
cc()¶ Compte the different connected components of the graph.
- Returns
label: array of shape(self.V), labelling of the vertices
-
degrees()¶ 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
-
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
- Returns
idx: array of shape (sizeof main cc)
-
set_edges(edges)¶ Sets the graph’s edges
Preconditions:
edges has a correct size
edges take values in [1..V]
Functions¶
-
nipy.algorithms.graph.graph.concatenate_graphs(G1, G2)[source]¶ 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]
-
nipy.algorithms.graph.graph.eps_nn(X, eps=1.0)[source]¶ 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
-
nipy.algorithms.graph.graph.graph_3d_grid(xyz, k=18)[source]¶ 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),
where E is the number of edges in the resulting graph (i, j) represent the edges, d their weights
-
nipy.algorithms.graph.graph.knn(X, k=1)[source]¶ 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
-
nipy.algorithms.graph.graph.lil_cc(lil)[source]¶ 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
-
nipy.algorithms.graph.graph.mst(X)[source]¶ 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
-
nipy.algorithms.graph.graph.wgraph_from_3d_grid(xyz, k=18)[source]¶ 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