| # -*- 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""" |
| |
| |
| 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 |
| |
| 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 |
| |
| 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 |
| |
| |
| 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 |
| |
| |
| |
| |
