algorithms.graph.field

Module: algorithms.graph.field

Inheritance diagram for nipy.algorithms.graph.field:

Inheritance diagram of nipy.algorithms.graph.field

This module implements the Field class, which simply a WeightedGraph (see the graph.py) module, plus an arrray that yields (possibly multi-dimnesional) features associated with graph vertices. This allows some kinds of computations (all thoses relating to mathematical morphology, diffusion etc.)

Certain functions are provided to Instantiate Fields easily, given a WeightedGraph and feature data.

Author:Bertrand Thirion, 2006–2011

Class

Field

class nipy.algorithms.graph.field.Field(V, edges=None, weights=None, field=None)

Bases: nipy.algorithms.graph.graph.WeightedGraph

This is the basic field structure,
which contains the weighted graph structure plus an array of data (the ‘field’)
field is an array of size(n, p)
where n is the number of vertices of the graph and p is the field dimension

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
closing([nbiter]) Morphological closing of the field data.
compact_neighb() returns a compact representation of self
constrained_voronoi(seed) Voronoi parcellation of the field starting from the input seed
copy() copy function
custom_watershed([refdim, th]) customized watershed analysis of the field.
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.
diffusion([nbiter]) diffusion of the field data in the weighted graph structure
dijkstra([seed]) Returns all the [graph] geodesic distances starting from seed
dilation([nbiter, fast]) Morphological dilation of the field data, changed in place
erosion([nbiter]) Morphological openeing of the field
floyd([seed]) Compute all the geodesic distances starting from seeds
from_3d_grid(xyz[, k]) Sets the graph to be the topological neighbours graph
geodesic_kmeans([seeds, label, maxiter, …]) Geodesic k-means algorithm i.e.
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_field()
get_local_maxima([refdim, th]) Look for the local maxima of one dimension (refdim) of self.field
get_vertices() To get the graph’s vertices (as id)
get_weights()
highest_neighbor([refdim]) Computes the neighbor with highest field value along refdim
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
local_maxima([refdim, th]) Returns all the local maxima of a field
main_cc() Returns the indexes of the vertices within the main cc
normalize([c]) Normalize the graph according to the index c
opening([nbiter]) Morphological opening of the field data.
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_field(field)
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
subfield(valid) Returns a subfield of self, with only vertices such that valid > 0
subgraph(valid) Creates a subgraph with the vertices for which valid>0
symmeterize() Symmeterize self, modify edges and weights so that self.adjacency becomes the symmetric part of the current self.adjacency.
threshold_bifurcations([refdim, th]) Analysis of the level sets of the field:
to_coo_matrix() Return adjacency matrix as coo sparse
voronoi_diagram(seeds, samples) Defines the graph as the Voronoi diagram (VD) that links the seeds.
voronoi_labelling(seed) Performs a voronoi labelling of the graph
ward(nbcluster) Ward’s clustering of self
__init__(V, edges=None, weights=None, field=None)
Parameters:

V (int > 0) the number of vertices of the graph :

edges=None: the edge array of the graph :

weights=None: the asociated weights array :

field=None: the field data itself :

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

anti_symmeterize()

anti-symmeterize self, i.e. produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix

cc()

Compte the different connected components of the graph.

Returns:label: array of shape(self.V), labelling of the vertices :
cliques()

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

closing(nbiter=1)

Morphological closing of the field data. self.field is changed inplace

Parameters:nbiter=1 : the number of iterations required
compact_neighb()

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 :

constrained_voronoi(seed)

Voronoi parcellation of the field starting from the input seed

Parameters:seed: int array of shape(p), the input seeds :
Returns:label: The resulting labelling of the data :
copy()

copy function

custom_watershed(refdim=0, th=-inf)

customized watershed analysis of the field. Note that bassins are found around each maximum (and not minimum as conventionally)

Parameters:

refdim: int, optional :

th: float optional, threshold of the field :

Returns:

idx: array of shape (nbassins) :

indices of the vertices that are local maxima

label : array of shape (self.V)

labelling of the vertices according to their bassin

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.

Returns:the resulting WeightedGraph :
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 :

diffusion(nbiter=1)

diffusion of the field data in the weighted graph structure self.field is changed inplace

Parameters:nbiter: int, optional the number of iterations required :

Notes

The process is run for all the dimensions of the field

dijkstra(seed=0)

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

dilation(nbiter=1, fast=True)

Morphological dilation of the field data, changed in place

Parameters:nbiter: int, optional, the number of iterations required :
erosion(nbiter=1)

Morphological openeing of the field

Parameters:nbiter: int, optional, the number of iterations required :
floyd(seed=None)

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…)

from_3d_grid(xyz, k=18)

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 :

geodesic_kmeans(seeds=None, label=None, maxiter=100, eps=0.0001, verbose=0)

Geodesic k-means algorithm i.e. obtention of clusters that are topologically connected and minimally variable concerning the information of self.field

Parameters:

seeds: array of shape(p), optional, :

