negative cycle check

ViewController.mm

//
//  ViewController.mm
//  NegativeCycleCheck
//
//  Created by MizushimaYusuke on 8/20/15.
//  Copyright (c) 2015 MizushimaYusuke. All rights reserved.
//

#import "ViewController.h"

typedef struct {int u, v, cost;} Edge;
#include <vector>
#include <memory>
using namespace std;
class NegativeCycleChecker {
public:
    bool check(vector<Edge> es, int v) {
        int d[v];
        fill(d, d + v, 0);
        
        for (int i=0; i<v; i++) {
            for (auto &e : es) {
                if (d[e.v] > d[e.u] + e.cost) {
                    d[e.v] = d[e.u] + e.cost;
                    if (i == v - 1) return true;
                }
            }
        }
        return false;
    }
};

@interface ViewController () {
    vector<CGPoint> v1, v2;
    vector<Edge> e1, e2;
}
@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    self.view.backgroundColor = [UIColor darkGrayColor];
    
    UILabel *title = [[UILabel alloc] init];
    title.font = [UIFont systemFontOfSize:30];
    title.textColor = [UIColor whiteColor];
    title.text = @"negative cycle?";
    [title sizeToFit];
    title.center = CGPointMake(CGRectGetMidX(self.view.bounds), 30);
    [self.view addSubview:title];
    
    
    v1 = {
        CGPointMake(50, 50), CGPointMake(100, 100), CGPointMake(250, 100),
        CGPointMake(50, 150), CGPointMake(100, 200), CGPointMake(250, 250)
    };
    e1 = {
        {1,2,1},{3,1,6},{2,3,2},
        {1,4,3},{4,5,-2},{5,6,8}};
    [self createGraph:v1 edge:e1];
    
    
    v2 = {
        CGPointMake(50, 50), CGPointMake(100, 100), CGPointMake(250, 100),
        CGPointMake(50, 150), CGPointMake(100, 200), CGPointMake(250, 250)
    };
    e2 = {
        {1,2,1},{3,1,-6},{2,3,2},
        {1,4,3},{4,5,2},{5,6,8}};
    UIView *g2 = [self createGraph:v2 edge:e2];
    g2.center = CGPointMake(g2.center.x + CGRectGetMidX(self.view.bounds), g2.center.y);

}

- (UIView *)createGraph:(vector<CGPoint>)vertex edge:(vector<Edge>)edge {

    float w = CGRectGetMidX(self.view.bounds) * 0.9;
    
    UIView *g1 = [[UIView alloc] initWithFrame:CGRectMake(0, 0, w, w)];
    g1.center = CGPointMake(CGRectGetMaxX(self.view.bounds) / 4.0, w * 0.7);
    g1.layer.borderWidth = 1;
    g1.layer.borderColor = [UIColor whiteColor].CGColor;
    [self.view addSubview:g1];
    
    for (int i=0; i < vertex.size(); i++) {
        UIView *v = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 20, 20)];
        v.tag = i + 1;
        v.backgroundColor = [UIColor lightGrayColor];
        v.center = vertex[i];
        v.layer.zPosition = 10;
        [g1 addSubview:v];
    }
    
    for (auto &e : edge) {
        UIView *u = [self.view viewWithTag:e.u];
        UIView *v = [self.view viewWithTag:e.v];
        
        UIBezierPath *path = [UIBezierPath bezierPath];
        [path moveToPoint:u.center];
        [path addLineToPoint:v.center];
        CAShapeLayer *l = [CAShapeLayer layer];
        l.path = path.CGPath;
        l.fillColor = [UIColor clearColor].CGColor;
        l.strokeColor = [UIColor whiteColor].CGColor;
        [g1.layer addSublayer:l];
        
        
        float dx = v.center.x - u.center.x;
        float dy = v.center.y - u.center.y;
        CGPoint ap = CGPointMake(u.center.x + dx * 0.75, u.center.y + dy * 0.75);
        UILabel *arrow = [[UILabel alloc] init];
        arrow.font = [UIFont boldSystemFontOfSize:20];
        arrow.text = @">";
        arrow.textColor = [UIColor whiteColor];
        [arrow sizeToFit];
        arrow.center = ap;
        arrow.transform = CGAffineTransformRotate(arrow.transform, atan2(dy, dx));
        [g1 addSubview:arrow];
        
        
        UILabel *cost = [[UILabel alloc] init];
        cost.text = [NSString stringWithFormat:@"%d", e.cost];
        cost.font = [UIFont boldSystemFontOfSize:20];
        cost.textColor = [UIColor yellowColor];
        [cost sizeToFit];
        cost.center = CGPointMake((u.center.x + v.center.x) * 0.5, (u.center.y + v.center.y) * 0.5);
        [g1 addSubview:cost];
    }
    
    UIButton *btn = [UIButton buttonWithType:UIButtonTypeSystem];
    btn.titleLabel.font = [UIFont boldSystemFontOfSize:20];
    [btn setTitleColor:[UIColor whiteColor] forState:UIControlStateNormal];
    [btn setTitle:@"check" forState:UIControlStateNormal];
    [btn sizeToFit];
    btn.center = CGPointMake(w/2.0, w * 0.90);
    [g1 addSubview:btn];
    
    [btn addTarget:self action:@selector(check:) forControlEvents:UIControlEventTouchUpInside];
    
    return g1;
}

- (void)check:(UIButton *)btn {
    
    shared_ptr<NegativeCycleChecker> cppClass(new NegativeCycleChecker());
    
    CGPoint p;
    bool isNegativeCycle = false;
    
    if (btn.superview.center.x < CGRectGetMidX(self.view.bounds)) {
        p = btn.superview.center;
        isNegativeCycle = cppClass->check(e1, (int)v1.size());
    } else {
        p = btn.superview.center;
        isNegativeCycle = cppClass->check(e2, (int)v2.size());
    }
    
    UILabel *res = [[UILabel alloc] init];
    res.text = isNegativeCycle ? @"TRUE" : @"FALSE";
    res.textColor = [UIColor orangeColor];
    res.font = [UIFont boldSystemFontOfSize:100];
    [res sizeToFit];
    res.center = p;
    [self.view addSubview:res];
}

@end