Table Of Contents

Previous topic

neurospin.graph.field

Next topic

neurospin.graph.hroi

This Page

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

__init__(V, W, edges=None, weights=None)
INPUT: V: the number of edges of the graph edges=None: the edge array of the graph weights=None: the asociated weights array This is the build function
check_feature_matrices(X, Y)
self.check_feature_matrices(self,X,Y) checks wether the dismension of X and Y is coherent with self and possibly reshape it INPUT: - The arrays X,Y is assumed to be of size (self.V) or (self.V,p) and (self.W) or (self.W,p) respectively where p = dimension of the features
copy()
G = self.copy() returns a copy of self
cross_eps(X, Y, eps=1.0)
E = self.cross_eps(X,Y,eps=1.) set the graph to be the eps-neighbours graph of from X to Y INPUT: - The arrays X,Y is assumed to be of size (self.V) or (self.V,p) and (self.W) or (self.W,p) respectively where p = dimension of the features - eps=1 : the neighbourhood size considered OUTPUT: - the number of edges of the resulting graph, self.E NOTE: - It is assumed that the features are embedded in a (locally) Euclidian space - for the sake of speed it is advisable to give a PCA-preprocessed matrices X and Y.
cross_eps_robust(X, Y, eps=1.0)
E = self.cross_eps(X,Y,eps=1.) 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. INPUT: - The arrays X,Y is assumed to be of size (self.V) or (self.V,p) and (self.W) or (self.W,p) respectively where p = dimension of the features - eps=1 : the neighbourhood size considered OUTPUT: - the number of edges of the resulting graph, self.E NB: - It is assumed that the features are embedded in a (locally) Euclidian space - for the sake of speed it is advisable to give a PCA-preprocessed matrices X and Y.
cross_knn(X, Y, k=1)

E = self.cross_knn(X,Y,k) set the graph to be the k-nearest-neighbours graph of from X to Y INPUT:

  • The arrays X,Y is assumed to be of size (self.V) or (self.V,p)

and (self.W) or (self.W,p) respectively where p = dimension of the features - k=1 : is the number of neighbours considered OUTPUT: - the number of edges of the resulting graph, self.E NB: - It is assumed that the features are embedded in a (locally) Euclidian space - for the sake of speed it is advisable to give a PCA-preprocessed matrices X and Y.

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]

Forest

class nipy.neurospin.graph.graph.Forest(V, parents=None)

Bases: nipy.neurospin.graph.graph.WeightedGraph

This is a Forest structure, i.e. a set of trees - the nodes can be segmented into trees - within each tree a node has one parent and children (hierarchical structure) - some of the nodes can be viewed as leaves, other as roots - the edges within a tree are associated with a weight: +1 from child to parent -1 from parent to child

fields: - V : (int,>0) the number of vertices - E : (int) the number of edges - parents: array of shape (self.V) the parent array - edges: array of shape (self.E,2) reprensenting pairwise neighbors - weights, array of shape (self.E), +1/-1 for scending/descending links - children: list of arrays that represents the childs of any node

__init__(V, parents=None)
INPUT: V: the number of edges of the graph parents = None: array of shape (V) the parents of the graph by default, the parents are set to range(V), i.e. each node is its own parent, and each node is a tree
all_distances(seed=None)
returns all the distanceof the graph as a tree dg = self.all_distances(seed=None) by convention infinte distances are given the distance np.infty
check()
Check that the proposed is indeed a graph, i.e. contains no loop NOTE : slow implementation... to be rewritten in C OUTPUT : a boolean b==0 iff there are loops, 1 otherwise
compute_children()
self.compute_children() define the children list OUPUT: - children: a list of self.V lists that yields the children of each node
define_graph_attributes()
define the edge and weights array
depth_from_leaves()
compute a labelling of the nodes which is 0 for the leaves, 1 for their parents etc and maximal for the roots
get_children(v=-1)
returns the list list of children arrays in all the forest if v==-1 or the children of v otherwise
get_descendents(v)
returns the nodes that are children of v
isleaf()
returns a bool array of shape(self.V) so that isleaf==1 iff the node is a leaf in the forest (has no kids)
isroot()
returns a bool array of shape(self.V) so that isleaf==1 iff the node is a root in the forest i.e. : is its own parent
leaves_of_a_subtree(ids, custom=False)
tests whether the given nodes within ids represent all the leaves of a certain subtree of self if custom==true the behavior of the function is somewhat mroe bizare: - the different connected components are considered as being in a same greater tree - when a node has more than two subbbranches, any subset of these children is considered as a subtree
merge_simple_branches()
merge the branches of the forest that are the only child of the parent branch into their child
reorder_from_leaves_to_roots()
reorder the tree so that the leaves come first then their parents and so on, and the roots are last the permutation necessary to apply to all vertex-based information
subforest(valid)
creates a subforest with the vertices for which valid>0 and with the correponding set of edges the children of deleted vertices become their own parent a new forest is created

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

