Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / chordal.py @ 5cef0f13

History | View | Annotate | Download (10.5 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Algorithms for chordal graphs.
4

5
A graph is chordal if every cycle of length at least 4 has a chord
6
(an edge joining two nodes not adjacent in the cycle).
7
https://en.wikipedia.org/wiki/Chordal_graph
8
"""
9
import sys
10
import networkx as nx
11
from networkx.utils import arbitrary_element
12

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

    
19
__all__ = ['is_chordal',
20
           'find_induced_nodes',
21
           'chordal_graph_cliques',
22
           'chordal_graph_treewidth',
23
           'NetworkXTreewidthBoundExceeded']
24

    
25

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

    
30

    
31
def is_chordal(G):
32
    """Checks whether G is a chordal graph.
33

34
    A graph is chordal if every cycle of length at least 4 has a chord
35
    (an edge joining two nodes not adjacent in the cycle).
36

37
    Parameters
38
    ----------
39
    G : graph
40
      A NetworkX graph.
41

42
    Returns
43
    -------
44
    chordal : bool
45
      True if G is a chordal graph and False otherwise.
46

47
    Raises
48
    ------
49
    NetworkXError
50
        The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
51
        If the input graph is an instance of one of these classes, a
52
        :exc:`NetworkXError` is raised.
53

54
    Examples
55
    --------
56
    >>> import networkx as nx
57
    >>> e=[(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)]
58
    >>> G=nx.Graph(e)
59
    >>> nx.is_chordal(G)
60
    True
61

62
    Notes
63
    -----
64
    The routine tries to go through every node following maximum cardinality
65
    search. It returns False when it finds that the separator for any node
66
    is not a clique.  Based on the algorithms in [1]_.
67

68
    References
69
    ----------
70
    .. [1] R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms
71
       to test chordality of graphs, test acyclicity of hypergraphs, and
72
       selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984),
73
       pp. 566–579.
74
    """
75
    if G.is_directed():
76
        raise nx.NetworkXError('Directed graphs not supported')
77
    if G.is_multigraph():
78
        raise nx.NetworkXError('Multiply connected graphs not supported.')
79
    if len(_find_chordality_breaker(G)) == 0:
80
        return True
81
    else:
82
        return False
83

    
84

    
85
def find_induced_nodes(G, s, t, treewidth_bound=sys.maxsize):
86
    """Returns the set of induced nodes in the path from s to t.
87

88
    Parameters
89
    ----------
90
    G : graph
91
      A chordal NetworkX graph
92
    s : node
93
        Source node to look for induced nodes
94
    t : node
95
        Destination node to look for induced nodes
96
    treewith_bound: float
97
        Maximum treewidth acceptable for the graph H. The search
98
        for induced nodes will end as soon as the treewidth_bound is exceeded.
99

100
    Returns
101
    -------
102
    I : Set of nodes
103
        The set of induced nodes in the path from s to t in G
104

105
    Raises
106
    ------
107
    NetworkXError
108
        The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
109
        If the input graph is an instance of one of these classes, a
110
        :exc:`NetworkXError` is raised.
111
        The algorithm can only be applied to chordal graphs. If
112
        the input graph is found to be non-chordal, a :exc:`NetworkXError` is raised.
113

114
    Examples
115
    --------
116
    >>> import networkx as nx
117
    >>> G=nx.Graph()
118
    >>> G = nx.generators.classic.path_graph(10)
119
    >>> I = nx.find_induced_nodes(G,1,9,2)
120
    >>> list(I)
121
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
122

123
    Notes
124
    -----
125
    G must be a chordal graph and (s,t) an edge that is not in G.
126

127
    If a treewidth_bound is provided, the search for induced nodes will end
128
    as soon as the treewidth_bound is exceeded.
129

130
    The algorithm is inspired by Algorithm 4 in [1]_.
131
    A formal definition of induced node can also be found on that reference.
132

133
    References
