"六度空间"的应用——找出两个陌生人之间的关系(二)

叁歲伎倆 2021-10-26 12:20 245阅读 0赞

# 终于"完工" #

哎, 熬了好几个夜, 掉了好多根头发, 终于接近完工, 如果真的要拿给别人用还需要修补很多东西. 先发几张程序运行的图片吧:) 第一张是找出两人关系, 我试了很多人, 几乎都只需要通过一个人就能找到另一个人, 第二张是寻找XML文件中某个人有哪些好友.

![2011011721403045.jpg][]![2011011721405551.jpg][]

# 存储内容的改进 #

在写上篇博客的时候程序一直在运行(在保存人和人之间的完整对应关系), 我估算还需要好几个小时才能停下来, 所存储的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个人...循环下去, 这个对产品的推广是十分有好处的. 当下很多东西正是基于"六度空间"的这个理论, 用户群变得超级庞大.

转载于:https://www.cnblogs.com/technology/archive/2011/01/17/1937831.html

[2011011721403045.jpg]: https://pic002.cnblogs.com/images/2011/70278/2011011721403045.jpg
[2011011721405551.jpg]: /images/20211026/9b157ce7780743698729d938d05c4a90.png