State-flipping algorithm for max cut.

maxcut.py

#!/usr/bin/env python
# encoding: utf-8
import networkx as nx
from time import time
import random
"""
    Lab 1 EDAN55
    Max cut: State-flipping algorithm
    https://github.com/thorehusfeldt/Maxcut-Lab
"""
FNAME = 'data/pw09_100.9.txt'

def read_input(file_name):
    f = open(FNAME, 'r')
    first_row = True
    graph = nx.Graph()
    for row in f:
        if not first_row:
            rs = row.split()
            graph.add_node(rs[0])
            graph.add_node(rs[1])
            graph.add_edge(rs[0], rs[1], weight=int(rs[2]))
        else:
            first_row = False
    return graph

def R(graph):
    A = []
    B = []
    for node in graph.nodes():
        if random.choice((True, False)):
            A.append(node)
        else:
            B.append(node)
    return A, B

def cut_weight(graph, A, B):
    total = 0
    # for edges in graph.edges_iter():
    #   if (edge[0] in A and edge[1] in B) or (edge[0] in B and edge[1] in A):
    #       total += 


    for vertice in A:
        for neighboor in graph[vertice]:
            if neighboor in B:
                total += graph[vertice][neighboor]['weight']
    return total

def main():
    graph = read_input(FNAME)
    A, B = R(graph)
    result = cut_weight(graph, A, B)

    return result

if __name__ == "__main__":
    old_result = 0
    old_time = time()
    while True:
        result = main()
        if result > old_result:
            t = time()
            print t - old_time
            print result
            old_time = t
            old_result = result

first_row onödig?

next(f)
for row in f:

borde funka?