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, 20072011
Forest
¶

class
nipy.algorithms.graph.forest.
Forest
(V, parents=None)¶ 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:
 +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)¶ 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

all_distances
(seed=None)¶ returns all the distances of the graph as a tree
Parameters: seed=None array of shape(nbseed) with valuesin [0..self.V1]
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

check
()¶ 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

compute_children
()¶ Define the children of each node (stored in self.children)

define_graph_attributes
()¶ define the edge and weights array

depth_from_leaves
()¶ 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

get_children
(v=1)¶ 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)¶ 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

isleaf
()¶ Identification of the leaves of the forest
Returns: leaves: bool array of shape(self.V), indicator of the forest’s leaves

isroot
()¶ Returns an indicator of nodes being roots
Returns: roots, array of shape(self.V, bool), indicator of the forest’s roots

leaves_of_a_subtree
(ids, custom=False)¶ tests whether the given nodes are the leaves of a certain subtree
Parameters: ids: array of shape (n) that takes values in [0..self.V1]
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

merge_simple_branches
()¶ Return a subforest, where chained branches are collapsed
Returns: sf, Forest instance, same as self, without any chain

propagate_upward
(label)¶ 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)

propagate_upward_and
(prop)¶ 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

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.
Returns: order: array of shape(self.V)
the order of the old vertices in the reordered graph

subforest
(valid)¶ 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

tree_depth
()¶ Returns the number of hierarchical levels in the tree