芥子屋

什么是二分图

定义：设 G=(V, E) 是一个无向图，如果顶点 V 可分割为两个互不相交的子集｛U｝、｛V｝，并且图中的每条边 (i, j) 所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集 i∈ U，j∈ V，则称图 G 为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。

二分图（Bipartite Graph）是指图中的顶点可以划分到两个不相交的集合中，同一个集合中的顶点不相邻，即同一个集合中的两个顶点之间不存在边。如下图，我可以将左侧的蓝色和紫色构成的图转化为右图的二分图，集合 A 中全由紫色顶点构成，集合 B 中全由蓝色顶点构成，只存在蓝-紫（紫-蓝）边，同色顶点间不存在边。

所以二分图又可以等价于二色图（Two-colorable Graph），以下是一些二分图的常见示例，如星状图、网格图、齿轮图等。

Bipartiteness Check

批处理

那么如何检测一个图是否为二分图呢？在批处理情形下，即一个图的所有顶点和所有边的信息都已明确，我们借助于二色图的思想，可以通过染色法来判断一个图是否为二分图。算法可以通过 BFS 广度优先算法来实现，具体步骤如下：

1. 从任意一个顶点出发，将该顶点染成黑色。
2. 遍历该顶点的所有相邻顶点，将其染成白色。
3. 采用 BFS 依次遍历各个顶点的相邻顶点，将其染成与自身颜色相反的颜色。
4. 当出现已访问过的相邻顶点颜色与自己相同，则该图不是二分图。否则，该图为二分图。

前言

该文档是我在团队中负责集成测试模块时为团队成员编写的 API 接口文档，这次拿过来修改了一下，并已经将业务无关的代码剥离出来上传到 GitHub 上。主要是向大家展示一种流畅接口设计框架代码的模式。

所谓流畅接口，可以参考我之前翻译的 Martin Flower 的博客译文。简单来说，流畅接口被设计为可读的和流式的，使用起来几乎和自然语言一般流畅，并且配合 IDE 的智能提示，易于 API 使用者的理解和使用。譬如下面我编写的集成测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class InboundToOutboundExampleJobTest extends JobIntegrationTest {

    @Test
    public void should_send_ACTT_and_receive_trigger_event_from_kafka() {
        kafkaSuite.send(new ResourceFile("sample/send/pek/ACTT.xml"))
                .toTopic()
                .ofConfig("inbound_imf");

        SubjectEvent event = kafkaSuite
                .await().latestOne()
                .fromTopic()
                .ofConfig("trigger")
                .toJavaObject(SubjectEvent.class);

        assertThat(event.getEventName()).isEqualTo("FLOP_ACTT");
        assertThat(event.getGids().size()).isEqualTo(1);
        assertThat(event.getGids().get(0)).isEqualTo("PEK_80664162170310656");
    }
}

代码读起来非常明了，KafkaSuite 是我编写的 Kafka 集成测试套件，负责将 xml 文件发送至 Kafka 的一个 Topic 中，该 Topic 配置在配置文件中，对应着 inbound_imf 项。同时 KafkaSuite 监听另一个 Topic trigger 的最新一条消息并转换成 Java 对象，对结果进行验证（其间过程 xml 文件会被其他模块解析并经过一系列的业务处理）。

上述代码中，assertThat().isEqualTo() 就是断言框架 assertj 的 API，它是一个非常优秀的流畅接口的框架，建议大家阅读其源代码。我在编写 Kafka 集成测试框架时就借鉴了这种编码模式。

集成测试

代码目前完成了 Kafka 集成测试的发送和监听功能。我们的流处理框架采用的是 Flink，将任务分解为一个个 Job 独立运行，所以集成测试首先得启动 Job，并且加载包括 Kafka IP地址等相关配置。为此我编写了 JobIntegrationTest 类，并规定所有集成测试用例必须继承该类。此外，KafkaSuite 是负责 Kafka 集成测试的套件，封装了各种流畅接口 API。

JobIntegrationTest

所有的集成测试必需继承 JobIntegrationTest 类，该类提供 final 的 setUp() 方法和 tearDown() 方法。

声明

