Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tree / recognition.py @ 5cef0f13

 1 ```#-*- coding: utf-8 -*- ``` ```""" ``` ```Recognition Tests ``` ```================= ``` ``` ``` ```A *forest* is an acyclic, undirected graph, and a *tree* is a connected forest. ``` ```Depending on the subfield, there are various conventions for generalizing these ``` ```definitions to directed graphs. ``` ``` ``` ```In one convention, directed variants of forest and tree are defined in an ``` ```identical manner, except that the direction of the edges is ignored. In effect, ``` ```each directed edge is treated as a single undirected edge. Then, additional ``` ```restrictions are imposed to define *branchings* and *arborescences*. ``` ``` ``` ```In another convention, directed variants of forest and tree correspond to ``` ```the previous convention's branchings and arborescences, respectively. Then two ``` ```new terms, *polyforest* and *polytree*, are defined to correspond to the other ``` ```convention's forest and tree. ``` ``` ``` ```Summarizing:: ``` ``` ``` ``` +-----------------------------+ ``` ``` | Convention A | Convention B | ``` ``` +=============================+ ``` ``` | forest | polyforest | ``` ``` | tree | polytree | ``` ``` | branching | forest | ``` ``` | arborescence | tree | ``` ``` +-----------------------------+ ``` ``` ``` ```Each convention has its reasons. The first convention emphasizes definitional ``` ```similarity in that directed forests and trees are only concerned with ``` ```acyclicity and do not have an in-degree constraint, just as their undirected ``` ```counterparts do not. The second convention emphasizes functional similarity ``` ```in the sense that the directed analog of a spanning tree is a spanning ``` ```arborescence. That is, take any spanning tree and choose one node as the root. ``` ```Then every edge is assigned a direction such there is a directed path from the ``` ```root to every other node. The result is a spanning arborescence. ``` ``` ``` ```NetworkX follows convention "A". Explicitly, these are: ``` ``` ``` ```undirected forest ``` ``` An undirected graph with no undirected cycles. ``` ``` ``` ```undirected tree ``` ``` A connected, undirected forest. ``` ``` ``` ```directed forest ``` ``` A directed graph with no undirected cycles. Equivalently, the underlying ``` ``` graph structure (which ignores edge orientations) is an undirected forest. ``` ``` In convention B, this is known as a polyforest. ``` ``` ``` ```directed tree ``` ``` A weakly connected, directed forest. Equivalently, the underlying graph ``` ``` structure (which ignores edge orientations) is an undirected tree. In ``` ``` convention B, this is known as a polytree. ``` ``` ``` ```branching ``` ``` A directed forest with each node having, at most, one parent. So the maximum ``` ``` in-degree is equal to 1. In convention B, this is known as a forest. ``` ``` ``` ```arborescence ``` ``` A directed tree with each node having, at most, one parent. So the maximum ``` ``` in-degree is equal to 1. In convention B, this is known as a tree. ``` ``` ``` ```For trees and arborescences, the adjective "spanning" may be added to designate ``` ```that the graph, when considered as a forest/branching, consists of a single ``` ```tree/arborescence that includes all nodes in the graph. It is true, by ``` ```definition, that every tree/arborescence is spanning with respect to the nodes ``` ```that define the tree/arborescence and so, it might seem redundant to introduce ``` ```the notion of "spanning". However, the nodes may represent a subset of ``` ```nodes from a larger graph, and it is in this context that the term "spanning" ``` ```becomes a useful notion. ``` ``` ``` ```""" ``` ```import networkx as nx ``` ```__author__ = """\n""".join([ ``` ``` 'Ferdinando Papale ', ``` ``` 'chebee7i ', ``` ```]) ``` ```__all__ = ['is_arborescence', 'is_branching', 'is_forest', 'is_tree'] ``` ```@nx.utils.not_implemented_for('undirected') ``` ```def is_arborescence(G): ``` ``` """ ``` ``` Returns True if `G` is an arborescence. ``` ``` ``` ``` An arborescence is a directed tree with maximum in-degree equal to 1. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` The graph to test. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` b : bool ``` ``` A boolean that is True if `G` is an arborescence. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` In another convention, an arborescence is known as a *tree*. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` is_tree ``` ``` ``` ``` """ ``` ``` return is_tree(G) and max(d for n, d in G.in_degree()) <= 1 ``` ```@nx.utils.not_implemented_for('undirected') ``` ```def is_branching(G): ``` ``` """ ``` ``` Returns True if `G` is a branching. ``` ``` ``` ``` A branching is a directed forest with maximum in-degree equal to 1. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : directed graph ``` ``` The directed graph to test. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` b : bool ``` ``` A boolean that is True if `G` is a branching. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` In another convention, a branching is also known as a *forest*. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` is_forest ``` ``` ``` ``` """ ``` ``` return is_forest(G) and max(d for n, d in G.in_degree()) <= 1 ``` ```def is_forest(G): ``` ``` """ ``` ``` Returns True if `G` is a forest. ``` ``` ``` ``` A forest is a graph with no undirected cycles. ``` ``` ``` ``` For directed graphs, `G` is a forest if the underlying graph is a forest. ``` ``` The underlying graph is obtained by treating each directed edge as a single ``` ``` undirected edge in a multigraph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` The graph to test. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` b : bool ``` ``` A boolean that is True if `G` is a forest. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` In another convention, a directed forest is known as a *polyforest* and ``` ``` then *forest* corresponds to a *branching*. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` is_branching ``` ``` ``` ``` """ ``` ``` if len(G) == 0: ``` ``` raise nx.exception.NetworkXPointlessConcept('G has no nodes.') ``` ``` if G.is_directed(): ``` ``` components = nx.weakly_connected_component_subgraphs ``` ``` else: ``` ``` components = nx.connected_component_subgraphs ``` ``` return all(len(c) - 1 == c.number_of_edges() for c in components(G)) ``` ```def is_tree(G): ``` ``` """ ``` ``` Returns True if `G` is a tree. ``` ``` ``` ``` A tree is a connected graph with no undirected cycles. ``` ``` ``` ``` For directed graphs, `G` is a tree if the underlying graph is a tree. The ``` ``` underlying graph is obtained by treating each directed edge as a single ``` ``` undirected edge in a multigraph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` The graph to test. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` b : bool ``` ``` A boolean that is True if `G` is a tree. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` In another convention, a directed tree is known as a *polytree* and then ``` ``` *tree* corresponds to an *arborescence*. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` is_arborescence ``` ``` ``` ``` """ ``` ``` if len(G) == 0: ``` ``` raise nx.exception.NetworkXPointlessConcept('G has no nodes.') ``` ``` if G.is_directed(): ``` ``` is_connected = nx.is_weakly_connected ``` ``` else: ``` ``` is_connected = nx.is_connected ``` ``` # A connected graph with no cycles has n-1 edges. ``` ``` return len(G) - 1 == G.number_of_edges() and is_connected(G) ```