second shortest path

ViewController.mm

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

#import "ViewController.h"

#include <queue>
#include <vector>
#include <memory>
#define INF 9999
using namespace::std;

typedef struct {int to, cost; } Edge;
typedef struct pair<int, int> P; // shortest cost 1st: cost, 2d: vertex

class SecondShortestPathSolver {
public:
    void solve(vector<Edge>[], int);
private:
    void notify(NSArray*, NSArray*);
};
void SecondShortestPathSolver::solve(vector<Edge> graph[], int size) {
    int prev[2][size], dist[2][size];
    
    for (int i=0; i<2; i++)
        for (int j=0; j<size; j++) {
            prev[i][j] = -1;
            dist[i][j] = INF;
    }
    
    int start = 0;
    dist[0][start] = 0;

    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(start, 0));
    
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second, d = p.first;
        if (dist[1][v] < d) continue;
        for (auto &e : graph[v]) {
            int next = d + e.cost;
            if (dist[0][e.to] > next) {
                swap(dist[0][e.to], next);
                que.push(P(dist[0][e.to], e.to));
                prev[0][e.to] = v;
            }
            if (dist[1][e.to] > next && dist[0][e.to] < next) {
                dist[1][e.to] = next;
                que.push(P(dist[1][e.to], e.to));
                prev[1][e.to] = v;
            }
        }
    }
    
    NSMutableArray *f = [NSMutableArray array];
    NSMutableArray *s = [NSMutableArray array];
    for (int i=0; i<size; i++) {
        [f addObject:@(prev[0][i])];
        [s addObject:(prev[1][i] != -1) ? @(prev[1][i]) : @(prev[0][i])];
    }
    notify(f, s);
};
void SecondShortestPathSolver::notify(NSArray *firstPath, NSArray *secondPath) {
    [[NSNotificationCenter defaultCenter] postNotificationName:@"my message" object:@[firstPath, secondPath]];
}

@interface ViewController () {
    vector<Edge> graph[8];
}
@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    self.view.backgroundColor = [self color:0];
    
    graph[0] = {{.to=2, .cost=5}, {.to=1, .cost=4}};
    graph[1] = {{.to=3, .cost=2}};
    graph[2] = {{.to=3, .cost=4}, {.to=5, .cost=5}};
    graph[3] = {{.to=4, .cost=3}, {.to=6, .cost=4}};
    graph[4] = {{.to=7, .cost=8}};
    graph[5] = {{.to=6, .cost=2}};
    graph[6] = {{.to=7, .cost=3}};
    graph[7] = {};
    
    CGPoint o = CGPointMake(CGRectGetMidX(self.view.bounds), CGRectGetMidY(self.view.bounds));
    CGPoint pts[] = {
        CGPointMake(o.x - 130, o.y - 200),
        CGPointMake(o.x, o.y - 200),
        CGPointMake(o.x - 130, o.y),
        CGPointMake(o.x, o.y),
        CGPointMake(o.x + 130, o.y),
        CGPointMake(o.x - 130, o.y + 200),
        CGPointMake(o.x, o.y + 200),
        CGPointMake(o.x + 130, o.y + 200)
    };
    for (int i=0; i<8; i++) {
        UILabel *vertex = [[UILabel alloc] initWithFrame:CGRectMake(0, 0, 30, 30)];
        vertex.tag = 100 + i;
        vertex.backgroundColor = [self color:1];
        vertex.center = pts[i];
        vertex.text = i==0 ? @"S" : i==7 ? @"G" : [NSString stringWithFormat:@"%d", i];
        vertex.textAlignment = NSTextAlignmentCenter;
        vertex.textColor = [self color:0];
        vertex.layer.zPosition = 10;
        [self.view addSubview:vertex];
        
        for (auto e : graph[i]) {
            UIBezierPath *path = [UIBezierPath bezierPath];
            [path moveToPoint:vertex.center];
            [path addLineToPoint:pts[e.to]];
            
            CAShapeLayer *line = [CAShapeLayer layer];
            line.path = path.CGPath;
            line.lineWidth = 8;
            line.fillColor = [UIColor clearColor].CGColor;
            line.strokeColor = [self color:3].CGColor;
            [self.view.layer addSublayer:line];
            
            UILabel *cost = [[UILabel alloc] init];
            cost.text = [NSString stringWithFormat:@"%d", e.cost];
            cost.textColor = [self color:1];
            [cost sizeToFit];
            cost.center = CGPointMake((vertex.center.x + pts[e.to].x) * 0.5, (vertex.center.y + pts[e.to].y) * 0.5);
            [self.view addSubview:cost];
        }
    }
    
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(receiveMessage:) name:@"my message" object:nil];
}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    shared_ptr<SecondShortestPathSolver> cppClass(new SecondShortestPathSolver());
    cppClass->solve(graph, 8);
}

- (void)receiveMessage:(NSNotification *)note {
    NSArray *firstPath = note.object[0];
    NSArray *secondPath = note.object[1];
    
    [self drawLine:firstPath color:[self color:4] w:8];
    
    dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(0 * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
        [self drawLine:secondPath color:[self color:2] w:4];
    });
}

- (void)drawLine:(NSArray *)pathArr color:(UIColor *)color w:(int)w{
    
    int i = [pathArr.lastObject intValue];
    int last = 7;
    int count = 3;
    while (i >= 0) {
        UIView *v = [self.view viewWithTag:i + 100];
        UIView *v0 = [self.view viewWithTag:last + 100];
        UIBezierPath *path = [UIBezierPath bezierPath];
        [path moveToPoint:v.center];
        [path addLineToPoint:v0.center];
        
        CAShapeLayer *line = [CAShapeLayer layer];
        line.path = path.CGPath;
        line.lineWidth = w;
        line.fillColor = [UIColor clearColor].CGColor;
        line.strokeColor = color.CGColor;
        line.strokeEnd =0;
        [self.view.layer addSublayer:line];
        last = i;
        i = [[pathArr objectAtIndex:i] intValue];
        
        CABasicAnimation *pathAnimation = [CABasicAnimation animationWithKeyPath:@"strokeEnd"];
        pathAnimation.duration = 2.0;
        pathAnimation.fromValue = [NSNumber numberWithFloat:0.0f];
        pathAnimation.toValue = [NSNumber numberWithFloat:1.0f];
        
        int64_t delay = (int64_t)(2.0 * count * NSEC_PER_SEC);
        
        if (w == 4) {
            delay += (int64_t)(5.0 * NSEC_PER_SEC);
        }
        
        dispatch_after(dispatch_time(DISPATCH_TIME_NOW, delay), dispatch_get_main_queue(), ^{
            line.strokeEnd = 2.0;
            [line addAnimation:pathAnimation forKey:nil];
        });

        
        count--;
    }
}

#define ColorHex(rgb) [UIColor colorWithRed:((rgb & 0xFF0000) >> 16)/255.0 green:((rgb & 0xFF00) >> 8)/255.0 blue:(rgb & 0xFF)/255.0 alpha:1.0]
- (UIColor *)color:(int)i {
    if (i > 4) return nil;
    int code[] = {0xB8ECD7, 0x083643, 0xB1E001, 0xCEF09D, 0x476C5E};
    return ColorHex(code[i]);
}

@end