Convert a graph in DIMACS format to its complement graph

to-complement-dimacs.py

#!/usr/bin/python3
#
# Convert a DIMACS graph to its complement graph.
#
# Usage:
#
#  to-complement.py < in-dimacs > out-dimacs

import sys

data = sys.stdin.readlines()

# first line is the problem description
first_line = data[0]
if first_line[0] != 'p':
    print('First line must start with "p".', file=sys.stderr)
    exit(1)

p, name, nv, ne = first_line.split()  # first line: p name num_of_vertices num_of_edges
nv = int(nv)
ne = int(ne)
print('{} {} {} {}'.format(p, name, nv, nv * (nv - 1) // 2 - ne))

edges = set()

for line in data[1:]:
    if line[0] == 'v':
        print(line.strip())
        continue

    if line[0] == 'e':
        _, v0, v1 = line.split()
        edges.add(frozenset({int(v0), int(v1)}))

for v0 in range(1, nv + 1):
    for v1 in range(v0 + 1, nv + 1):
        if frozenset({v0, v1}) not in edges:
            print('e {} {}'.format(v0, v1))