neurospin.graph.graph

Module: neurospin.graph.graph

Inheritance diagram for nipy.neurospin.graph.graph:

Graph routines. Author: Bertrand Thirion (INRIA Futurs, Orsay, France), 2004-2008.

Classes

BipartiteGraph

class nipy.neurospin.graph.graph.BipartiteGraph(V, W, edges=None, weights=None)

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

Kruskal
Kruskal_dev
Voronoi_Labelling
Voronoi_diagram
WeightedDegree
adjacency
anti_symmeterize
cc
check_feature_matrices
cliques
complete
converse_edge
copy
cross_eps
cross_eps_robust
cross_knn
cut_redundancies
degrees
dijkstra
eps
floyd
from_3d_grid
from_adjacency
get_E
get_V
get_edges
get_vertices
get_weights
is_connected
knn
left_incidence
list_of_neighbors
main_cc
mst
normalize
remove_edges
remove_trivial_edges
reorder
right_incidence
set_edges
set_euclidian
set_gaussian
set_weights
show
skeleton
subgraph
subgraph_left
subgraph_right
symmeterize
to_neighb

__init__(V, W, edges=None, weights=None)

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

the edge array of the graph

weights=None: array of shape (self.E) :

the asociated weights array

Kruskal()

Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse

Returns:

K: WeightedGraph instance :

the resulting MST

Kruskal_dev()

Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse

Returns:

K: WeightedGraph instance :

the resulting MST

Voronoi_Labelling(seed)

label = self.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

fixme: how is dealt the case of diconnected graph ? :

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

WeightedDegree(c)

returns the sum of weighted degree of graph self

Parameters:

c (int): side selection :

if c==0 considering left side if c==1 considering right side of the edges

Returns:

wd : array of shape (self.V),

the resulting weighted degree

Note: slow implementation

adjacency()

Create the adjacency matrix of self

Returns:

A : an ((self.V*self.V),np.double) array

adjacency matrix of the graph

anti_symmeterize()

self.anti_symmeterize() anti-symmeterize the self , ie produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix

cc()

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 :

check_feature_matrices(X, Y)

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

and (self.W) or (self.W,p) respectively where p = common dimension of the features

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

complete() makes self a complete graph (i.e. each pair of vertices is an edge)

converse_edge()

Returns the index of the edge (j,i) for each edge (i,j) Note: a C implementation might be necessary

copy()

returns a copy of self

cross_eps(X, Y, eps=1.0)

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

and (self.W) or (self.W,p) respectively where p = common dimension of the features

eps=1, float : the neighbourhood size considered

Returns:

self.E (int) the number of edges of the resulting graph :

cross_eps_robust(X, Y, eps=1.0)

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

and (self.W) or (self.W,p) respectively where p = dimension of the features

eps=1, float, the neighbourhood size considered :

Returns:

self.E (int) the number of edges of the resulting graph :

cross_knn(X, Y, k=1)

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

and (self.W) or (self.W,p) respectively where p = dimension of the features

k=1, int is the number of neighbours considered :

Returns:

self.E, int the number of edges of the resulting graph :

cut_redundancies()

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 :

degrees()

returns the degree of the graph vertices

Returns:

rdegree: array of shape self.V, the right degree :

ldegree: array of shape self.V, the left degree :

dijkstra(seed=0)

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

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

eps(X, eps=1.0)

set the graph to be the eps-nearest-neighbours graph of the data

Parameters:

X array of shape (self.V) or (self.V,p) :

where p = dimension of the features data used for eps-neighbours computation

eps=1. (float), the neighborhood width :

Returns:

self.E the number of edges of the resulting graph :

floyd(seed=None)

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 :

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

from_3d_grid(xyz, k=18)

set the graph to be the topological neighbours graph of the thre-dimensional coordinate 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 :

from_adjacency(A)

sets the edges of self according to the adjacency matrix M

Parameters:M: array of shape(sef.V,self.V) :

get_E()

get_V()

get_edges()

get_vertices()

get_weights()

is_connected()

States whether self is connected or not

knn(X, k=1)

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

where p = dimension of the features data used for eps-neighbours computation

k=1 : is the number of neighbours considered

Returns:

- self.E (int): the number of edges of the resulting graph :

left_incidence()

Returns:

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

main_cc()

