[Python] Remove networkx dependency

[bcollazo]

It seems using a pure-python dictionary-based data structure for graph operations makes catanatron simulate games faster than using the nxgraph library. nxgraph is mostly used today just to consult neighbors for a given node, and so building a lookup table at game initialization (or even at simulation initialization) could make catanatron faster.

[pachewise]

At the very least, it looks like we can move the dependency to catanatron gym, as all of the production usages are there (we define the graphs in catanatron.models.board, but only use them in the gym and in tests). That said, it looks like we do use the graph in the catanatron_gym - is that a usage we can easily replace with python stdlib objects or a performant custom class?

[bcollazo]

There are some production usages of the STATIC_GRAPH object (an nx.Graph) in core board methods like board.build_settlement or the longest_acyclic_path method (which are used by catanatron_core). Tho they look like its mostly to "lookup neighbors" given a node.

These usages could be substituted to reading from a hard-coded lookup table (be it a dictionary or multidimensional array). Something like this seems to work:

NEIGHBORS = [list(STATIC_GRAPH.neighbors(i)) for i in range(72)]

That is, compute that once, save the result in a hardcoded python object of literals, and use that instead.

[bcollazo]

Here the result:

[[5, 1, 20],
 [2, 0, 6],
 [1, 3, 9],
 [2, 4, 12],
 [3, 5, 15],
 [4, 0, 16],
 [1, 7, 23],
 [8, 6, 24],
 [7, 9, 27],
 [8, 2, 10],
 [9, 11, 29],
 [10, 12, 32],
 [11, 3, 13],
 [12, 14, 34],
 [13, 15, 37],
 [14, 4, 17],
 [18, 5, 21],
 [15, 18, 39],
 [17, 16, 40],
 [21, 20, 46],
 [0, 19, 22],
 [16, 19, 43],
 [20, 23, 49],
 [6, 22, 52],
 [7, 25, 53],
 [26, 24, 54],
 [25, 27, 57],
 [26, 8, 28],
 [27, 29, 59],
 [28, 10, 30],
 [29, 31, 61],
 [30, 32, 64],
 [31, 11, 33],
 [32, 34, 66],
 [33, 13, 35],
 [34, 36, 68],
 [35, 37, 71],
 [36, 14, 38],
 [37, 39, 73],
 [38, 17, 41],
 [42, 18, 44],
 [39, 42, 75],
 [41, 40, 76],
 [44, 21, 47],
 [40, 43, 79],
 [47, 46, 84],
 [19, 45, 48],
 [43, 45, 81],
 [46, 49, 87],
 [22, 48, 50],
 [49, 51, 89],
 [52, 50, 92],
 [51, 23, 53],
 [24, 52, 94],
 [25, 55, 95],
 [56, 54],
 [55, 57],
 [56, 26, 58],
 [57, 59],
 [58, 28, 60],
 [59, 61],
 [60, 30, 62],
 [61, 63],
 [62, 64],
 [63, 31, 65],
 [64, 66],
 [65, 33, 67],
 [66, 68],
 [67, 35, 69],
 [68, 70],
 [69, 71],
 [70, 36, 72]]

[bcollazo]

It would break the ability for us to support customly-shaped maps, but thats ok for now. It seems we could always make the "72" bigger and just require all maps to be contained in a hexagon-like sea of water tiles, like they are right now. Then this would hold.

[pachewise]

where's the 72 coming from?

[zarns]

Can this be closed? I don't see that nxgraph is still used after this 2021 PR

[bcollazo]

Ahh.. I think the title of this Issue can be improved. It's actually called networkx the library I am referring to. Let me make the update. Its still used here: https://github.com/bcollazo/catanatron/blob/master/catanatron_core/catanatron/models/board.py#L7C8-L7C16. That's the STATIC_GRAPH usage I refer to above.