1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
import doctest
import sys
import unittest
def check_if_graph_is_line_and_get_consecutive_nodes(graph):
"""
>>> graph = {'edge12': ['node1', 'node2'], 'edge23': ['node2', 'node3']}
>>> check_if_graph_is_line_and_get_consecutive_nodes(graph)
['node1', 'node2', 'node3']
>>> graph = {'edge12': ['node1', 'node2'], 'edge34': ['node3', 'node4']}
>>> check_if_graph_is_line_and_get_consecutive_nodes(graph)
Traceback (most recent call last):
...
ValueError: The graph is not a line.
"""
# Example: graph = {'edge12': ['node1', 'node2'], 'edge23': ['node2', 'node3']}
_check_the_graph_format(graph)
dict_node_edges = _build_dict_node_edges(graph)
# Example: dict_node_edges == {
# 'node1': ['edge12'],
# 'node2': ['edge12', 'edge23'],
# 'node3': ['edge23']
# }
dict_edge_count_node = _build_dict_edge_count_node(dict_node_edges)
# Example: dict_edge_count_node == {1: ['node1', 'node3'], 2: ['node2']}
_check_if_the_graph_is_a_line(dict_edge_count_node)
result = _build_line(graph, dict_node_edges, dict_edge_count_node)
# Example: result == ['node1', 'node2', 'node3']
return result
def _check_the_graph_format(graph):
"""
>>> graph = {'edge12': ['node1', 'node2'], 'edge23': ['node2', 'node3']}
>>> _check_the_graph_format(graph)
"""
assert isinstance(graph, dict)
assert graph
for edge, nodes in graph.items():
assert isinstance(edge, str)
assert isinstance(nodes, list)
assert len(nodes) == 2
node1, node2 = nodes
assert isinstance(node1, (int, str))
assert isinstance(node2, (int, str))
assert node1 != node2
def _build_dict_node_edges(graph):
"""
>>> graph = {'edge12': ['node1', 'node2'], 'edge23': ['node2', 'node3']}
>>> _build_dict_node_edges(graph) == {
... 'node1': ['edge12'],
... 'node2': ['edge12', 'edge23'],
... 'node3': ['edge23'],
... }
True
"""
dict_node_edges = dict()
for edge, nodes in graph.items():
for node in nodes:
dict_node_edges.setdefault(node, []).append(edge)
return dict_node_edges
def _build_dict_edge_count_node(dict_node_edges):
"""
>>> dict_node_edges = {
... 'node1': ['edge12'],
... 'node2': ['edge12', 'edge23'],
... 'node3': ['edge23'],
... }
>>> _build_dict_edge_count_node(dict_node_edges)
{1: ['node1', 'node3'], 2: ['node2']}
"""
dict_edge_count_node = dict()
for node, edges in dict_node_edges.items():
dict_edge_count_node.setdefault(len(edges), []).append(node)
return dict_edge_count_node
def _check_if_the_graph_is_a_line(dict_edge_count_node):
"""
>>> dict_edge_count_node = {1: ['node1', 'node3'], 2: ['node2']}
>>> _check_if_the_graph_is_a_line(dict_edge_count_node)
"""
# Check if 2 nodes have 1 edge and all the other nodes have 2 edges.
if len(dict_edge_count_node.get(1, [])) != 2 or set(dict_edge_count_node) - {1, 2} != set():
raise ValueError("The graph is not a line.")
def _build_line(graph, dict_node_edges, dict_edge_count_node):
"""
>>> graph = {'edge12': ['node1', 'node2'], 'edge23': ['node2', 'node3']}
>>> dict_node_edges = {
... 'node1': ['edge12'],
... 'node2': ['edge12', 'edge23'],
... 'node3': ['edge23'],
... }
>>> dict_edge_count_node = {1: ['node1', 'node3'], 2: ['node2']}
>>> _build_line(graph, dict_node_edges, dict_edge_count_node)
['node1', 'node2', 'node3']
"""
current_node = dict_edge_count_node[1][0]
current_edge = dict_node_edges[current_node][0]
result = [current_node]
while True:
node1, node2 = graph[current_edge]
next_node = node1 if node1 != current_node else node2
result.append(next_node)
next_node_edges = dict_node_edges[next_node]
if len(next_node_edges) == 1:
break # end of the line
edge1, edge2 = next_node_edges
next_edge = edge1 if edge1 != current_edge else edge2
current_node = next_node
current_edge = next_edge
return result
class Test(unittest.TestCase):
def test_good_line(self):
graph = {
'A': ['tg', 17],
'B': [59, 60],
'C': [60, 61],
'D': [57, 'tt'],
'E': [61, 'tg'],
'F': ['tt', 59],
}
nodes = check_if_graph_is_line_and_get_consecutive_nodes(graph)
self.assertEqual(nodes, [17, 'tg', 61, 60, 59, 'tt', 57])
def test_one_edge(self):
graph = {'edge12': [1, 2]}
nodes = check_if_graph_is_line_and_get_consecutive_nodes(graph)
self.assertEqual(nodes, [1, 2])
def test_disconnected_graph(self):
graph = {
'edge12': [1, 2],
'edge23': [2, 3],
'edge45': [4, 5],
'edge56': [5, 6],
}
with self.assertRaises(ValueError):
check_if_graph_is_line_and_get_consecutive_nodes(graph)
def test_node_with_3_edges(self):
graph = {
'edge12': [1, 2],
'edge13': [1, 3],
'edge14': [1, 4],
}
with self.assertRaises(ValueError):
check_if_graph_is_line_and_get_consecutive_nodes(graph)
if __name__ == "__main__":
failure_count, _ = doctest.testmod()
if failure_count != 0:
sys.exit(1)
unittest.main() |
