Consolidate IPs into ranges in python

Question

Assume I have a list of IP ranges (last term only) that may or may not overlap:

('1.1.1.1-7', '2.2.2.2-10', '3.3.3.3-3.3.3.3', '1.1.1.4-25', '2.2.2.4-6')

I'm looking for a way to identify any overlapping ranges and consolidate them into single ranges.

('1.1.1.1-25', '2.2.2.2-10', '3.3.3.3-3')

Current thought for algorithm is to expand all ranges into a list of all IPs, eliminate duplicates, sort, and consolidate any consecutive IPs.

Any more python-esque algorithm suggestions?

Answer 1

Here is my version, as a module. My algorithm is identical to the one lunixbochs mentions in his answer, and the conversion from range string to integers and back is nicely modularized.

import socket, struct

def ip2long(ip):
    packed = socket.inet_aton(ip)
    return struct.unpack("!L", packed)[0]

def long2ip(n):
    unpacked = struct.pack('!L', n)
    return socket.inet_ntoa(unpacked)

def expandrange(rng):
    # expand '1.1.1.1-7' to ['1.1.1.1', '1.1.1.7']
    start, end = [ip.split('.') for ip in rng.split('-')]
    return map('.'.join, (start, start[:len(start) - len(end)] + end))

def compressrange((start, end)):
    # compress ['1.1.1.1', '1.1.1.7'] to '1.1.1.1-7'
    start, end = start.split('.'), end.split('.')
    return '-'.join(map('.'.join,
          (start, end[next((i for i in range(4) if start[i] != end[i]), 3):])))

def strings_to_ints(ranges):
    # turn range strings into list of lists of ints
    return [map(ip2long, rng) for rng in map(expandrange, ranges)]

def ints_to_strings(ranges):
    # turn lists of lists of ints into range strings
    return [compressrange(map(long2ip, rng)) for rng in ranges]

def consolodate(ranges):
    # join overlapping ranges in a sorted iterable
    iranges = iter(ranges)
    startmin, startmax = next(iranges)
    for endmin, endmax in iranges:
        # leave out the '+ 1' if you want to join overlapping ranges
        # but not consecutive ranges.
        if endmin <= (startmax + 1):
            startmax = max(startmax, endmax)
        else:
            yield startmin, startmax
            startmin, startmax = endmin, endmax
    yield startmin, startmax

def convert_consolodate(ranges):
    # convert a list of possibly overlapping ip range strings
    # to a sorted, consolodated list of non-overlapping ip range strings
    return list(ints_to_strings(consolodate(sorted(strings_to_ints(ranges)))))

if __name__ == '__main__':
    ranges = ('1.1.1.1-7',
              '2.2.2.2-10',
              '3.3.3.3-3.3.3.3',
              '1.1.1.4-25',
              '2.2.2.4-6')
    print convert_consolodate(ranges)
    # prints ['1.1.1.1-25', '2.2.2.2-10', '3.3.3.3-3']

Answer 2

Convert your ranges into pairs of numbers. These functions will convert individual IPs to and from integer values.

def ip2long(ip):
    packed = socket.inet_aton(ip)
    return struct.unpack("!L", packed)[0]

def long2ip(n):
    unpacked = struct.pack('!L', n)
    return socket.inet_ntoa(unpacked)

Now you can sort/merge the edges of each range as numbers, then convert back to IPs to get a nice representation. This question about merging time ranges has a nice algorithm.

---

1. Parse your strings of 1.1.1.1-1.1.1.2 and 1.1.1.1-2 into a pair of numbers. For the latter format, you could do:

   x = '1.1.1.1-2'
   first, add = x.split('-')
   second = first.rsplit('.', 1)[0] + '.' + add
   pair = ip2long(first), ip2long(second)
   

2. Merge the overlapping ranges using simple number comparisons.

3. Convert back to string representation (still assumes latter format):

   first, second = pair
   first = long2ip(first) + '-' + long2ip(second).rsplit('.', 1)[1]