NIPY logo

Site Navigation

NIPY Community

Table Of Contents

This Page

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)

Bases: object

Basic topological (non-weighted) directed Graph class

Methods

adjacency
cc
degrees
get_E
get_V
get_edges
get_vertices
main_cc
set_edges
show
to_coo_matrix
__init__(V, E=0, edges=None)

Constructor

Parameters :

- V (int): the number of vertices :

- E (int): the number of edges :

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

show(ax=None)

Shows the graph as a planar one.

Parameters :ax, axis handle :
Returns :ax, axis handle :
to_coo_matrix()
Returns :

sp: scipy.sparse matrix instance, :

that encodes the adjacency matrix of self

WeightedGraph

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

Bases: nipy.algorithms.graph.graph.Graph

Basic weighted, directed graph class

Methods

adjacency
anti_symmeterize
cc
cliques
compact_neighb
copy Generic (shallow and deep) copying operations.
cut_redundancies
degrees
dijkstra
floyd
from_3d_grid
get_E
get_V
get_edges
get_vertices
get_weights
is_connected
kruskal
left_incidence
list_of_neighbors
main_cc
normalize
remove_edges
remove_trivial_edges
right_incidence
set_edges
set_euclidian
set_gaussian
set_weights
show
subgraph
symmeterize
to_coo_matrix
voronoi_diagram
voronoi_labelling
__init__(V, edges=None, weights=None)

Constructor

Parameters :

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

- edges (array, type=int, shape=(E,2)): edges of the graph :

- weights (array, type=int, shape=(E,)): weights/lenghts of the edges :

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

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 :

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.

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 :

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

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

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 :

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. efficient is self is sparse

Returns :K, WeightedGraph instance: the resulting MST :
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) :
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 :
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 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_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 :

set_weights(weights)
Parameters :weights, array of shape(self.V): edges weights :
show(X=None, ax=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 :

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 self , modify edges and weights so that self.adjacency becomes the symmetric part of the current self.adjacency

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

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 :

Functions

nipy.algorithms.graph.graph.complete_graph(n)

returns a complete graph with n vertices

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

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 :
nipy.algorithms.graph.graph.eps_nn(X, eps=1.0)

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)

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)

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 :

nipy.algorithms.graph.graph.lil_cc(lil)

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 :
nipy.algorithms.graph.graph.mst(X)

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)

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 :

nipy.algorithms.graph.graph.wgraph_from_adjacency(x)

Instantiates a weighted graph from a square 2D array

Parameters :x: 2D array instance, the input array :
Returns :wg: WeightedGraph instance :
nipy.algorithms.graph.graph.wgraph_from_coo_matrix(x)

Instantiates a weighted graph from a (sparse) coo_matrix

Parameters :x: scipy.sparse.coo_matrix instance, the input matrix :
Returns :wg: WeightedGraph instance :