四角と四角の２部グラフを表示するiPhoneアプリ(C++)のサンプルコードを描いてみます。
#import “ViewController.h”
#include <vector>
#include <memory>
using namespace std;
class GraphChecker {
public:
void solve(vector<int>[], int);
void notify(int, int);
private:
int color[100];
bool dfs(vector<int>[], int, int);
};
bool GraphChecker::dfs(vector<int> graph[], int n, int c) {
color[n] = c;
notify(n, c);
for (auto &adj : graph[n]) {
if (color[adj] == c) return false;
if (color[adj] == 0 && !dfs(graph, adj, -c)) {
return false;
}
}
return true;
};
void GraphChecker::solve(vector<int> graph[], int size) { // Adjacency list
for (int i=0; i<size; i++) {
if (color[i] == 0) {
if(!dfs(graph, i, 1)) {
NSLog(@”false!”);
return;
}
}
}
};
void GraphChecker::notify(int n, int color) {
[[NSNotificationCenter defaultCenter] postNotificationName:@”my message” object:@[@(n), color > 0 ? [UIColor redColor] : [UIColor blueColor]]];
}
@interface ViewController ()
@property (nonatomic) int counter;
@end
@implementation ViewController
vector<int> g[] = {
{1,3,4},{0,2,5},{1,3,6},{2,0,7},
{0,5,7},{1,4,6},{2,5,7},{3,6,4}
};
– (void)viewDidLoad {
[super viewDidLoad];
self.view.backgroundColor = [UIColor blackColor];
for (int i=0; i<8; i++) {
UIView *node = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 20, 20)];
node.tag = i + 1;
node.backgroundColor = [UIColor clearColor];
node.layer.cornerRadius = 10;
node.layer.borderColor = [UIColor whiteColor].CGColor;
node.layer.borderWidth = 1.5;
node.layer.zPosition = 10;
node.center = [self pointAt:i];
[self.view addSubview:node];
for (int j=0; j<3; j++) {
int a = g[i][j];
UIBezierPath *path = [UIBezierPath bezierPath];
[path moveToPoint:node.center];
[path addLineToPoint:[self pointAt:a]];
CAShapeLayer *l = [CAShapeLayer layer];
l.path = path.CGPath;
l.strokeColor = [UIColor whiteColor].CGColor;
l.lineWidth = 1.5;
l.fillColor = [UIColor clearColor].CGColor;
[self.view.layer addSublayer:l];
}
}
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(recieve:) name:@”my message” object:nil];
}
– (CGPoint)pointAt:(int)i {
float r = (i<4) ? 120 : 40;
float x = r * cos(i * M_PI * 0.5) + CGRectGetMidX(self.view.bounds);
float y = r * sin(i * M_PI * 0.5) + CGRectGetMidY(self.view.bounds);
return CGPointMake(x, y);
}
– (void)recieve:(NSNotification *)note {
int n = [note.object[0] intValue];
UIColor *c = note.object[1];
UIView *node = [self.view viewWithTag:n + 1];
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(0.5 * self.counter * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
node.backgroundColor = c;
});
self.counter++;
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
shared_ptr<GraphChecker> cppClass(new GraphChecker());
cppClass->solve(g, 8);
}
@end