How to create a map for Interconnected devices?

Python Help
1

I’m trying to create a random map of few thousand interconnected devices.

Here is an example of the desired output:

m = {
    0: [2, 5, 7],
    1: [8, 9],
    2: [0, 3, 4],
    3: [2, 5],
    4: [2, 7],
    5: [0, 3, 8],
    6: [7, 9],
    7: [0, 4, 6],
    8: [1, 5],
    9: [1, 6]
}

And its plot (The plot is only for demonstration):

layer_zero_map
layer_zero_map1152×648 9.58 KB

As you can see, the value of each key (device) in the map is a list which corresponds to its neighbors (connected device).
For example device 1 is connected to device 8 and device 9:

{1: [8, 9]}

Is there a way to create a map that consist of thousands of devices (keys) which has at least 1 device and at most three devices connected to it?

As shown in the picture there is no device with less than 1 connection or more than 3 connections.

And here is what I have tried:

from random import choice


def create_map(size):
    m = dict()
    for router in range(size):
        m.update({router: []})

    routers = list(m.keys())

    for router in range(size):
        length = 3 - len(m[router])
        if length > 0:
            while length > 0:
                if len(routers) > 0:
                    neighbors = [neighbor for neighbor in routers if neighbor != router]
                    if len(neighbors) < 1:
                        break
                    neighbor = choice(neighbors)
                    if len(neighbors) == 1:
                        if len(m[neighbor]) == 3:
                            break
                    if len(m[neighbor]) < 3:
                        if neighbor not in m[router]:
                            length -= 1
                            m.update({router: m[router] + [neighbor]})
                            m.update({neighbor: m[neighbor] + [router]})
                    else:
                        routers.remove(neighbor)
            else:
                continue
            break
        else:
            if router in routers:
                routers.remove(router)

    _m = m.copy()
    for router, routers in _m.items():
        for length, neighbor in enumerate(routers[:]):
            routers[length] = f'{neighbor:02}'
        del m[router]
        router = f'{router:02}'
        m.update({router: routers})

    return m


size = 1024
m = create_map(size)

for router, neighbors in m.items():
    print(router, neighbors)

But it doesn’t work all the times, and not for all sizes

2

since your key = device
and there is no standard on the geo/location of a single key/device
there is no way to ask Python to print anything resembling a graph structure.

If your devices are called routers and you build mesh network you need predefined routing table.
But in any case, you need to set X-Y location of every device/key/router

What comes next is an algorithm to keep interlinks short (standard solution known from graph theory)

darius

3

I have created this function recently, And it does what I want.
But sometimes there is not a path from each router to the rest (that’s a problem).

Is there a way to fix this?

def create_map(size, n):
    routers = {f'{router:02}': n for router in range(size)}
    m = {f'{router:02}': [] for router in range(size)}

    for _ in range(1000):
        for router in m.keys():
            neighbors = list(routers.keys() - [router])

            # Check if there are any neighbor available
            if not neighbors:
                continue

            neighbor = choice(neighbors)
            neighbor = f'{neighbor:02}'

            # Check if the router is already connected to the neighbor or vice versa
            if router in m[neighbor] or neighbor in m[router]:
                continue

            # Check if the router is still exist in routers, after several routers have
            # been deleted in the past via 'del routers[neighbor]' bellow
            if router not in routers or neighbor not in routers:
                continue

            # Connect the router and the neighbor
            m.update({router: m[router] + [neighbor]})
            m.update({neighbor: m[neighbor] + [router]})

            routers[router] -= 1
            routers[neighbor] -= 1

            if routers[neighbor] == 0:
                del routers[neighbor]

            if routers[router] == 0:
                del routers[router]
        else:
            break

    return m

size: it is the number of routers (devices).
n: it is the number of connections it has.