Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / mycielski.py @ 5cef0f13

History | View | Annotate | Download (3.36 KB)

1
#    Copyright (C) 2010-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7

    
8
"""Functions related to the Mycielski Operation and the Mycielskian family
9
of graphs.
10

11
"""
12

    
13
import networkx as nx
14
from networkx.utils import not_implemented_for
15

    
16
__all__ = ['mycielskian', 'mycielski_graph']
17

    
18

    
19
@not_implemented_for('directed')
20
@not_implemented_for('multigraph')
21
def mycielskian(G, iterations=1):
22
    r"""Returns the Mycielskian of a simple, undirected graph G
23

24
    The Mycielskian of graph preserves a graph's triangle free
25
    property while increasing the chromatic number by 1.
26

27
    The Mycielski Operation on a graph, :math:`G=(V, E)`, constructs a new
28
    graph with :math:`2|V| + 1` nodes and :math:`3|E| + |V|` edges.
29

30
    The construction is as follows:
31

32
    Let :math:`V = {0, ..., n-1}`. Construct another vertex set
33
    :math:`U = {n, ..., 2n}` and a vertex, `w`.
34
    Construct a new graph, `M`, with vertices :math:`U \bigcup V \bigcup w`.
35
    For edges, :math:`(u, v) \in E` add edges :math:`(u, v), (u, v + n)`, and
36
    :math:`(u + n, v)` to M. Finally, for all vertices :math:`u \in U`, add
37
    edge :math:`(u, w)` to M.
38

39
    The Mycielski Operation can be done multiple times by repeating the above
40
    process iteratively.
41

42
    More information can be found at https://en.wikipedia.org/wiki/Mycielskian
43

44
    Parameters
45
    ----------
46
    G : graph
47
        A simple, undirected NetworkX graph
48
    iterations : int
49
        The number of iterations of the Mycielski operation to
50
        perform on G. Defaults to 1. Must be a non-negative integer.
51

52
    Returns
53
    -------
54
    M : graph
55
        The Mycielskian of G after the specified number of iterations.
56

57
    Notes
58
    ------
59
    Graph, node, and edge data are not necessarily propagated to the new graph.
60

61
    """
62

    
63
    n = G.number_of_nodes()
64
    M = nx.convert_node_labels_to_integers(G)
65

    
66
    for i in range(iterations):
67
        n = M.number_of_nodes()
68
        M.add_nodes_from(range(n, 2 * n))
69
        old_edges = list(M.edges())
70
        M.add_edges_from((u, v + n) for u, v in old_edges)
71
        M.add_edges_from((u + n, v) for u, v in old_edges)
72
        M.add_node(2 * n)
73
        M.add_edges_from((u + n, 2 * n) for u in range(n))
74

    
75
    return M
76

    
77

    
78
def mycielski_graph(n):
79
    """Generator for the n_th Mycielski Graph.
80

81
    The Mycielski family of graphs is an infinite set of graphs.
82
    :math:`M_1` is the singleton graph, :math:`M_2` is two vertices with an
83
    edge, and, for :math:`i > 2`, :math:`M_i` is the Mycielskian of
84
    :math:`M_{i-1}`.
85

86
    More information can be found at
87
    http://mathworld.wolfram.com/MycielskiGraph.html
88

89
    Parameters
90
    ----------
91
    n : int
92
        The desired Mycielski Graph.
93

94
    Returns
95
    -------
96
    M : graph
97
        The n_th Mycielski Graph
98

99
    Notes
100
    -----
101
    The first graph in the Mycielski sequence is the singleton graph.
102
    The Mycielskian of this graph is not the :math:`P_2` graph, but rather the
103
    :math:`P_2` graph with an extra, isolated vertex. The second Mycielski
104
    graph is the :math:`P_2` graph, so the first two are hard coded.
105
    The remaining graphs are generated using the Mycielski operation.
106

107
    """
108

    
109
    if n < 1:
110
        raise nx.NetworkXError("must satisfy n >= 0")
111

    
112
    if n == 1:
113
        return nx.empty_graph(1)
114

    
115
    else:
116
        return mycielskian(nx.path_graph(2), n - 2)