134
    ----------
135
    .. [1] Learning Bounded Treewidth Bayesian Networks.
136
       Gal Elidan, Stephen Gould; JMLR, 9(Dec):2699--2731, 2008.
137
       http://jmlr.csail.mit.edu/papers/volume9/elidan08a/elidan08a.pdf
138
    """
139
    if not is_chordal(G):
140
        raise nx.NetworkXError("Input graph is not chordal.")
141

    
142
    H = nx.Graph(G)
143
    H.add_edge(s, t)
144
    I = set()
145
    triplet = _find_chordality_breaker(H, s, treewidth_bound)
146
    while triplet:
147
        (u, v, w) = triplet
148
        I.update(triplet)
149
        for n in triplet:
150
            if n != s:
151
                H.add_edge(s, n)
152
        triplet = _find_chordality_breaker(H, s, treewidth_bound)
153
    if I:
154
        # Add t and the second node in the induced path from s to t.
155
        I.add(t)
156
        for u in G[s]:
157
            if len(I & set(G[u])) == 2:
158
                I.add(u)
159
                break
160
    return I
161

    
162

    
163
def chordal_graph_cliques(G):
164
    """Returns the set of maximal cliques of a chordal graph.
165

166
    The algorithm breaks the graph in connected components and performs a
167
    maximum cardinality search in each component to get the cliques.
168

169
    Parameters
170
    ----------
171
    G : graph
172
      A NetworkX graph
173

174
    Returns
175
    -------
176
    cliques : A set containing the maximal cliques in G.
177

178
    Raises
179
    ------
180
    NetworkXError
181
        The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
182
        If the input graph is an instance of one of these classes, a
183
        :exc:`NetworkXError` is raised.
184
        The algorithm can only be applied to chordal graphs. If the
185
        input graph is found to be non-chordal, a :exc:`NetworkXError` is raised.
186

187
    Examples
188
    --------
189
    >>> import networkx as nx
190
    >>> e= [(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6),(7,8)]
191
    >>> G = nx.Graph(e)
192
    >>> G.add_node(9)
193
    >>> setlist = nx.chordal_graph_cliques(G)
194
    """
195
    if not is_chordal(G):
196
        raise nx.NetworkXError("Input graph is not chordal.")
197

    
198
    cliques = set()
199
    for C in nx.connected.connected_component_subgraphs(G):
200
        cliques |= _connected_chordal_graph_cliques(C)
201

    
202
    return cliques
203

    
204

    
205
def chordal_graph_treewidth(G):
206
    """Returns the treewidth of the chordal graph G.
207

208
    Parameters
209
    ----------
210
    G : graph
211
      A NetworkX graph
212

213
    Returns
214
    -------
215
    treewidth : int
216
        The size of the largest clique in the graph minus one.
217

218
    Raises
219
    ------
220
    NetworkXError
221
        The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
222
        If the input graph is an instance of one of these classes, a
223
        :exc:`NetworkXError` is raised.
224
        The algorithm can only be applied to chordal graphs. If
225
        the input graph is found to be non-chordal, a :exc:`NetworkXError` is raised.
226

227
    Examples
228
    --------
229
    >>> import networkx as nx
230
    >>> e = [(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6),(7,8)]
231
    >>> G = nx.Graph(e)
232
    >>> G.add_node(9)
233
    >>> nx.chordal_graph_treewidth(G)
234
    3
235

236
    References
237
    ----------
238
    .. [1] https://en.wikipedia.org/wiki/Tree_decomposition#Treewidth