Returns the indexes of the vertices within the main cc

Returns:idx: array of shape (sizeof main cc) :

mst(X)

makes self the MST of the array X

Parameters:

X: an array of shape (self.V,dim) :

p is the feature dimension of X

Returns:

tl (float) the total length of the mst :

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

remove_edges(valid)

Removes all the edges for which valid==0

Parameters:valid, an array of shape (self.E) :

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 :

reorder(c=0)

Reorder the graph according to the index c

Parameters:

c=0 in {0,1,2}, index that designates the array :

according to which the vectors are jointly reordered c == 0 => reordering makes edges[:,0] increasing,

and edges[:,1] increasing for edges[:,0] fixed

c == 1 => reordering makes edges[:,1] increasing,

and edges[:,0] increasing for edges[:,1] fixed

c == 2 => reordering makes weights increasing

right_incidence()

Returns:

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 self.edges=edges if

1. edges has a correct size
2. edges take values in [0..V-1]*[0..W-1]

Parameters:edges: array of shape(self.E,2): set of candidate 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_gaussian(X, sigma=0)

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

the coordinate matrix of the embedding

sigma=0, float : the parameter of the gaussian function

set_weights(weights)

Parameters:weights : an array of shape(self.V), edges weights

show(X=None, ax=None)

a = self.show(X=None) plots the current graph in 2D

Parameters:

X=None, 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: ax handle, optional :

Returns:

ax: axis handle :

skeleton()

returns a MST that based on self.weights Note: self must be connected

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 :

subgraph_left(valid, renumb=True)

Extraction of a subgraph

Parameters:

valid, boolean array of shape self.V :

renumb, boolean: renumbering of the (left) edges :

subgraph_right(valid, renumb=True)

Extraction of a subgraph

Parameters:

valid, boolean array of shape self.V :

renumb, boolean: renumbering of the (right) edges :

symmeterize()

symmeterize the graphself , ie produces the graph whose adjacency matrix would be the symmetric part of its current adjacency matrix

to_neighb()

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

