MapReduce-寻找三角形
在图中,如何判断三角形?三角形在很多场景都有应用,比如社交网络中确定人和人之间的关系。
那么如果通过代码逻辑来实现呢?在数据结构之图中,区分三联体(有一端没有关联关系的三角形)和三角形是关键;两者之间的差别在于边的"度",如果>=2,则可以断定点和边的关系是三角形。为什么度要>=2呢?因为如果一条边是三角形的边,冲要件是:
1)这条边是存在的(三联体里面允许一条边不存在);
2)这条边至少有一个节点和他连接;
所以度>=2的涵义就是满足了这两个条件;
那么算法中一般怎么实现?
基本的思路是当前边角的关系以数字集合的方式传递到map中,map1的处理就是讲传入的无向的两点关系转化为有向的关系,比如传入1-2,那么经过map处理就会变成两条记录(1,2),(2,1),这样处理的目的是为了reduce1阶段的处理能够形成各个点都和哪些点有关联关系;这些点也解决了上述的第一个问题:边的存在性;
map1阶段的输出会形成点和哪些点有关联关系,例如:
1, [2] # 点1和点2以及点3有关联关系
2, [1,3,4,5]
reduce1阶段会继续根据上述的输入数据进行处理,形成边和点的关系:
[1], [2] → [(1,2), (-)]
[2], [1,3,4,5] → [(2,1), (-)]
[(2,3), (-)]
...
[(1,3), (2)]
[(1,4), (2)]
第一个阶段即使要形成这样的数据,能够确定点和那些点有关联关系;注意reduce1的输出中,但凡是标记为"-"的代表是边的存在性,而且key值一定存在于map1过程的边对应关系中;
下面是第二个阶段,第二个阶段主要是根据点的关系来获取边和点的关系;根据我们上面讲到的三角形的充要条件是度>=2,所以在第二个阶段map2是恒等处理,在reduce2中会根据上面的数据,对于key进行groupby,整理出各条边的关联的点,如果和某条边关联的点>=2,则说明三角形存在,可以获取三角形:
(2,3), [-, 4] → 可以推测出有三角形2,3,4(其中"-"代表点2到点3的连线是存在的,4代表有一个点和线段2-3都关联,于是推测出这是一个三角形)
最后一个步骤是去重,reduce2中获取的三角形是重复的(每个都有两个),于是需要点位置进行排序,删除重复的三角形。
最新文章
- Python Day20
- django一些操作命令
- [vijos P1040] 高精度乘法
- python之购物车的编写(熬夜撸代码中。。。)
- java中使用二重循环打印图形
- C/C++:[2]enum-枚举量声明、定义和使用
- Uxf框架引入Rest控制器特性
- svn cleanup failed–previous operation has not finished 解决方法
- 微软职位内部推荐-SDE
- nutch 采集效率--设置采集间隔
- Jquery 动态生成表单 并将表单数据 批量通过Ajax插入到数据库
- perl HTML::TreeBuilder::XPath
- nginx---Beginner's Guide
- NYOJ 5 Binary String Matching
- MySql_5-7安装教程
- Cisco Packet Tracer 6.0 实验笔记
- JavaScript 闭包小记
- 属性复制方法,当属性名字不一致时候可以传入匹配的Map
- mysql对身份证号码进行脱敏处理
- video maker &; video tutorials