__init__(V, E=0)
adjacency()
cc()
Returns an array of labels corresponding to the different connex components of the graph. output: -label: array of shape(self.V) that labels the vertices
complete()
degrees()
returns the degree of the graph vertices ouput: - 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()
set_edges(edges)
sets self.edges=edges if 1. edges has a correct size 2. edges take values in [1..V]
show(figid=-1)
show the graph as a planar graph INPUT: -figid = -1 the figure id in pylab by default a new figure is created OUTPUT: - figid

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

__init__(V, edges=None, weights=None)
INPUT: V: the number of edges of the graph edges=None: the edge array of the graph weights=None: the asociated weights array This is the build function
Kruskal()
K = self.Kruskal() creates the MST of self using Kruskal’s algo. efficient is self is sparse NOTE: if self contains several connected components, self.Kruskal() will also retain a graph with k connected components
Kruskal_dev()
K = self.Kruskal() creates the MST of self using Kriskal’s algo. efficient is self is sparse NOTE: if self contains several connected components, self.Kruskal() will also retain a graph with k connected components
Voronoi_Labelling(seed)
label = self.Voronoi_Labelling(seed) performs a voronoi labelling of the graph INPUT: - seed is an array of vertices from which the cells are built OUTPUT: - the labelling of the vertices
Voronoi_diagram(seeds, samples)
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. INPUT: - seeds: array of shape (self.V,dim) - samples: array of shape (nsamples,dim) NOTE: - by default, the weights are a Gaussian function of the distance - The implementation is somewhat awkward
WeightedDegree(c)
returns the sum of weighted degree of graph self INPUT: - c (int) if c==0 considering left side if c==1 considering right side of the edges OUTPUT: - wd : array of shape (self.V): the resulting weighted degree NOTE:inefficient code
adjacency()
INPUT: None OUTPUT: -A : an ((self.V*self.V),np.double) array that represents the adjacency matrix of the graph NOTE: Future version should allow sparse matrix coding
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
cliques()
cliques = self.cliques() OUTPUT: a labelling of the vertices according to the clique they belong to the cliques are defined using replicator dynamics equations
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/TODO :slow and memory-consuming version a C implementation is necessary
copy()
G = self.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 OUPUT: the number of edges, self.E
dijkstra(seed=0)
dg = self.dijkstra(seed=0) returns all the [graph] geodesic distances starting from seed it is mandatory that the graph weights are non-negative INPUT: - seed is the edge from which the distances are computed OUTPUT: - the graph distance dg from the seed to any edge
eps(X, eps=1.0)
E = self.eps(X,eps=1.) set the graph to be the eps-nearest-neighbours graph of the data INPUT: - The array X is assumed to be of size (n) or (n,p) where n = number of vertices of the graph and p = dimension of the features - eps=1. : the neighborhood width OUTPUT: - the number of edges of the resulting graph, self.E NB: - It is assumed that the features are embedded in a (locally) Euclidian space - trivial edges (aa) are included - for the sake of speed it is advisable to give a PCA-preprocessed matrix X.
floyd(seed=None)
dg = self.floyd(seed=None): returns all the geodesic distances starting from seeds it is mandatory that the graph weights are non-negative INPUT: - seed is an arry of edges from which the distances are computed if seed==None, then every edge is a seed point OUTPUT: - the graph distance dg from each seed to any edge Note that it has size (nbseed,nbedges) NB: - In fact the algo proceeds byr epeating dijkstra’s algo for each seed. floyd’s algo is not used (O(self.V)^3 complexity...) - by convention, infinte distances are coded with sum(self.wedges)+1
from_3d_grid(xyz, k=18)
E = self.from_3d_grid(xyz,k=18) set the graph to be the topological neighbours graph of the dataset xyz, in the k-connectivity scheme INPUT: - xyz: an array of int with shape (n,3), where n=self.V - k = 18: the number of neighbours considered. (6,18 or 26) OUTPUT: - E: the number of edges of the graph
from_adjacency(A)
sets the edges of self according to the adjacency matrix M INPUT M: array of size(n,n) so that n = self.V
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 INPUT: - The array X is assumed to be of size (n) or (n,p) where n = number of vertices of the graph and p = dimension of the features - k=1 : is the number of neighbours considered OUTPUT: - the number of edges of the resulting graph, self.E NB: - It is assumed that the features are embedded in a (locally) Euclidian space - the knn system is symmeterized: if (ab) is one of the edges then (ba) is also included - trivial edges (aa) are not included - for the sake of speed it is advisable to give a PCA-preprocessed matrix X.
left_incidence()
return 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()
ln = self.list_of_neighbors() returns the set of neighbors as a python list
mst(X)
l = self.mst(X) maskes self the MST of the array X INPUT: - X: an array of shape (n,p) where n=self.V and p is the feature dimension OUTPUT: - the length of the mst NB: - It is assumed that the features are embedded in a (locally) Euclidian space - The edge system is symmeterized: if (ab) is one of the edges then (ba) is another edge - As a consequence, the graph comprises (2*self.V-2) edges - the algorithm uses Boruvska’s method
normalize(c=0)
self.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 INPUT: - c=0 is an index that designates the array according to which D is normalized It is an optional argument, by default c = 0 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 NB: Note that when sum(edge[e,.]=a) D[e]=0, nothing is performed
remove_edges(valid) Removes all the edges for which valid==0 INPUT: - valid, an array of shape (self.E)
remove_trivial_edges()
self.remove_trivial_edges() Removes trivial edges, i.e. edges that are (vv)-like self.weights and self.E are corrected accordingly OUTPUT: The number of edges
reorder(c=0)
self.reorder(c=0) Reorder the graph according to the index c INPUT: - c=0 is an 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()
return 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_euclidian(X) Compute the weights of the graph in an Euclidian space INPUT: X is the coordinate matrix of the vertices it is assumed to be of size (self.V, p)
set_gaussian(X, sigma = 0) Compute the weights of the graph as a gaussian function of their length INPUT: - X is the coordinate matrix of the vertices it is assumed to be of size (self.V, p) - sigma = 0 : the parameter of the gaussian function NB = when sigma = 0, an empirical value is used : sigma = sqrt(mean(||X[, self.edges[, :, 0], :], -X[, self.edges[, :, 1], :], ||^2))
set_weights(weights)
INPUT: -weights : an array of size self.V which yields edges weights
show(X=None, figid=-1)
a = self.show(X=None) plots the current graph in 2D INPUT: - X=None, a set of coordinates that can be used to embed the vertices in 2D. to be useful X, should have shape((self.V,p)) if p>2, a svd reduces X for display if p=3 the figure si 3d By default, the graph is presented on a circle - figid=-1: a figure id for pylab plotting by default, a new figure is created OUTPUT: a = figure handle NB: This should be used only for small graphs...
skeleton()
G = self.skeleton() returns a MST that based on self.weights Caveat: self must be connected
subgraph(valid)
creates a subgraph with the vertices for which valid>0 and with the correponding set of edges INPUT: - valid of shape (self.V): nonzero for vertices to be retained CAVEAT: - the vertices are renumbered as [1..p] where p = sum(valid>0) - when sum(valid==0) then None is returned
symmeterize()
self.symmeterize() symmeterize the graphself , ie produces the graph whose adjacency matrix would be the symmetric part of its current adjacency matrix
WeightedGraph.to_neighb() converts the graph to a neighboring system The neighboring system is nothing but a (sparser) representation of the edge matrix OUTPUT: The arrays ci, ne ,we 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)
G = concatenate(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 isjoint sets INPUT: - G1,K2: the two graphs to be concatenated OUPUT - G NOTE: this implies that the vertices of G corresponding to G2 are labeled [G1.V .. G1.V+G2.V]