Is there a class in networkx 1.8 which encapsulates tree assertions in node add/remove operations

Question

I searched now for an hour for an answer to this trivial question (trivial for those who know) in an actually well written documentation (citations of papers, not one bit undocumented). Let me show you what I found so far:

• networkx.generators.directed package where gn_graph is "always a (directed) tree" but doesn't certainly encapsulate the assertions
• networkx.balanced_tree obviously produces a tree, but not an arbitrary, but a balanced
• graph.Graph.Tree(http://networkx.lanl.gov/archive/networkx-0.37/networkx.tree.Tree-class.html) seems perfect, but is from version 0.37 which is not 1.8
• endless number of generatores and iteratores providing - well - generators and iteraors, but none of them has a documented encapuslation of tree assertions in operations

With encapsulation in operations I'm referring to checks of the tree assertions (directed acyclic graph) when adding or removing edges, e.g.

tree = networkx.tree.Tree()
tree.add_edge(a,b) # ok
tree.add_edge(b,c) # ok
tree.add_edge(b,a) # should raise TreeException("This is a tree, i****")

Answer 1

Here is a modified version of the 'Tree' class (from networkx-0.37, now deprecated) that works with modern versions of networkx. Lightly tested with networkx-1.9 but no guarantees any of this works correctly; expect bugs. Downloadable version at https://gist.github.com/hagberg/c855589980d644254f6d

from networkx import Graph
from networkx.exception import NetworkXException, NetworkXError
import networkx.convert as convert

class Tree(Graph):
    """ A free (unrooted) tree."""
    def __init__(self, data=None, **attr):
        Graph.__init__(self, **attr)
        if data is not None:
            convert.to_networkx_graph(data, create_using=self)
            # check if it is a tree.
            if not (G.order() == G.size() + 1 and
                    nx.number_connected_components(G) == 1):
                raise NetworkXError("Data %s is not a tree" % data)
        # load graph attributes (must be after convert)
        self.graph.update(attr)
        self.edge = self.adj

    def add_node(self, n):
        if n in self:
            return  # already in tree
        elif len(self.adj) == 0:
            Graph.add_node(self, n)  # first node
        else:  # not allowed
            raise NetworkXError(
                "adding single node %s not allowed in non-empty tree" % (n))

    def add_nodes_from(self, nbunch):
        for n in nbunch:
            self.add_node(n)

    def remove_node(self, n):
        try:
            if len(self.adj[n]) == 1:  # allowed for leaf node
                Graph.remove_node(self, n)
            else:
                raise NetworkXError(
                    "deleting interior node %s not allowed in tree" % (n))
        except KeyError:  # NetworkXError if n not in self
            raise NetworkXError("node %s not in graph" % n)

    def remove_nodes_from(self, nbunch):
        for n in nbunch:
            self.remove_node(n)

    def add_edge(self, u, v=None):
        if v is None:
            (u, v) = u  # no v given, assume u is an edge tuple
        if self.has_edge(u, v):
            return  # no parallel edges allowed
        elif u in self and v in self:
            raise NetworkXError(
                "adding edge %s-%s not allowed in tree" % (u, v))
        elif u in self or v in self:
            Graph.add_edge(self, u, v)
            return
        elif len(self.adj) == 0:  # first leaf
            Graph.add_edge(self, u, v)
            return
        else:
            raise NetworkXError(
                "adding edge %s-%s not allowed in tree" % (u, v))

    def add_edges_from(self, ebunch):
        for e in ebunch:
            self.add_edge(e)

    def remove_edge(self, u, v=None):
        if v is None:
            (u, v) = u
        if self.degree(u) == 1 or self.degree(v) == 1:  # leaf edge
            Graph.remove_edge(self, u, v)
        else:  # interior edge
            raise NetworkXError(
                "deleting interior edge %s-%s not allowed in tree" % (u, v))
        if self.degree(u) == 0:  # OK to remove remaining isolated node
            Graph.remove_node(self, u)
        if self.degree(v) == 0:  # OK to remove remaining isolated node
            Graph.remove_node(self, v)

    def remove_edges_from(self, ebunch):
        for e in ebunch:
            self.remove_edge(e)

    # leaf notation
    def add_leaf(self, u, v=None):
        self.add_edge(u, v)

    def remove_leaf(self, u, v=None):
        self.remove_edge(u, v)

    def add_leaves_from(self, ebunch):
        for e in ebunch:
            self.add_leaf(e)

    def remove_leaves_from(self, ebunch):
        for e in ebunch:
            self.remove_leaf(e)