[转载]”六度空间”的应用——找出两个陌生人之间的关系(二) – Create Chen – 博客园.
终于”完工”
哎, 熬了好几个夜, 掉了好多根头发, 终于接近完工, 如果真的要拿给别人用还需要修补很多东西. 先发几张程序运行的图片吧:) 第一张是找出两人关系, 我试了很多人, 几乎都只需要通过一个人就能找到另一个人, 第二张是寻找XML文件中某个人有哪些好友.
存储内容的改进
在写上篇博客的时候程序一直在运行(在保存人和人之间的完整对应关系), 我估算还需要好几个小时才能停下来, 所存储的XML文件也会大的惊人, 估算达到1GB以上, 其实运算之前这个时候的XML中已经包含了所有的人, 只不过暂时是一种类似”有向图”(A是B的好友, B不是A的好友)的关系, 现在运算的也只是把有向图的关系完全拓展开, 变成无向图(A是B的好友, B也是A的好友而已). 在发现完整关系的情况下, 存储所需要的空间如此之大时, 我放弃了这种方法. 在下载完所有人的头像照片(4万多张)后, 我把XML中每个节点的school和faceUri删除掉了, 这样存储人与人的关系只用了15.8MB.
现在的存储结构如下:
<? xml version="1.0"?> <Relations> <Person id="" name=""> <Friend id="" name=""/> <Friend id="" name=""/> ........ </Person> <Person id="" name=""> <Friend id="" name=""/> <Friend id="" name=""/> ........ </Person> </Relations>
从这个XML中通过一些XML的操作方法可以就可以得到很多信息了.
RelationOperate类
1. 每次定义一个RelationOperate类, 需要传进一个XML文件地址, 以对它进行操作
private XmlDocument xmlDoc = new XmlDocument(); public RelationOperate(string xmlDocPath) { xmlDoc.Load(xmlDocPath); }
2. 通过一个id找到他的好友列表
/// <summary> /// 获取一个id的好友 /// </summary> /// <param name="id">要查找的id</param> /// <returns>该id的好友id列表</returns> public List<string> getFriend(string id) { List<string> friendList = new List<string>(); var PersonList = xmlDoc.SelectNodes("//Person"); //所有的Person节点 foreach (XmlNode xmlNode in PersonList) //若果Person节点已经包含了该id的用户 if (xmlNode.Attributes["id"].InnerText == id) { //则增加这个Person节点的每一个子节点到friendList中 //因为他的每一个子节点都是他的好友 foreach (XmlNode node in xmlNode.ChildNodes) friendList.Add(node.Attributes["id"].InnerText); return friendList; } //上面的条件不满足时, 就查找哪些Person的子节点(朋友)里边包含这个id foreach (XmlNode xmlNode in PersonList) foreach (XmlNode node in xmlNode.ChildNodes) { if (node.Attributes["id"].InnerText == id) { friendList.Add(xmlNode.Attributes["id"].InnerText); break; } } return friendList; }
3. 获取一个id的姓名
public string getName(string id) { var PersonList = xmlDoc.SelectNodes("//Person"); //所有的Person节点 foreach (XmlNode xmlNode in PersonList) //若果Person节点已经包含了该id的用户 if (xmlNode.Attributes["id"].InnerText == id) { return xmlNode.Attributes["name"].InnerText; } //上面的条件不满足时, 就查找哪些Person的子节点(朋友)里边包含这个id string name = ""; foreach (XmlNode xmlNode in PersonList) foreach (XmlNode node in xmlNode.ChildNodes) { if (node.Attributes["id"].InnerText == id) { name = node.Attributes["name"].InnerText; return name; } } return name; }
4. 获取一个姓名的id号码
public string getID(string name) { var PersonList = xmlDoc.SelectNodes("//Person"); //所有的Person节点 foreach (XmlNode xmlNode in PersonList) //若果Person节点已经包含了该id的用户 if (xmlNode.Attributes["name"].InnerText.Contains(name)) { return xmlNode.Attributes["id"].InnerText; } //上面的条件不满足时, 就查找哪些Person的子节点(朋友)里边包含这个id foreach (XmlNode xmlNode in PersonList) foreach (XmlNode node in xmlNode.ChildNodes) { if (node.Attributes["name"].InnerText.Contains(name)) { string id = node.Attributes["id"].InnerText; return id; } } return null; }
5. 获取两个id之间的关系(广度优先)
public List<string> getRelation(string A, string B) { //A直接认识B 0层关系 var Afriend = getFriend(A); List<string> relation = new List<string>(); foreach (string id in Afriend) if (id == B) { relation.Add(A); relation.Add(B); return relation; } //A的好友是B的好友 1层关系 var Bfriend = getFriend(B); foreach (string friendA in Afriend) foreach (string friendB in Bfriend) { //A的某个朋友也是B的某个朋友 if (friendA == friendB) { relation.Add(A); relation.Add(friendA); relation.Add(B); return relation; } } //A的好友的好友是B的好友 2层关系 List<FriendFriend> AFriendFriend = new List<FriendFriend>(); foreach (string friend in Afriend) { if (friend != B) //涉及两层关系时, A的Friend不直接是B { FriendFriend ff = new FriendFriend(); ff.parent = friend; ff.friend = getFriend(friend); AFriendFriend.Add(ff); } } foreach (FriendFriend ff in AFriendFriend) { foreach (string friend in ff.friend) //涉及两层关系时,A的Friend的Friend不直接是B if (friend != A) { foreach (string friendB in Bfriend) { //B的朋友也不直接是A, B的朋友也不直接是A的朋友 if ((friendB != A) && (friendB != ff.parent)) { if (friend == friendB) { relation.Add(A); relation.Add(ff.parent); relation.Add(friend); relation.Add(B); break; } return relation; } } } } //涉及3层关系 A的好友的好友C 是 B的好友的好友 //C一定是那个种子节点 //还没写3层关系 return relation; }
总结
结合上边的类操作已经保存好了的XML, 可以用WPF或者其它做出一些找关系的程序, 在自己的网站上加上这么一个功能, 很绚丽的哦. 另外我还发现应该用手机人人网的协议接口, 那个页面下载的内容精简, 没有很复杂的CSS, JavaScript等等, 以后真正要做出应用的话应该研究手机版的协议. 本文也只是提供一个思路, 可以做出一个这个东西. 另外真正了解”六度空间”的威力也是很好的, 如果一个产品被20个人看到, 每个人推荐给了另外的20个人…循环下去, 这个对产品的推广是十分有好处的. 当下很多东西正是基于”六度空间”的这个理论, 用户群变得超级庞大.