239
    """
240
    if not is_chordal(G):
241
        raise nx.NetworkXError("Input graph is not chordal.")
242

    
243
    max_clique = -1
244
    for clique in nx.chordal_graph_cliques(G):
245
        max_clique = max(max_clique, len(clique))
246
    return max_clique - 1
247

    
248

    
249
def _is_complete_graph(G):
250
    """Returns True if G is a complete graph."""
251
    if nx.number_of_selfloops(G) > 0:
252
        raise nx.NetworkXError("Self loop found in _is_complete_graph()")
253
    n = G.number_of_nodes()
254
    if n < 2:
255
        return True
256
    e = G.number_of_edges()
257
    max_edges = ((n * (n - 1)) / 2)
258
    return e == max_edges
259

    
260

    
261
def _find_missing_edge(G):
262
    """ Given a non-complete graph G, returns a missing edge."""
263
    nodes = set(G)
264
    for u in G:
265
        missing = nodes - set(list(G[u].keys()) + [u])
266
        if missing:
267
            return (u, missing.pop())
268

    
269

    
270
def _max_cardinality_node(G, choices, wanna_connect):
271
    """Returns a the node in choices that has more connections in G
272
    to nodes in wanna_connect.
273
    """
274
#    max_number = None
275
    max_number = -1
276
    for x in choices:
277
        number = len([y for y in G[x] if y in wanna_connect])
278
        if number > max_number:
279
            max_number = number
280
            max_cardinality_node = x
281
    return max_cardinality_node
282

    
283

    
284
def _find_chordality_breaker(G, s=None, treewidth_bound=sys.maxsize):
285
    """ Given a graph G, starts a max cardinality search
286
    (starting from s if s is given and from an arbitrary node otherwise)
287
    trying to find a non-chordal cycle.
288

289
    If it does find one, it returns (u,v,w) where u,v,w are the three
290
    nodes that together with s are involved in the cycle.
291
    """
292

    
293
    unnumbered = set(G)
294
    if s is None:
295
        s = arbitrary_element(G)
296
    unnumbered.remove(s)
297
    numbered = set([s])
298
#    current_treewidth = None
299
    current_treewidth = -1
300
    while unnumbered:  # and current_treewidth <= treewidth_bound:
301
        v = _max_cardinality_node(G, unnumbered, numbered)
302
        unnumbered.remove(v)
303
        numbered.add(v)
304
        clique_wanna_be = set(G[v]) & numbered
305
        sg = G.subgraph(clique_wanna_be)
306
        if _is_complete_graph(sg):
307
            # The graph seems to be chordal by now. We update the treewidth
308
            current_treewidth = max(current_treewidth, len(clique_wanna_be))
309
            if current_treewidth > treewidth_bound:
310
                raise nx.NetworkXTreewidthBoundExceeded(
311
                    "treewidth_bound exceeded: %s" % current_treewidth)
312
        else:
313
            # sg is not a clique,
314
            # look for an edge that is not included in sg
315
            (u, w) = _find_missing_edge(sg)
316
            return (u, v, w)
317
    return ()
318

    
319

    
320
def _connected_chordal_graph_cliques(G):
321
    """Returns the set of maximal cliques of a connected chordal graph."""
322
    if G.number_of_nodes() == 1:
323
        x = frozenset(G.nodes())
324
        return set([x])
325
    else:
326
        cliques = set()
327
        unnumbered = set(G.nodes())
328
        v = arbitrary_element(G)
329
        unnumbered.remove(v)
330
        numbered = set([v])
331
        clique_wanna_be = set([v])
332
        while unnumbered:
333
            v = _max_cardinality_node(G, unnumbered, numbered)
334
            unnumbered.remove(v)
335
            numbered.add(v)
336
            new_clique_wanna_be = set(G.neighbors(v)) & numbered
337
            sg = G.subgraph(clique_wanna_be)
338
            if _is_complete_graph(sg):
339
                new_clique_wanna_be.add(v)
340
                if not new_clique_wanna_be >= clique_wanna_be:
341
                    cliques.add(frozenset(clique_wanna_be))
342
                clique_wanna_be = new_clique_wanna_be
343
            else:
344
                raise nx.NetworkXError("Input graph is not chordal.")
345
        cliques.add(frozenset(clique_wanna_be))
346
        return cliques