algorithms.graph.forest¶
Module: algorithms.graph.forest¶
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
Forest¶
-
class
nipy.algorithms.graph.forest.Forest(V, parents=None)[source]¶ Bases:
nipy.algorithms.graph.graph.WeightedGraphForest 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:
+1 from child to parent
-1 from parent to child
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
-
__init__(V, parents=None)[source]¶ Constructor
- Parameters
V : int
the number of edges of the graph
parents : None or (V,) array
the parents of zach vertex. If `parents`==None , the parents are set to range(V), i.e. each node is its own parent, and each node is a tree
-
get_children(v=-1)[source]¶ Get the children of a node/each node
- Parameters
v: int, optional
a node index
- Returns
children: list of int the list of children of node v (if v is provided)
a list of lists of int, the children of all nodes otherwise
-
get_descendants(v, exclude_self=False)[source]¶ 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
-
check()[source]¶ 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
-
isleaf()[source]¶ Identification of the leaves of the forest
- Returns
leaves: bool array of shape(self.V), indicator of the forest’s leaves
-
isroot()[source]¶ Returns an indicator of nodes being roots
- Returns
roots, array of shape(self.V, bool), indicator of the forest’s roots
-
subforest(valid)[source]¶ 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
-
merge_simple_branches()[source]¶ Return a subforest, where chained branches are collapsed
- Returns
sf, Forest instance, same as self, without any chain
-
all_distances(seed=None)[source]¶ returns all the distances of the graph as a tree
- Parameters
seed=None array of shape(nbseed) with valuesin [0..self.V-1]
set of vertices from which tehe distances are computed
- Returns
dg: array of shape(nseed, self.V), the resulting distances
Notes
By convention infinite distances are given the distance np.inf
-
depth_from_leaves()[source]¶ 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
-
reorder_from_leaves_to_roots()[source]¶ 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)
the order of the old vertices in the reordered graph
-
leaves_of_a_subtree(ids, custom=False)[source]¶ 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
if custom==true the behavior of the function is more specific - the different connected components are considered as being in a same greater tree - when a node has more than two subbranches, any subset of these children is considered as a subtree
-
propagate_upward_and(prop)[source]¶ 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
-
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
Notes
It is mandatory that the graph weights are non-negative
-
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
-
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
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
-
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
-
propagate_upward(label)[source]¶ 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)
-
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
Preconditions:
edges has a correct size
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 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.
-
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.
-
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