Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.5 KB)

1
import itertools
2

    
3
__all__ = ['greedy_coloring_with_interchange']
4

    
5

    
6
class Node(object):
7

    
8
    __slots__ = ['node_id', 'color', 'adj_list', 'adj_color']
9

    
10
    def __init__(self, node_id, n):
11
        self.node_id = node_id
12
        self.color = -1
13
        self.adj_list = None
14
        self.adj_color = [None for _ in range(n)]
15

    
16
    def __repr__(self):
17
        return "Node_id: {0}, Color: {1}, Adj_list: ({2}), \
18
            adj_color: ({3})".format(
19
            self.node_id, self.color, self.adj_list, self.adj_color)
20

    
21
    def assign_color(self, adj_entry, color):
22
        adj_entry.col_prev = None
23
        adj_entry.col_next = self.adj_color[color]
24
        self.adj_color[color] = adj_entry
25
        if adj_entry.col_next is not None:
26
            adj_entry.col_next.col_prev = adj_entry
27

    
28
    def clear_color(self, adj_entry, color):
29
        if adj_entry.col_prev is None:
30
            self.adj_color[color] = adj_entry.col_next
31
        else:
32
            adj_entry.col_prev.col_next = adj_entry.col_next
33
        if adj_entry.col_next is not None:
34
            adj_entry.col_next.col_prev = adj_entry.col_prev
35

    
36
    def iter_neighbors(self):
37
        adj_node = self.adj_list
38
        while adj_node is not None:
39
            yield adj_node
40
            adj_node = adj_node.next
41

    
42
    def iter_neighbors_color(self, color):
43
        adj_color_node = self.adj_color[color]
44
        while adj_color_node is not None:
45
            yield adj_color_node.node_id
46
            adj_color_node = adj_color_node.col_next
47

    
48

    
49
class AdjEntry(object):
50

    
51
    __slots__ = ['node_id', 'next', 'mate', 'col_next', 'col_prev']
52

    
53
    def __init__(self, node_id):
54
        self.node_id = node_id
55
        self.next = None
56
        self.mate = None
57
        self.col_next = None
58
        self.col_prev = None
59

    
60
    def __repr__(self):
61
        return "Node_id: {0}, Next: ({1}), Mate: ({2}), \
62
            col_next: ({3}), col_prev: ({4})".format(
63
            self.node_id,
64
            self.next,
65
            self.mate.node_id,
66
            None if self.col_next is None else self.col_next.node_id,
67
            None if self.col_prev is None else self.col_prev.node_id
68
        )
69

    
70

    
71
def greedy_coloring_with_interchange(original_graph, nodes):
72
    """
73
        This procedure is an adaption of the algorithm described by [1]_,
74
        and is an implementation of coloring with interchange. Please be
75
        advised, that the datastructures used are rather complex because
76
        they are optimized to minimize the time spent identifying
77
        subcomponents of the graph, which are possible candidates for color
78
        interchange.
79

80
    References
81
    ----------
82
    .. [1] Maciej M. Syslo, Marsingh Deo, Janusz S. Kowalik,
83
       Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983.
84
       ISBN 0-486-45353-7.
85
    """
86
    n = len(original_graph)
87

    
88
    graph = {node_id: Node(node_id, n) for node_id in original_graph}
89

    
90
    for (node1, node2) in original_graph.edges():
91
        adj_entry1 = AdjEntry(node2)
92
        adj_entry2 = AdjEntry(node1)
93
        adj_entry1.mate = adj_entry2
94
        adj_entry2.mate = adj_entry1
95
        node1_head = graph[node1].adj_list
96
        adj_entry1.next = node1_head
97
        graph[node1].adj_list = adj_entry1
98
        node2_head = graph[node2].adj_list
99
        adj_entry2.next = node2_head
100
        graph[node2].adj_list = adj_entry2
101

    
102
    k = 0
103
    for node in nodes:
104
        # Find the smallest possible, unused color
105
        neighbors = graph[node].iter_neighbors()
106
        col_used = {graph[adj_node.node_id].color for adj_node in neighbors}
107
        col_used.discard(-1)
108
        k1 = next(itertools.dropwhile(
109
            lambda x: x in col_used, itertools.count()))
110

    
111
        # k1 is now the lowest available color
112
        if k1 > k:
113
            connected = True
114
            visited = set()
115
            col1 = -1
116
            col2 = -1
117
            while connected and col1 < k:
118
                col1 += 1
119
                neighbor_cols = (
120
                    graph[node].iter_neighbors_color(col1))
121
                col1_adj = [it for it in neighbor_cols]
122

    
123
                col2 = col1
124
                while connected and col2 < k:
125
                    col2 += 1
126
                    visited = set(col1_adj)
127
                    frontier = list(col1_adj)
128
                    i = 0
129
                    while i < len(frontier):
130
                        search_node = frontier[i]
131
                        i += 1
132
                        col_opp = (
133
                            col2 if graph[search_node].color == col1 else col1)
134
                        neighbor_cols = (
135
                            graph[search_node].iter_neighbors_color(col_opp))
136

    
137
                        for neighbor in neighbor_cols:
138
                            if neighbor not in visited:
139
                                visited.add(neighbor)
140
                                frontier.append(neighbor)
141

    
142
                    # Search if node is not adj to any col2 vertex
143
                    connected = len(visited.intersection(
144
                        graph[node].iter_neighbors_color(col2))) > 0
145

    
146
            # If connected is false then we can swap !!!
147
            if not connected:
148
                # Update all the nodes in the component
149
                for search_node in visited:
150
                    graph[search_node].color = (
151
                        col2 if graph[search_node].color == col1 else col1)
152
                    col2_adj = graph[search_node].adj_color[col2]
153
                    graph[search_node].adj_color[col2] = (
154
                        graph[search_node].adj_color[col1])
155
                    graph[search_node].adj_color[col1] = col2_adj
156

    
157
                # Update all the neighboring nodes
158
                for search_node in visited:
159
                    col = graph[search_node].color
160
                    col_opp = col1 if col == col2 else col2
161
                    for adj_node in graph[search_node].iter_neighbors():
162
                        if graph[adj_node.node_id].color != col_opp:
163
                            # Direct reference to entry
164
                            adj_mate = adj_node.mate
165
                            graph[adj_node.node_id].clear_color(
166
                                adj_mate, col_opp)
167
                            graph[adj_node.node_id].assign_color(adj_mate, col)
168
                k1 = col1
169

    
170
        # We can color this node color k1
171
        graph[node].color = k1
172
        k = max(k1, k)
173

    
174
        # Update the neighbors of this node
175
        for adj_node in graph[node].iter_neighbors():
176
            adj_mate = adj_node.mate
177
            graph[adj_node.node_id].assign_color(adj_mate, k1)
178

    
179
    return {node.node_id: node.color for node in graph.values()}