NetworkX

Source code for networkx.algorithms.chordal.chordal_alg

# -*- coding: utf-8 -*-
"""
Algorithms for chordal graphs.

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).
http://en.wikipedia.org/wiki/Chordal_graph
"""
import networkx as nx
import random
import sys

__authors__ = "\n".join(['Jesus Cerquides <cerquide@iiia.csic.es>'])
#    Copyright (C) 2010 by 
#    Jesus Cerquides <cerquide@iiia.csic.es>
#    All rights reserved.
#    BSD license.

__all__ = ['is_chordal',
           'find_induced_nodes', 
           'chordal_graph_cliques',
           'chordal_graph_treewidth',
           'NetworkXTreewidthBoundExceeded']

class NetworkXTreewidthBoundExceeded(nx.NetworkXException):
    """Exception raised when a treewidth bound has been provided and it has 
    been exceeded"""
    

[docs]def is_chordal(G): """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. 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 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 [1]_. References ---------- .. [1] 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. """ if G.is_directed(): raise nx.NetworkXError('Directed graphs not supported') if G.is_multigraph(): raise nx.NetworkXError('Multiply connected graphs not supported.') if len(_find_chordality_breaker(G))==0: return True else: return False
[docs]def find_induced_nodes(G,s,t,treewidth_bound=sys.maxsize): """Returns the set of induced nodes in the path from s to t. Parameters ---------- G : graph A chordal NetworkX graph s : node Source node to look for induced nodes t : node Destination node to look for induced nodes treewith_bound: float Maximum treewidth acceptable for the graph H. The search for induced nodes will end as soon as the treewidth_bound is exceeded. Returns ------- I : Set of nodes The set of induced nodes in the path from s to t in G 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. The algorithm can only be applied to chordal graphs. If the input graph is found to be non-chordal, a NetworkXError is raised. Examples -------- >>> import networkx as nx >>> G=nx.Graph() >>> G = nx.generators.classic.path_graph(10) >>> I = nx.find_induced_nodes(G,1,9,2) >>> list(I) [1, 2, 3, 4, 5, 6, 7, 8, 9] Notes ----- G must be a chordal graph and (s,t) an edge that is not in G. If a treewidth_bound is provided, the search for induced nodes will end as soon as the treewidth_bound is exceeded. The algorithm is inspired by Algorithm 4 in [1]_. A formal definition of induced node can also be found on that reference. References ---------- .. [1] Learning Bounded Treewidth Bayesian Networks. Gal Elidan, Stephen Gould; JMLR, 9(Dec):2699--2731, 2008. http://jmlr.csail.mit.edu/papers/volume9/elidan08a/elidan08a.pdf """ if not is_chordal(G): raise nx.NetworkXError("Input graph is not chordal.") H = nx.Graph(G) H.add_edge(s,t) I = set() triplet = _find_chordality_breaker(H,s,treewidth_bound) while triplet: (u,v,w) = triplet I.update(triplet) for n in triplet: if n!=s: H.add_edge(s,n) triplet = _find_chordality_breaker(H,s,treewidth_bound) if I: # Add t and the second node in the induced path from s to t. I.add(t) for u in G[s]: if len(I & set(G[u]))==2: I.add(u) break return I
[docs]def chordal_graph_cliques(G): """Returns the set of maximal cliques of a chordal graph. The algorithm breaks the graph in connected components and performs a maximum cardinality search in each component to get the cliques. Parameters ---------- G : graph A NetworkX graph Returns ------- cliques : A set containing the maximal cliques in G. 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. The algorithm can only be applied to chordal graphs. If the input graph is found to be non-chordal, a NetworkXError is raised. 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),(7,8)] >>> G = nx.Graph(e) >>> G.add_node(9) >>> setlist = nx.chordal_graph_cliques(G) """ if not is_chordal(G): raise nx.NetworkXError("Input graph is not chordal.") cliques = set() for C in nx.connected.connected_component_subgraphs(G): cliques |= _connected_chordal_graph_cliques(C) return cliques
[docs]def chordal_graph_treewidth(G): """Returns the treewidth of the chordal graph G. Parameters ---------- G : graph A NetworkX graph Returns ------- treewidth : int The size of the largest clique in the graph minus one. 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. The algorithm can only be applied to chordal graphs. If the input graph is found to be non-chordal, a NetworkXError is raised. 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),(7,8)] >>> G = nx.Graph(e) >>> G.add_node(9) >>> nx.chordal_graph_treewidth(G) 3 References ---------- .. [1] http://en.wikipedia.org/wiki/Tree_decomposition#Treewidth """ if not is_chordal(G): raise nx.NetworkXError("Input graph is not chordal.") max_clique = -1 for clique in nx.chordal_graph_cliques(G): max_clique = max(max_clique,len(clique)) return max_clique - 1
def _is_complete_graph(G): """Returns True if G is a complete graph.""" if G.number_of_selfloops()>0: raise nx.NetworkXError("Self loop found in _is_complete_graph()") n = G.number_of_nodes() if n < 2: return True e = G.number_of_edges() max_edges = ((n * (n-1))/2) return e == max_edges def _find_missing_edge(G): """ Given a non-complete graph G, returns a missing edge.""" nodes=set(G) for u in G: missing=nodes-set(list(G[u].keys())+[u]) if missing: return (u,missing.pop()) def _max_cardinality_node(G,choices,wanna_connect): """Returns a the node in choices that has more connections in G to nodes in wanna_connect. """ # max_number = None max_number = -1 for x in choices: number=len([y for y in G[x] if y in wanna_connect]) if number > max_number: max_number = number max_cardinality_node = x return max_cardinality_node def _find_chordality_breaker(G,s=None,treewidth_bound=sys.maxsize): """ Given a graph G, starts a max cardinality search (starting from s if s is given and from a random node otherwise) trying to find a non-chordal cycle. If it does find one, it returns (u,v,w) where u,v,w are the three nodes that together with s are involved in the cycle. """ unnumbered = set(G) if s is None: s = random.choice(list(unnumbered)) unnumbered.remove(s) numbered = set([s]) # current_treewidth = None current_treewidth = -1 while unnumbered:# and current_treewidth <= treewidth_bound: v = _max_cardinality_node(G,unnumbered,numbered) unnumbered.remove(v) numbered.add(v) clique_wanna_be = set(G[v]) & numbered sg = G.subgraph(clique_wanna_be) if _is_complete_graph(sg): # The graph seems to be chordal by now. We update the treewidth current_treewidth = max(current_treewidth,len(clique_wanna_be)) if current_treewidth > treewidth_bound: raise nx.NetworkXTreewidthBoundExceeded(\ "treewidth_bound exceeded: %s"%current_treewidth) else: # sg is not a clique, # look for an edge that is not included in sg (u,w) = _find_missing_edge(sg) return (u,v,w) return () def _connected_chordal_graph_cliques(G): """Return the set of maximal cliques of a connected chordal graph.""" if G.number_of_nodes() == 1: x = frozenset(G.nodes()) return set([x]) else: cliques = set() unnumbered = set(G.nodes()) v = random.choice(list(unnumbered)) unnumbered.remove(v) numbered = set([v]) clique_wanna_be = set([v]) while unnumbered: v = _max_cardinality_node(G,unnumbered,numbered) unnumbered.remove(v) numbered.add(v) new_clique_wanna_be = set(G.neighbors(v)) & numbered sg = G.subgraph(clique_wanna_be) if _is_complete_graph(sg): new_clique_wanna_be.add(v) if not new_clique_wanna_be >= clique_wanna_be: cliques.add(frozenset(clique_wanna_be)) clique_wanna_be = new_clique_wanna_be else: raise nx.NetworkXError("Input graph is not chordal.") cliques.add(frozenset(clique_wanna_be)) return cliques