Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.91 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Haakon H. Rød (haakonhr@gmail.com)
10
"""
11
Algorithms for asteroidal triples and asteroidal numbers in graphs.
12

13
An asteroidal triple in a graph G is a set of three non-adjacent vertices
14
u, v and w such that there exist a path between any two of them that avoids
15
closed neighborhood of the third. More formally, v_j, v_k belongs to the same
16
connected component of G - N[v_i], where N[v_i] denotes the closed neighborhood
17
of v_i. A graph which does not contain any asteroidal triples is called
18
an AT-free graph. The class of AT-free graphs is a graph class for which
19
many NP-complete problems are solvable in polynomial time. Amongst them,
20
independent set and coloring.
21
"""
22
import networkx as nx
23
from networkx.utils import not_implemented_for
24

    
25
__all__ = ["is_at_free", "find_asteroidal_triple"]
26

    
27

    
28
@not_implemented_for("directed")
29
@not_implemented_for("multigraph")
30
def find_asteroidal_triple(G):
31
    r"""Find an asteroidal triple in the given graph.
32

33
    An asteroidal triple is a triple of non-adjacent vertices such that
34
    there exists a path between any two of them which avoids the closed
35
    neighborhood of the third. It checks all independent triples of vertices
36
    and whether they are an asteroidal triple or not. This is done with the
37
    help of a data structure called a component structure.
38
    A component structure encodes information about which vertices belongs to
39
    the same connected component when the closed neighborhood of a given vertex
40
    is removed from the graph. The algorithm used to check is the trivial
41
    one, outlined in [1]_, which has a runtime of
42
    :math:`O(|V||\overline{E} + |V||E|)`, where the second term is the
43
    creation of the component structure.
44

45
    Parameters
46
    ----------
47
    G : NetworkX Graph
48
        The graph to check whether is AT-free or not
49

50
    Returns
51
    -------
52
    list or None
53
        An asteroidal triple is returned as a list of nodes. If no asteroidal
54
        triple exists, i.e. the graph is AT-free, then None is returned.
55
        The returned value depends on the certificate parameter. The default
56
        option is a bool which is True if the graph is AT-free, i.e. the
57
        given graph contains no asteroidal triples, and False otherwise, i.e.
58
        if the graph contains at least one asteroidal triple.
59

60
    Notes
61
    -----
62
    The component structure and the algorithm is described in [1]_. The current
63
    implementation implements the trivial algorithm for simple graphs.
64

65
    References
66
    ----------
67
    .. [1] Ekkehard Köhler,
68
       "Recognizing Graphs without asteroidal triples",
69
       Journal of Discrete Algorithms 2, pages 439-452, 2004.
70
       https://www.sciencedirect.com/science/article/pii/S157086670400019X
71
    """
72
    V = set(G.nodes)
73

    
74
    if len(V) < 6:
75
        # An asteroidal triple cannot exist in a graph with 5 or less vertices.
76
        return None
77

    
78
    component_structure = create_component_structure(G)
79
    E_complement = set(nx.complement(G).edges)
80

    
81
    for e in E_complement:
82
        u = e[0]
83
        v = e[1]
84
        u_neighborhood = set(G[u]).union([u])
85
        v_neighborhood = set(G[v]).union([v])
86
        union_of_neighborhoods = u_neighborhood.union(v_neighborhood)
87
        for w in V - union_of_neighborhoods:
88
            """Check for each pair of vertices whether they belong to the
89
            same connected component when the closed neighborhood of the
90
            third is removed."""
91
            if (component_structure[u][v] == component_structure[u][w] and
92
                component_structure[v][u] == component_structure[v][w] and
93
                    component_structure[w][u] == component_structure[w][v]):
94
                return [u, v, w]
95

    
96
    return None
97

    
98

    
99
@not_implemented_for("directed")
100
@not_implemented_for("multigraph")
101
def is_at_free(G):
102
    """Check if a graph is AT-free.
103

104
    The method uses the `find_asteroidal_triple` method to recognize
105
    an AT-free graph. If no asteroidal triple is found the graph is
106
    AT-free and True is returned. If at least one asteroidal triple is
107
    found the graph is not AT-free and False is returned.
108

109
    Parameters
110
    ----------
111
    G : NetworkX Graph
112
        The graph to check whether is AT-free or not.
113

114
    Returns
115
    -------
116
    bool
117
        True if G is AT-free and False otherwise.
118

119
    Examples
120
    --------
121
    >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (4, 5)])
122
    >>> nx.is_at_free(G)
123
    True
124

125
    >>> G = nx.cycle_graph(6)
126
    >>> nx.is_at_free(G)
127
    False
128
    """
129
    return find_asteroidal_triple(G) is None
130

    
131

    
132
@not_implemented_for("directed")
133
@not_implemented_for("multigraph")
134
def create_component_structure(G):
135
    r"""Create component structure for G.
136

137
    A *component structure* is an `nxn` array, denoted `c`, where `n` is
138
    the number of vertices,  where each row and column corresponds to a vertex.
139

140
    .. math::
141
        c_{uv} = \begin{cases} 0, if v \in N[u] \\
142
            k, if v \in component k of G \setminus N[u] \end{cases}
143

144
    Where `k` is an arbitrary label for each component. The structure is used
145
    to simplify the detection of asteroidal triples.
146

147
    Parameters
148
    ----------
149
    G : NetworkX Graph
150
        Undirected, simple graph.
151

152
    Returns
153
    -------
154
    component_structure : dictionary
155
        A dictionary of dictionaries, keyed by pairs of vertices.
156

157
    """
158
    V = set(G.nodes)
159
    component_structure = {}
160
    for v in V:
161
        label = 0
162
        closed_neighborhood = set(G[v]).union(set([v]))
163
        row_dict = {}
164
        for u in closed_neighborhood:
165
            row_dict[u] = 0
166

    
167
        G_reduced = G.subgraph(set(G.nodes) - closed_neighborhood)
168
        for cc in nx.connected_components(G_reduced):
169
            label += 1
170
            for u in cc:
171
                row_dict[u] = label
172

    
173
        component_structure[v] = row_dict
174

    
175
    return component_structure