SHARE
TWEET

Untitled

a guest Jan 21st, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import pprint
  2. import random
  3.  
  4. import matplotlib.pyplot as plt
  5. import networkx as nx
  6.  
  7. MAT_ROWS = 7
  8. MAT_COLS = 7
  9. MAT_SIZE = MAT_ROWS * MAT_COLS
  10. MAT_FOLD_SIZE = 3
  11. HI = 3
  12. LO = 2
  13.  
  14. assert MAT_ROWS == MAT_COLS
  15.  
  16. # Nodes matrix
  17. #####
  18.  
  19. matrix = []
  20.  
  21. for i in range(MAT_ROWS):
  22.     matrix.append([j + i * MAT_COLS for j in range(MAT_COLS)])
  23.  
  24. print("## Matrix\n")
  25. pprint.pprint(matrix)
  26. print("")
  27.  
  28. # LED index map matrix
  29. #####
  30.  
  31. led_matrix = []
  32.  
  33. for i in range(MAT_ROWS):
  34.     offset = max(led_matrix[-1]) + MAT_FOLD_SIZE + 1 if len(led_matrix) else 0
  35.     row = [j + offset for j in range(MAT_COLS)]
  36.     row = list(reversed(row)) if i % 2 == 1 else row
  37.     led_matrix.append(row)
  38.  
  39. print("## LED index matrix\n")
  40. pprint.pprint(led_matrix)
  41. print("")
  42.  
  43. # Adjacency cost matrix
  44. #####
  45.  
  46. adj_cost_mat = [
  47.     [0 for j in range(MAT_SIZE)]
  48.     for i in range(MAT_SIZE)
  49. ]
  50.  
  51. for i in range(MAT_ROWS):
  52.     for j in range(MAT_COLS):
  53.         adj_idx = i + j * 7
  54.  
  55.         cost_hi = [
  56.             (i - 1, j - 1),
  57.             (i - 1, j + 1),
  58.             (i + 1, j - 1),
  59.             (i + 1, j + 1)
  60.         ]
  61.  
  62.         cost_lo = [
  63.             (i - 1, j),
  64.             (i, j - 1),
  65.             (i, j),
  66.             (i, j + 1),
  67.             (i + 1, j)
  68.         ]
  69.  
  70.         for tup in cost_hi + cost_lo:
  71.             try:
  72.                 assert tup[0] >= 0 and tup[1] >= 0
  73.                 matrix[tup[0]][tup[1]]
  74.                 tup_idx = tup[0] + tup[1] * 7
  75.                 cost_val = HI if tup in cost_hi else LO
  76.                 adj_cost_mat[adj_idx][tup_idx] = cost_val
  77.                 adj_cost_mat[tup_idx][adj_idx] = cost_val
  78.             except (IndexError, AssertionError):
  79.                 pass
  80.  
  81. print("## Adj. cost matrix\n")
  82. for row in adj_cost_mat:
  83.     print(row)
  84. print("")
  85.  
  86. # Adjacency cost matrix (C literal)
  87. #####
  88.  
  89. print("## Adj. cost matrix (C literal)\n")
  90. print("{")
  91.  
  92. for i, adj_row in enumerate(adj_cost_mat):
  93.     rstr = "  {}".format(str(adj_row).replace("[", "{").replace("]", "}"))
  94.     print("{},".format(rstr) if i != len(adj_row) - 1 else "{}".format(rstr))
  95.  
  96. print("}")
  97. print("")
  98.  
  99. # nx.Graph built from the previous data
  100. #####
  101.  
  102. graph = nx.Graph()
  103. graph.add_nodes_from(range(MAT_ROWS * MAT_COLS))
  104.  
  105. for i, adj_cost_row in enumerate(adj_cost_mat):
  106.     for j, cost in enumerate(adj_cost_row):
  107.         if cost > 0:
  108.             graph.add_edge(i, j, weight=cost)
  109.  
  110. nx.draw_spectral(graph)
  111. plt.show()
  112.  
  113. assert list(list(nx.connected_components(graph))[0]) == range(MAT_SIZE)
  114.  
  115. # Tests
  116. #####
  117.  
  118. print("## Shortest paths\n")
  119.  
  120. test_paths = {
  121.     (0, 3): [0, 1, 2, 3],
  122.     (0, 21): [0, 7, 14, 21],
  123.     (0, 24): [0, 8, 16, 24],
  124.     (3, 6): [3, 4, 5, 6],
  125.     (3, 21): [3, 9, 15, 21],
  126.     (3, 24): [3, 10, 17, 24],
  127.     (3, 27): [3, 11, 19, 27],
  128.     (6, 24): [6, 12, 18, 24],
  129.     (6, 27): [6, 13, 20, 27],
  130.     (21, 24): [21, 22, 23, 24],
  131.     (21, 42): [21, 28, 35, 42],
  132.     (24, 27): [24, 25, 26, 27],
  133.     (24, 42): [24, 30, 36, 42],
  134.     (24, 45): [24, 31, 38, 45],
  135.     (24, 48): [24, 32, 40, 48],
  136.     (27, 45): [27, 33, 39, 45],
  137.     (27, 48): [27, 34, 41, 48],
  138.     (42, 45): [42, 43, 44, 45]
  139. }
  140.  
  141. for (source, target), expected_path in test_paths.items():
  142.     res_path = nx.dijkstra_path(graph, source=source, target=target)
  143.     assert res_path == expected_path
  144.     print("Shortest path {0:0=2d} -> {1:0=2d}: {2}".format(
  145.         source, target,
  146.         ["{0:0=2d}".format(item) for item in res_path]))
  147.  
  148. print("")
  149.  
  150. pprint.pprint([
  151.     ["{0:0=2d}".format(item) for item in matrix[i]]
  152.     for i in range(len(matrix))
  153. ])
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top