such that self.edges, self.weights is coded such that: for j in [ci[a] ci[a+1][, there exists en edge e so that (edge[e,0]=a,edge[e,1]=ne[j],self.weights[e] = we[j])

Graph

class nipy.neurospin.graph.graph.Graph(V, E=0)

This is the basic topological (non-weighted) directed Graph class fields : - V(int) = the number of vertices - E(int) = the number of edges - edges = array of int with shape (E,2) : the edges of the graph

Methods

adjacency
cc
complete
degrees
get_E
get_V
get_edges
get_vertices
main_cc
set_edges
show

__init__(V, E=0)

adjacency()

cc()

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 :

complete()

degrees()

returns the degree of the graph vertices

Returns:

rdegree: array of shape self.V, the right degree :

ldegree: array of shape self.V, the left degree :

get_E()

get_V()

get_edges()

get_vertices()

main_cc()

Returns the indexes of the vertices within the main cc

Returns:idx: array of shape (sizeof main cc) :

set_edges(edges)

sets self.edges=edges if 1. edges has a correct size 2. edges take values in [1..V]

show(ax=None)

show the graph as a planar graph

Parameters:ax, axis handle : Returns:ax, axis handle :

WeightedGraph

class nipy.neurospin.graph.graph.WeightedGraph(V, edges=None, weights=None)

Bases: nipy.neurospin.graph.graph.Graph

This is the basic weighted, directed graph class implemented in fff fields : V(int) = the number of vertices E(int) = the number of edges edges = array of int with shape (E,2):

the edges of the graph

weihghts = array of int with shape (E):

the weights/length of the graph edges

Methods

Kruskal
Kruskal_dev
Voronoi_Labelling
Voronoi_diagram
WeightedDegree
adjacency
anti_symmeterize
cc
cliques
complete
converse_edge
copy
cut_redundancies
degrees
dijkstra
eps
floyd
from_3d_grid
from_adjacency
get_E
get_V
get_edges
get_vertices
get_weights
is_connected
knn
left_incidence
list_of_neighbors
main_cc
mst
normalize
remove_edges
remove_trivial_edges
reorder
right_incidence
set_edges
set_euclidian
set_gaussian
set_weights
show
skeleton
subgraph
symmeterize
to_neighb

__init__(V, edges=None, weights=None)

Parameters:

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

edges=None: array of shape(E,2) :

the edge array of the graph

weights=None: array of shape (E) :

the asociated weights array

Kruskal()

Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse

Returns:

K: WeightedGraph instance :

the resulting MST

Kruskal_dev()

Creates the Minimum Spanning Tree self using Kruskal’s algo. efficient is self is sparse

Returns:

K: WeightedGraph instance :

the resulting MST

Voronoi_Labelling(seed)

label = self.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

fixme: how is dealt the case of diconnected graph ? :

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

WeightedDegree(c)

returns the sum of weighted degree of graph self

Parameters:

c (int): side selection :

if c==0 considering left side if c==1 considering right side of the edges

Returns:

wd : array of shape (self.V),

the resulting weighted degree

Note: slow implementation

adjacency()

Create the adjacency matrix of self

Returns:

A : an ((self.V*self.V),np.double) array

adjacency matrix of the graph

anti_symmeterize()

self.anti_symmeterize() anti-symmeterize the self , ie produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix

cc()

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 :

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

complete() makes self a complete graph (i.e. each pair of vertices is an edge)

converse_edge()

Returns the index of the edge (j,i) for each edge (i,j) Note: a C implementation might be necessary

copy()

returns a copy of self

cut_redundancies()

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 :

degrees()

returns the degree of the graph vertices

Returns:

rdegree: array of shape self.V, the right degree :

ldegree: array of shape self.V, the left degree :

dijkstra(seed=0)

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

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

eps(X, eps=1.0)

set the graph to be the eps-nearest-neighbours graph of the data

Parameters:

X array of shape (self.V) or (self.V,p) :

where p = dimension of the features data used for eps-neighbours computation

eps=1. (float), the neighborhood width :

Returns:

self.E the number of edges of the resulting graph :

floyd(seed=None)

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 :

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

from_3d_grid(xyz, k=18)

set the graph to be the topological neighbours graph of the thre-dimensional coordinate 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 :

from_adjacency(A)

sets the edges of self according to the adjacency matrix M

Parameters:M: array of shape(sef.V,self.V) :

get_E()

get_V()

get_edges()

get_vertices()

get_weights()

is_connected()

States whether self is connected or not

knn(X, k=1)

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

where p = dimension of the features data used for eps-neighbours computation

k=1 : is the number of neighbours considered

Returns:

- self.E (int): the number of edges of the resulting graph :

left_incidence()

Returns:

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

main_cc()

Returns the indexes of the vertices within the main cc

Returns:idx: array of shape (sizeof main cc) :

mst(X)

makes self the MST of the array X

Parameters:

X: an array of shape (self.V,dim) :

p is the feature dimension of X

Returns:

tl (float) the total length of the mst :

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

remove_edges(valid)

Removes all the edges for which valid==0

Parameters:valid, an array of shape (self.E) :

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 :

reorder(c=0)

Reorder the graph according to the index c

Parameters:

c=0 in {0,1,2}, index that designates the array :

according to which the vectors are jointly reordered c == 0 => reordering makes edges[:,0] increasing,

and edges[:,1] increasing for edges[:,0] fixed

c == 1 => reordering makes edges[:,1] increasing,

and edges[:,0] increasing for edges[:,1] fixed

c == 2 => reordering makes weights increasing

right_incidence()

Returns:

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 self.edges=edges if 1. edges has a correct size 2. edges take values in [1..V]

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_gaussian(X, sigma=0)

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

the coordinate matrix of the embedding

sigma=0, float : the parameter of the gaussian function

set_weights(weights)

Parameters:weights : an array of shape(self.V), edges weights

show(X=None, ax=None)

a = self.show(X=None) plots the current graph in 2D

Parameters:

X=None, 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: ax handle, optional :

Returns:

ax: axis handle :

skeleton()

returns a MST that based on self.weights Note: self must be connected

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 :

symmeterize()

symmeterize the graphself , ie produces the graph whose adjacency matrix would be the symmetric part of its current adjacency matrix

to_neighb()

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

such that self.edges, self.weights is coded such that: for j in [ci[a] ci[a+1][, there exists en edge e so that (edge[e,0]=a,edge[e,1]=ne[j],self.weights[e] = we[j])

Function

nipy.neurospin.graph.graph.concatenate_graphs(G1, G2)

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 :