本教程也是由于本人平时工作学习有 Google 的需求，所以就自己搭了一个梯子，并记录了搭建的过程方便以后重搭。大家搭建后小规模使用就好了，这样网速较快且不容易被封。特此申明：严禁用于商业用途！

准备

• VPS 服务器，需要选择国外的，推荐 Vultr，速度不错、稳定且性价比高，按小时计费，能够随时开通和删除服务器。操作系统选择 CentOS 6，为了更换内核方便不宜选择版本过高的操作系统。
• MacOS 自带的 Terminal，或者 Windows 的 XShell。用于 ssh 连接远程服务器并执行命令。
• ShadowsocksR 客户端，简称 SSR，是 Shadowsocks 的增强版，在其基础上增加了一些数据混淆方式。SSR 下载地址：Mac 版，Windows 版。

部署SSR服务端

执行 ssh root@{IP} 连接上 VPS 服务器，并安装 SSR 服务端一件部署脚本

1
2
3

yum -y install wget

wget -N --no-check-certificate https://raw.githubusercontent.com/ToyoDAdoubi/doubi/master/ssr.sh && chmod +x ssr.sh && bash ssr.sh

等待下载完成后出现如下界面，按照提示一步步进行配置

依次会配置：

前言

代理模式（Proxy Pattern）是一种常见的设计模式，也是 GoF 提出的 23 种设计模式中的一种，属于结构型设计模式。它使用代理对象完成用户请求，屏蔽用户对真实对象的访问。代理模式用处很多，本文主要介绍如何使用代理模式实现延迟加载和面向切面编程，并着重介绍动态代理的几种实现方式。本文涉及到的示例代码以上传到 GitHub 上。

角色及职责

代理模式中的几个角色：

• Subject，接口，定义了代理类和被代理类对外暴露的方法。代理类和被代理类都需要实现该接口。
• RealSubject，真实对象（被代理类），真正实现功能的对象。
• Proxy，代理类，用来封装真实对象。

适用场景

代理模式通常用于解决以下几类问题：

• 需要控制对象的访问权限
• 需要扩展一个对象的功能

对此，代理模式使用 Proxy 封装真实对象，以达到控制真实对象的访问权限，并在此基础上提供额外功能。代理模式有以下几个典型的应用场景：

问题

图中有一个无向图，其中圈内数字代表一个地点，边线上的数字代表长度 Le（双向相同）。机场一辆小型VIP电动摆渡车在起点 A，要去 3 个贵宾厅（V1，V2，V3）接贵宾（每个贵宾厅限1个VIP），送到 3 个对应航班机位（S1，S2，S3），即 V1 至 S1，V2 至 S2，V3 至 S3。VIP 电动摆渡车同时最多装下 2 个 VIP。

要求：VIP 电动摆渡车该怎么走路径最短？这个最短路径的长度是多少？这里 A 是出发点，最后一个 VIP（不限次序）送达地为终点。为了简化问题，假设贵宾厅VIP已在贵宾厅等候上车，VIP 电动摆渡车在接送期间不用等待。

分析

看到最短路径，不难想到 Dijkstra 等最短路径算法，这些算法用于求出一个图（Graph）中任意两个顶点（Vertex）的最短距离。但是本文待求解的问题不止于此，而是包含起始点 A 在内的 7 个点（A、V1、V2、V3、S1、S2、S3），我们需要先规划路线使得摆渡车依次通过这 7 个点，再求出这些路线中的最短路线。

综上所诉，该问题被拆解为以下两步：
第一步，列出从 A 出发经由其余 6 个点的所有可能的路线。
第二步，对于给定的任意两个点，求出它们之间的最短路径（例如给定 A、V2 两个点，可得从 A 到 V2 的最短路径为 2 -> 6 -> 7）。
然后对于每条路线，计算每一段（即两个点之间）的最短路径即可得到整条路线的最短路径。

由此，可以看出本题涉及两个算法，即第一步中的排序算法，和第二步中的最短路径算法。

排序算法

我们需要对 V1、V2、V3、S1、S2、S3 六个点进行排序。当然为满足题目的要求，排序得出的路线必须满足以下几个条件：