Inheritance diagram for nipy.algorithms.graph.forest:
Module implements the Forest class
A Forest is a graph with a hierarchical structure. Each connected component of a forest is a tree. The main characteristic is that each node has a single parent, so that a Forest is fully characterized by a “parent” array, that defines the unique parent of each node. The directed relationships are encoded by the weight sign.
Note that some methods of WeightedGraph class (e.g. dijkstra’s algorithm) require positive weights, so that they cannot work on forests in the current implementation. Specific methods (e.g. all_sidtance()) have been set instead.
Main author: Bertrand thirion, 2007-2011
Bases: nipy.algorithms.graph.graph.WeightedGraph
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 that describe the associated hierarchical structure. Some of the nodes can be viewed as leaves, other as roots The edges within a tree are associated with a weight:
Attributes
V | int | int > 0, the number of vertices |
E | int | the number of edges |
parents | (self.V,) array | the parent array |
edges | (self.E, 2) array | representing pairwise neighbors |
weights | (self.E,) array | +1/-1 for ascending/descending links |
children: list | list of arrays that represents the children any node |
Constructor
Parameters: | V : int
parents : None or (V,) array
|
---|
returns the adjacency matrix of the graph as a sparse coo matrix
Returns: | adj: scipy.sparse matrix instance, :
|
---|
returns all the distances of the graph as a tree
Parameters: | seed=None array of shape(nbseed) with valuesin [0..self.V-1] :
|
---|---|
Returns: | dg: array of shape(nseed, self.V), the resulting distances : |
Notes
By convention infinite distances are given the distance np.inf
anti-symmeterize self, i.e. produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix
Compte the different connected components of the graph.
Returns: | label: array of shape(self.V), labelling of the vertices : |
---|
Check that self is indeed a forest, i.e. contains no loop
Returns: | a boolean b=0 iff there are loops, 1 otherwise : |
---|
Notes
Slow implementation, might be rewritten in C or cython
Extraction of the graphe cliques these are defined using replicator dynamics equations
Returns: | cliques: array of shape (self.V), type (np.int) :
|
---|
returns a compact representation of self
Returns: | idx: array of of shape(self.V + 1): :
neighb: array of shape(self.E), concatenated list of neighbors : weights: array of shape(self.E), concatenated list of weights : |
---|
Define the children of each node (stored in self.children)
returns a copy of self
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 : |
---|
define the edge and weights array
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 : |
---|
compute an index for each node: 0 for the leaves, 1 for their parents etc. and maximal for the roots.
Returns: | depth: array of shape (self.V): the depth values of the vertices : |
---|
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), :
|
---|
Notes
It is mandatory that the graph weights are non-negative
Compute all the geodesic distances starting from seeds
Parameters: | seed= None: array of shape (nbseed), type np.int :
|
---|---|
Returns: | dg array of shape (nbseed, self.V) :
|
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...)
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 : |
To get the number of edges in the graph
To get the number of vertices in the graph
Get the children of a node/each node
Parameters: | v: int, optional :
|
---|---|
Returns: | children: list of int the list of children of node v (if v is provided) :
|
returns the nodes that are children of v as a list
Parameters: | v: int, a node index : |
---|---|
Returns: | desc: list of int, the list of all descendant of the input node : |
To get the graph’s edges
To get the graph’s vertices (as id)
States whether self is connected or not
Identification of the leaves of the forest
Returns: | leaves: bool array of shape(self.V), indicator of the forest’s leaves : |
---|
Returns an indicator of nodes being roots
Returns: | roots, array of shape(self.V, bool), indicator of the forest’s roots : |
---|
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
tests whether the given nodes are the leaves of a certain subtree
Parameters: | ids: array of shape (n) that takes values in [0..self.V-1] : custom == False, boolean :
|
---|
Return left incidence matrix
Returns: | left_incid: list :
|
---|
returns the set of neighbors of self as a list of arrays
Returns the indexes of the vertices within the main cc
Returns: | idx: array of shape (sizeof main cc) : |
---|
Return a subforest, where chained branches are collapsed
Returns: | sf, Forest instance, same as self, without any chain : |
---|
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 :
|
---|
Notes
Note that when sum_{edge[e, .] == a } D[e] = 0, nothing is performed
Propagation of a certain labelling from leves to roots Assuming that label is a certain positive integer field this propagates these labels to the parents whenever the children nodes have coherent properties otherwise the parent value is unchanged
Parameters: | label: array of shape(self.V) : |
---|---|
Returns: | label: array of shape(self.V) : |
propagates from leaves to roots some binary property of the nodes so that prop[parents] = logical_and(prop[children])
Parameters: | prop, array of shape(self.V), the input property : |
---|---|
Returns: | prop, array of shape(self.V), the output property field : |
Removes all the edges for which valid==0
Parameters: | valid : (self.E,) array |
---|
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 the tree so that the leaves come first then their parents and so on, and the roots are last.
Returns: | order: array of shape(self.V) :
|
---|
Return right incidence matrix
Returns: | right_incid: list :
|
---|
Sets the graph’s edges
Preconditions:
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), :
|
---|
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) :
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 edge weights
Parameters: | weights: array :
|
---|
Plots the current graph in 2D
Parameters: | X : None or array of shape (self.V, 2)
ax: None or int, optional :
|
---|---|
Returns: | ax: axis handle : |
Notes
This should be used only for small graphs.
Creates a subforest with the vertices for which valid > 0
Parameters: | valid: array of shape (self.V): idicator of the selected nodes : |
---|---|
Returns: | subforest: a new forest instance, with a reduced set of nodes : |
Notes
The children of deleted vertices become their own parent
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 self, modify edges and weights so that self.adjacency becomes the symmetric part of the current self.adjacency.
Return adjacency matrix as coo sparse
Returns: | sp: scipy.sparse matrix instance :
|
---|
Returns the number of hierarchical levels in the tree
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
Performs a voronoi labelling of the graph
Parameters: | seed: array of shape (nseeds), type (np.int), :
|
---|---|
Returns: | labels: array of shape (self.V) the labelling of the vertices : |