Problem with making torus graph in Graph3D by identifying edge of a square graph

Background: I want to imply periodicity along the given edges for a graph. For example in a square lattice with identifying parallel edges, you can construct a torus. consider the following image

enter image description here

So I start with the construction of a square lattice network

nmax = 15;(*Length of lattice*) points = Flatten[Table[{i, j}, {i, -nmax, nmax}, {j, -nmax, nmax}],       1];(*list coordinate of the lattice*) d1 = (Sqrt[2] + 1)/2;(*Max distance to construct linked between coordination of the lattice*) d0 = 1/2;(*Min distance to construct linked between coordination of the lattice*) nn = Nearest[points -> "Index"]; (*function which determine the nearest of a vertex. we can do this*)  (*also by for example DistanceMatrixor or NearestNeighborGraph*) ha = Select[    Flatten[ParallelTable[Module[{pp}, pp = nn[points[[i]], {10, d1}];       Select[{i + 0 pp, pp,            Norm /@ ((points[[pp]]\[Transpose] -                 points[[i]])\[Transpose])}\[Transpose],          d1 > #[[3]] &][[All, {1, 2}]]], {i, 1, Length[points]}],      1], #[[1]] > #[[2]] &]; (*I use select to just consider one linke between two vortex ,*) (*This part is somehow hard to catch at a glince but it did not *) (*change following discussion. Consider this line  as a function*) (*making nearest neighbor links*) Graph3D[ha] 

where gives,

enter image description here

now I am looking to identifying edges. I use the following, for the left and right one

vortexL =points//SortBy[Flatten[Position[#[[All, 1]], Max[#[[All, 1]]]]], points[[#, 2]] &] &; vortexR =points//SortBy[Flatten[Position[#[[All, 1]], Min[#[[All, 1]]]]],points[[#, 2]] &] &; 

and for up and down edge we have

vortexU =points//SortBy[Flatten[Position[#[[All, 2]], Max[#[[All, 2]]]]], points[[#, 1]] &] &; vortexD =points//SortBy[Flatten[Position[#[[All, 2]], Min[#[[All, 2]]]]],points[[#, 1]] &] &; 

now i define identifier as

vchanger = {Table[vortexL[[i]] -> vortexR[[i]], {i, 1, Length@vortexL}],Table[vortexU[[i]]-> vortexD[[i]], {i, 1, Length@vortexU}]}; 

By applying it on ha (the link address) sequentially you can see how periodicity along those edges established,

ha = ha /. vchanger[[1]]; Graph3D[ha] 

enter image description here


ha = ha /. vchanger[[2]]; Graph3D[ha] 

where gives,

enter image description here

although it seems torus, by rotation it, you notify two crossings of the links

enter image description here

Question? So I am wondering, I did a mistake to construct the lattice and implication of periodic boundary condition, or this is the problem of Mathematica? Do someone has an option for Graph3D to make it correct shape?

Update My problem is almost the visualization of correct geometry this lattice has.

In combat, how many creatures can be in a 5 foot square at the end of a turn? [closed]

In D&D 5e, basically all PCs fit in on a 5 foot square. I want to figure out how much that 5 foot square can hold at end of turn by rules as written.

My first estimation is 3 people. Using the rule that allows creatures to use other creatures that are a size category bigger then them as a mount, allows for the situation: A centaur barbarian counts as large for carrying and pushing so with some plate armored fighter on top, duel wielding lances, a half-ling sits on the fighters shoulders, gets us to three.

That is 3, but can we get more?

Finding multiple paths through a grid such that every grid square is equally used


Here’s the setup: I have an $ N$ x $ N$ grid of tiles, and a list of $ M$ agents that need to move across the grid. Each agent has its own start tile $ S(a)$ , end tile $ E(a)$ , and an exact number of steps $ D(a)$ it must make. Each step consists of a one-tile move horizontally, vertically, or staying in place. For each agent, $ D(a)$ is usually much larger than the Manhattan distance between $ S(a)$ and $ E(a)$ , so the path the agent takes is not necessarily a straight line from $ S(a)$ to $ E(a)$ . Furthermore, the sum of all $ D(a)$ is expected to be much larger than $ N$ x $ N$ , so every tile will be used at least once. Agent paths are allowed to intersect with other paths and with themselves, and the number of agents on a tile at any given time doesn’t matter.

The Problem

I would like to find paths for each agent that begin at $ S(a)$ , end at $ E(a)$ , and are exactly $ D(a)$ steps long, with the goal of minimizing the maximum number of times any given tile is used. More formally, given an agent path $ P_0 \ldots P_n$ , let $ C(P, t)$ be the number of times tile $ t$ appears in $ P$ , and let $ A(t)$ be the sum of $ C(P, t)$ over all agent paths. I would like to find agent paths that minimize the maximum $ A(t)$ over all tiles $ t$ .

My intuition tells me that this problem is almost certainly NP hard, so I’m looking for some kind of approximation or heuristic.

First Attempt

My first stab at solving this was to find each path sequentially. For each agent, I create a 3-dimensional $ N$ x $ N$ x $ D(a)$ search space, then use A* search to find the min-cost path from $ [S(a), 0]$ to $ [E(a), D(a)]$ . The cost of each node in the search is the number of times that tile has been used by previous paths. Then, once the path is found, I add to the cost of each tile used, and proceed to the next agent. Of course, this leads to the problem that while the last agent path will be pretty good, the first agent path will be essentially random because the grid is yet totally unused. So, I just loop this process a few times; once the last path is computed and the tile costs updated, I loop back to the first path, subtract from the grid the costs that agent contributed, then recompute that path and add the new costs in. After 3 or 4 loops, I converge on a pretty reasonable solution.

But I’m hoping there’s a better idea out there. Any ideas or references to similar problems that I could read up on would be very welcome.

Why is finding square root of perfect square $O(M(n))$

I saw this question and its answer on Theoretical Computer Science stack exchange and I can’t understand why the complexity of finding the root is the same as that of a multiplication. My thought was that we may need more than $ O(1)$ multiplications to find the root (using Newton’s Iteration as stated in the answer, since the method may need more than $ O(1)$ steps).

Is there an upper limit not depending on $ n$ to the amount of multiplications we may need? Or a method to find the root with enough accuracy(which means finding the actual root) after $ O(1)$ steps? Am I missing something?

Note: I didn’t ask this on theoretical CS stack exchange, since it is supposed to be for professional researchers in CS and no one asked about this in the comments so assume it isn’t a research level question even if it is about an explanation of one (research level question).

Find bipartial subgraph such that mean square deviation of edge lengths is minimum

Let there be graph $ G = (V, \, E)$ . $ G$ has neither loops nor parallel arcs.

$ V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$

For simplicity’s sake, let’s consider $ G$ is directed.

$ \forall \ e \in E \ \, e.tail \in A, \, e.head \in B, \, e.length \in (\mathbb{Z} \cap [1, 100]) \cup -\infty \ \forall \ a \in A, \, b \in B \ \ \exists! \ e \in E: e = (a, b)$

The goal is to develop an algorithm that finds a bipartite subgraph $ G’ = (V’, \, E’)$ such that:

1) $ |\,E’\;|$ is maximum;
2) Under restriction 1), $ \sum \limits_{e’ \in E’} (e’.length – (\sum \limits_{e’ \in E’} e’.length \; / \; |\, E’ \; |))^2 $ is minimum possible, where $ | \, E’ \; |$ is cardinality of $ E’$ .

For example, let graph $ G$ be defined as following: enter image description here

In this case, the correct solution is: enter image description here

The algorithm should run in polynomial time.

Count number of pairs of elements whose product is a perfect square

Given two arrays whose elements lie between $ [1,10^5]$ and the size of arrays is $ [1,10^5]$ , how can we find the total number of pairs of elements from these arrays such that their product is a perfect square? The arrays may have same elements.

For example:

Array 1: {1, 2, 4, 5}

Array 2: {4, 8, 16, 125}

Output : 6

The pairs are (1, 4), (1, 16), (2, 8), (4, 4), (4, 16), (5, 125).

If the array size is $ 10^5$ , an $ n^2$ algorithm would be inefficient.

How to get the address of a nearby square on a chess board?

I’m making a chess game from scratch and I got stuck.

So far I have all my figures placed, I have the positions set, I’ve already done the collision detection and everything.

When I click the figure that is in position A1 for example, I want to make two green rectangles at positions A2 and A3, and they will be used to make the figure move.

Is there a method for to add 1 to the string “A1” to form the string “A2” or something? Because thats all I really need right now.

Also if there’s a more clever way to make the positions please let me know.

As an example, here is how I currently look up my display positions using the A1, A2 etc. location codes:

let positions = {         A1 : [10, 710],B1 : [110, 710],C1 : [210, 710],D1 : [310, 710],E1 : [410, 710],F1 : [510, 710],G1 : [610, 710],H1 : [710, 710],         A2 : [10, 610],B2 : [110, 610],C2 : [210, 610],D2 : [310, 610],E2 : [410, 610],F2 : [510, 610],G2 : [610, 610],H2 : [710, 610],         A3 : [10, 510],B3 : [110, 510],C3 : [210, 510],D3 : [310, 510],E3 : [410, 510],F3 : [510, 510],G3 : [610, 510],H3 : [710, 510],         A4 : [10, 410],B4 : [110, 410],C4 : [210, 410],D4 : [310, 410],E4 : [410, 410],F4 : [510, 410],G4 : [610, 410],H4 : [710, 410],         A5 : [10, 310],B5 : [110, 310],C5 : [210, 310],D5 : [310, 310],E5 : [410, 310],F5 : [510, 310],G5 : [610, 310],H5 : [710, 310],         A6 : [10, 210],B6 : [110, 210],C6 : [210, 210],D6 : [310, 210],E6 : [410, 210],F6 : [510, 210],G6 : [610, 210],H6 : [710, 210],         A7 : [10, 110],B7 : [110, 110],C7 : [210, 110],D7 : [310, 110],E7 : [410, 110],F7 : [510, 110],G7 : [610, 110],H7 : [710, 110],         A8 : [10, 10], B8 : [110, 10], C8 : [210, 10], D8 : [310, 10], E8 : [410, 10], F8 : [510, 10], G8 : [610, 10], H8 : [710, 10],     } 

the [0] of the arrays is x and the [1] is y, and that’s also how I placed the figures.