Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
is_chordal¶
- is_chordal(G)[source]¶
Checks whether G is a chordal graph.
A graph is chordal if every cycle of length at least 4 has a chord (an edge joining two nodes not adjacent in the cycle).
Parameters : G : graph
A NetworkX graph.
Returns : chordal : bool
True if G is a chordal graph and False otherwise.
Raises : NetworkXError
The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. If the input graph is an instance of one of these classes, a NetworkXError is raised.
Notes
The routine tries to go through every node following maximum cardinality search. It returns False when it finds that the separator for any node is not a clique. Based on the algorithms in [R194].
References
[R194] (1, 2) R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579. Examples
>>> import networkx as nx >>> e=[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)] >>> G=nx.Graph(e) >>> nx.is_chordal(G) True