# Randomly rewire edges while preserving DD.

from sys import argv, exit
from random import sample
from math import ceil
from copy import copy

gw_file_name = argv[1]
percent = float(argv[2])
gw_out_file_name = argv[3]

# Read alignment file
gw_file = open(gw_file_name)

# Ignore header lines
h1 = gw_file.readline()
h2 = gw_file.readline()
h3 = gw_file.readline()

# Read nodes
n_nodes = int(gw_file.readline().strip())
nodes = ["n/a"]
for i in range(n_nodes):
	node = gw_file.readline().strip().strip("{}|")
	nodes.append(node)

# Read edges
edge_set = set()
n_edges = int(gw_file.readline().strip())
for i in range(n_edges):
	tokens = tuple(gw_file.readline().strip().split())
	v1 = nodes[int(tokens[0])]
	v2 = nodes[int(tokens[1])]
	edge_set.add((v1, v2))

original = copy(edge_set)

# REWIRE
# How many times?
rewires = int(ceil(percent * n_edges / 2))
rewired = set()
print "Rewiring %d pairs" % rewires
for i in xrange(rewires):
    # Keep trying until valid pair of edges found
    while 1:
        e1, e2 = sample(edge_set, 2)
        v11 = e1[0]
        v12 = e1[1]
        v21 = e2[0]
        v22 = e2[1]
        # Invalid pair
        if (v11, v22) in edge_set or (v22, v11) in edge_set:
            continue
        if (v12, v21) in edge_set or (v21, v12) in edge_set:
            continue
        if (v11, v22) in rewired or (v22, v11) in rewired:
            continue
        if (v12, v21) in rewired or (v21, v12) in rewired:
            continue
        if (v11, v22) in original or (v22, v11) in original:
            continue
        if (v12, v21) in original or (v21, v12) in original:
            continue
        break
    edge_set.remove(e1)
    edge_set.remove(e2)
    rewired.add((v11, v22))
    rewired.add((v12, v21))
new_edge_set = edge_set.union(rewired)

# Write back
gw_out_file = open(gw_out_file_name, 'w')
gw_out_file.write(h1 + h2 + h3)
gw_out_file.write("%d\n" % n_nodes)

# Node set (unchanged)
for node in nodes[1:]:
    gw_out_file.write("|{%s}|\n" % node)

# Rewired edge set
gw_out_file.write("%d\n" % len(new_edge_set))
for e in new_edge_set:
    i = nodes.index(e[0])
    j = nodes.index(e[1])
    gw_out_file.write("%d %d 0 |{}|\n" % (i, j))

print len(original.intersection(new_edge_set))

gw_file.close()
gw_out_file.close()






















