CODEWITHSUNDEEP
pythongraphtreenetworkx
papafe
papafe

Reputation: 3070

Check if an undirected graph is a tree in networkx

I would like to know if there is a simple way to check whether a certain undirected graph in networkx is a tree or not

Upvotes: 5

Views: 2994

Answers (2)

Edward
Edward

Reputation: 574

There are built-in functions in networkx to check the type of a given graph.

To check if it's a tree, run networkx.is_tree(g). See algorithms for trees in networkx documentation.

Upvotes: 7

Aric
Aric

Reputation: 25289

The fastest way for a graph G(V,E) might be to check if |V| = |E| + 1 and that G is connected:

import networkx as nx
def is_tree(G):
    if nx.number_of_nodes(G) != nx.number_of_edges(G) + 1:
        return False
    return nx.is_connected(G)

if __name__ == '__main__':

    print(is_tree(nx.path_graph(5)))
    print(is_tree(nx.star_graph(5)))
    print(is_tree(nx.house_graph()))

Upvotes: 10

Related Questions