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() |
Partager