initial indices of the seeds within the field if seeds==None the labels are used as initialization

labels: array of shape(self.V) initial labels, optional, :

it is expected that labels take their values in a certain range (0..lmax) if Labels==None, this is not used if seeds==None and labels==None, an ewxception is raised

maxiter: int, optional, :

maximal number of iterations

eps: float, optional, :

increase of inertia at which convergence is declared

Returns:

seeds: array of shape (p), the final seeds :

label : array of shape (self.V), the resulting field label

J: float, inertia value :

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_field()
get_local_maxima(refdim=0, th=-inf)

Look for the local maxima of one dimension (refdim) of self.field

Parameters:

refdim (int) the field dimension over which the maxima are looked after :

th = float, optional :

threshold so that only values above th are considered

Returns:

idx: array of shape (nmax) :

indices of the vertices that are local maxima

depth: array of shape (nmax) :

topological depth of the local maxima : depth[idx[i]] = q means that idx[i] is a q-order maximum

get_vertices()

To get the graph’s vertices (as id)

get_weights()
highest_neighbor(refdim=0)

Computes the neighbor with highest field value along refdim

Parameters:

refdim: int, optional, :

the dimension of the field under consideration

Returns:

hneighb: array of shape(self.V), :

index of the neighbor with highest value

is_connected()

States whether self is connected or not

kruskal()

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

left_incidence()

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

list_of_neighbors()

returns the set of neighbors of self as a list of arrays

local_maxima(refdim=0, th=-inf)

Returns all the local maxima of a field

Parameters:

refdim (int) field dimension over which the maxima are looked after :

th: float, optional :

threshold so that only values above th are considered

Returns:

depth: array of shape (nmax) :

a labelling of the vertices such that depth[v] = 0 if v is not a local maximum depth[v] = 1 if v is a first order maximum … depth[v] = q if v is a q-order maximum

main_cc()

Returns the indexes of the vertices within the main cc

Returns:idx: array of shape (sizeof main cc) :
normalize(c=0)

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

opening(nbiter=1)

Morphological opening of the field data. self.field is changed inplace

Parameters:nbiter: int, optional, the number of iterations required :
remove_edges(valid)

Removes all the edges for which valid==0

Parameters:valid : (self.E,) array
remove_trivial_edges()

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 :
right_incidence()

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

set_edges(edges)

Sets the graph’s edges

set_euclidian(X)

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_field(field)
set_gaussian(X, sigma=0)

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

set_weights(weights)

Set edge weights

Parameters:

weights: array :

array shape(self.V): edges weights

show(X=None, ax=None)

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.

subfield(valid)

Returns a subfield of self, with only vertices such that valid > 0

Parameters:

valid: array of shape (self.V), :

nonzero for vertices to be retained

Returns:

F: Field instance, :

the desired subfield of self

Notes

The vertices are renumbered as [1..p] where p = sum(valid>0) when sum(valid) == 0 then None is returned

subgraph(valid)

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

Symmeterize self, modify edges and weights so that self.adjacency becomes the symmetric part of the current self.adjacency.

threshold_bifurcations(refdim=0, th=-inf)

Analysis of the level sets of the field: Bifurcations are defined as changes in the topology in the level sets when the level (threshold) is varied This can been thought of as a kind of Morse analysis

Parameters:

th: float, optional, :

threshold so that only values above th are considered

Returns:

idx: array of shape (nlsets) :

indices of the vertices that are local maxima

height: array of shape (nlsets) :

the depth of the local maxima depth[idx[i]] = q means that idx[i] is a q-order maximum Note that this is also the diameter of the basins associated with local maxima

parents: array of shape (nlsets) :

the label of the maximum which dominates each local maximum i.e. it describes the hierarchy of the local maxima

label: array of shape (self.V) :

a labelling of thevertices according to their bassin

to_coo_matrix()

Return adjacency matrix as coo sparse

Returns:

sp: scipy.sparse matrix instance :

that encodes the adjacency matrix of self

voronoi_diagram(seeds, samples)

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

voronoi_labelling(seed)

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 :

ward(nbcluster)

Ward’s clustering of self

Parameters:

nbcluster: int, :

the number of desired clusters

Returns:

label: array of shape (self.V) :

the resulting field label

J (float): the resulting inertia :

Functions

nipy.algorithms.graph.field.field_from_coo_matrix_and_data(x, data)

Instantiates a weighted graph from a (sparse) coo_matrix

Parameters:

x: (V, V) scipy.sparse.coo_matrix instance, :

the input matrix

data: array of shape (V, dim), :

the field data

Returns:

ifield: resulting Field instance :

nipy.algorithms.graph.field.field_from_graph_and_data(g, data)

Instantiate a Fieldfrom a WeightedGraph plus some feature data Parameters ———- x: (V, V) scipy.sparse.coo_matrix instance,

the input matrix
data: array of shape (V, dim),
the field data
Returns:ifield: resulting field instance :