Efficiently detect overlapping networks

I know how to detect overlapping networks. There are two ways to do this: by using netaddr’s “IPNetwork in IPNetwork” or ipaddress’s “overlaps” method. The question is how to find overlapping networks in array in most efficient way.

At the moment, I use this code:

networks = {
    IPNetwork('10.1.0.0/24'): 'net2',
    IPNetwork('10.0.0.0/8'): 'net1',
    IPNetwork('10.0.0.0/16'): 'net3',
    IPNetwork('10.0.0.0/24'): 'net4',
    IPNetwork('192.168.0.0/16'): 'net5',
    IPNetwork('192.168.0.0/23'): 'net6',
    IPNetwork('192.168.1.0/24'): 'net7',
    IPNetwork('172.16.0.0/12'): 'net8'
}

net = sorted([key for key in networks.keys()])
for pi in range(0, len(net)-1):
    for si in range(pi+1, len(net)):
        if net[si] in net[pi]:
            print(f'{net[si]} ({networks[net[si]]}) overlaps with '
                  f'{net[pi]} ({networks[net[pi]]})')

It does the job, but uses many iterations (e.g. for 8 entries there are 7+6+5+… = 28 comparisons) and I’m looking for a more efficient way.

Answer

This will handle all of your cases, but it may not find EVERY duplicate, e.g. given (a, a', a'', a''', b) it will not show that (a''' overlaps a'). If you’re really interested in the primary supersets, then this code can be simplified

from netaddr.ip import IPNetwork
from collections import namedtuple

Network = namedtuple("Network", "name ip")

networks = {
    IPNetwork('10.1.0.0/24'): 'net2',
    IPNetwork('10.0.0.0/8'): 'net1',
    IPNetwork('10.0.0.0/16'): 'net3',
    IPNetwork('10.0.0.0/24'): 'net4',
    IPNetwork('192.168.0.0/16'): 'net5',
    IPNetwork('192.168.0.0/23'): 'net6',
    IPNetwork('192.168.1.0/24'): 'net7',
    IPNetwork('172.16.0.0/12'): 'net8'
}

print("original")
net = sorted([key for key in networks.keys()])
for pi in range(0, len(net)-1):
    for si in range(pi+1, len(net)):
        if net[si] in net[pi]:
            print(f'{net[si]} ({networks[net[si]]}) overlaps with '
                  f'{net[pi]} ({networks[net[pi]]})')

nets = sorted([Network(v, k) for k, v in networks.items()], key=lambda a: a.ip)

print()
print("faster")
aa = None
first = True
for a, b in zip(nets[0:-1], nets[1:]):
  if aa is None:
    aa = a
  if b.ip in aa.ip:
    print(f'{b.ip} ({b.name}) overlaps with {aa.ip} ({aa.name})')
    if not first and aa != a and b.ip in a.ip: 
      # it's already a subset of an earlier one...
      # only if you care about secondary overlaps
      print(f'{b.ip} ({b.name}) overlaps with {a.ip} ({a.name})')
    # aa = a
  elif b.ip in a.ip:
    print(f'{b.ip} ({b.name}) overlaps with {a.ip} ({a.name})')
    aa = a
  else:
    # print(f'! {b.ip} ({b.name}) overlaps with {aa.ip} ({aa.name})')
    aa = None
  first = False