无权图人员推荐系统Java实现与建模解析

本文详细介绍了如何利用无权图数据结构构建一个人员推荐系统。通过将每个人视为图中的节点，并基于共享社区、学校或雇主等属性定义“密切联系”为节点间的边，我们能有效建模人际关系。文章涵盖了从文件读取、数据存储、图的构建（包括优化策略）、邻接列表表示，到最终结合隐私设置生成推荐的完整过程，旨在提供一个清晰、专业的实现指南。

1. 理解问题与图数据结构的适用性

在构建一个基于人员关系的推荐系统时，核心任务是识别个体之间的关联性，并基于这些关联提供建议。例如，一个“密切联系人”的定义可能是共享同一社区、学校或雇主的人。同时，系统还需要尊重用户的隐私设置，不对请求隐私的用户发送推荐。

这种场景非常适合使用图数据结构来建模。图由节点（Vertices）和边（Edges）组成，其中：

• 节点：可以代表人系统中的每个个体（人）。
• 边：可以代表个体之间的某种关系，例如“密切联系”。由于本系统只关注是否存在联系，而不关注联系的强度，因此可以构建一个无权图。

通过将问题抽象为图模型，我们可以利用图论的算法来高效地发现关系、进行遍历，并最终生成推荐。

2. 数据加载与初始存储

在构建图之前，首先需要从文件中读取人员和活动数据，并将其存储在内存中以便后续处理。原始的代码片段展示了文件读取的逻辑，但缺少将读取到的Person和Activities对象实际存储起来的步骤。这是构建任何复杂数据结构（如图）的基础。

以下是修正后的数据读取和存储逻辑，我们使用ArrayList来存储Person和Activities对象：

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 假设 Person 和 Activities 类已定义如下
// 为了教程完整性，这里提供简化版本
class Person {
    private String firstname;
    private String lastname;
    private String community;
    private String school;
    private String employer;
    private String privacy; // "Y" for private, "N" for public

    // 构造函数、getter和setter省略，但应包含所有字段
    public Person(String firstname, String lastname, String community, String school, String employer, String privacy) {
        this.firstname = firstname;
        this.lastname = lastname;
        this.community = community;
        this.school = school;
        this.employer = employer;
        this.privacy = privacy;
    }

    public String getFirstname() { return firstname; }
    public String getLastname() { return lastname; }
    public String getCommunity() { return community; }
    public String getSchool() { return school; }
    public String getEmployer() { return employer; }
    public String getPrivacy() { return privacy; }

    // 方便调试的toString方法
    @Override
    public String toString() {
        return firstname + " " + lastname + " (Community: " + community + ", School: " + school + ", Employer: " + employer + ", Privacy: " + privacy + ")";
    }

    // 重写equals和hashCode方法，以便在集合中正确比较Person对象
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return firstname.equals(person.firstname) &&
               lastname.equals(person.lastname); // 假设名字组合唯一标识一个人
    }

    @Override
    public int hashCode() {
        return java.util.Objects.hash(firstname, lastname);
    }
}

class Activities {
    private String firstname;
    private String lastname;
    private String activity;

    public Activities(String firstname, String lastname, String activity) {
        this.firstname = firstname;
        this.lastname = lastname;
        this.activity = activity;
    }

    public String getFirstname() { return firstname; }
    public String getLastname() { return lastname; }
    public String getActivity() { return activity; }

    @Override
    public String toString() {
        return firstname + " " + lastname + " -> " + activity;
    }
}

public class InfoReader {

    // 声明两个ArrayList来存储读取到的数据
    private List persons = new ArrayList<>();
    private List activities = new ArrayList<>();

    public void readInfo() {
        // 读取人员数据
        try {
            // 请根据实际情况修改文件路径
            String fileLocation = System.getProperty("user.home") + File.separator + "Downloads" + File.separator + "SamplefilePersons2022Oct31text.csv";
            File personListFile = new File(fileLocation);
            Scanner personScanner = new Scanner(personListFile);

            while (personScanner.hasNextLine()) {
                String nextline = personScanner.nextLine();
                String[] personComponents = nextline.split(",");
                // 确保数据完整性，避免数组越界
                if (personComponents.length >= 8) {
                    String firstname = personComponents[0].trim();
                    String lastname = personComponents[1].trim();
                    // 电话和邮件在本教程中不直接用于图构建，但可以存储
                    // String phone = personComponents[2].trim();
                    // String email = personComponents[3].trim();
                    String community = personComponents[4].trim();
                    String school = personComponents[5].trim();
                    String employer = personComponents[6].trim();
                    String privacy = personComponents[7].trim();

                    Person newPerson = new Person(firstname, lastname, community, school, employer, privacy);
                    persons.add(newPerson); // 将新创建的Person对象添加到列表中
                }
            }
            personScanner.close();
        } catch (FileNotFoundException e) {
            System.err.println("人员文件未找到: " + e.getMessage());
        }

        // 读取活动数据
        try {
            // 请根据实际情况修改文件路径
            String fileLocation = System.getProperty("user.home") + File.separator + "Downloads" + File.separator + "SamplefileActivities2022Oct31text.csv";
            File activityListFile = new File(fileLocation);
            Scanner activityScanner = new Scanner(activityListFile);
            while (activityScanner.hasNextLine()) {
                String nextLine = activityScanner.nextLine();
                String[] activityComponents = nextLine.split(",");
                if (activityComponents.length >= 3) {
                    String firstname = activityComponents[0].trim();
                    String lastname = activityComponents[1].trim();
                    String activity = activityComponents[2].trim();

                    Activities newActivity = new Activities(firstname, lastname, activity);
                    activities.add(newActivity); // 将新创建的Activities对象添加到列表中
                }
            }
            activityScanner.close();
        } catch (FileNotFoundException e) {
            System.err.println("活动文件未找到: " + e.getMessage());
        }
    }

    public List getPersons() {
        return persons;
    }

    public List getActivities() {
        return activities;
    }

    public static void main(String[] args) {
        InfoReader reader = new InfoReader();
        reader.readInfo();
        System.out.println("加载的人员数量: " + reader.getPersons().size());
        reader.getPersons().forEach(System.out::println);
        System.out.println("\n加载的活动数量: " + reader.getActivities().size());
        reader.getActivities().forEach(System.out::println);
    }
}

注意事项：

• 文件路径应根据实际环境进行调整。
• Person类和Activities类需要实现完整的构造函数、getter/setter方法。为了在集合中正确识别和比较Person对象，equals()和hashCode()方法也应被重写。这里假设firstname和lastname的组合可以唯一标识一个人。
• 在分割字符串时，使用trim()去除可能存在的空格。

3. 图的组件：节点与边

在我们的推荐系统中：

• 节点 (Vertices)：系统中的每个人都将作为图中的一个节点。
• 边 (Edges)：两个人之间如果存在“密切联系”，则在他们之间建立一条边。密切联系的定义是：共享同一社区、学校或雇主。由于我们不关心联系的强度，因此这是一个无权图。此外，这种关系是相互的（如果A是B的密切联系人，那么B也是A的密切联系人），所以这是一个无向图。

4. 图的表示：邻接列表

对于大多数图算法和稀疏图（即边相对较少的图），邻接列表 (Adjacency List) 是一个高效且常用的表示方法。它比邻接矩阵更节省空间，并且在查找某个节点的邻居时效率更高。

邻接列表通常用一个映射（Map）来实现，其中键是图中的每个节点，值是与该节点直接相连的所有邻居节点的列表。

在本例中，我们可以使用 Map> 来表示图：

• Person 对象作为键，代表图中的一个节点。
• List 作为值，包含所有与键 Person 有密切联系的 Person 对象。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.List;
import java.util.ArrayList;

public class RecommendationGraph {
    private Map> adjList; // 邻接列表表示图

    public RecommendationGraph() {
        adjList = new HashMap<>();
    }

    // 添加一个节点（如果不存在）
    public void addPerson(Person person) {
        adjList.putIfAbsent(person, new ArrayList<>());
    }

    // 添加一条边（密切联系），由于是无向图，需要双向添加
    public void addEdge(Person person1, Person person2) {
        if (!person1.equals(person2)) { // 避免自环
            addPerson(person1); // 确保节点存在
            addPerson(person2); // 确保节点存在
            // 双向添加边，并避免重复添加
            if (!adjList.get(person1).contains(person2)) {
                adjList.get(person1).add(person2);
            }
            if (!adjList.get(person2).contains(person1)) {
                adjList.get(person2).add(person1);
            }
        }
    }

    // 获取某个人的所有密切联系人
    public List getCloseContacts(Person person) {
        return adjList.getOrDefault(person, new ArrayList<>());
    }

    // 打印图结构（用于调试）
    public void printGraph() {
        for (Map.Entry> entry : adjList.entrySet()) {
            System.out.print(entry.getKey().getFirstname() + " " + entry.getKey().getLastname() + " -> ");
            for (Person neighbor : entry.getValue()) {
                System.out.print(neighbor.getFirstname() + " " + neighbor.getLastname() + ", ");
            }
            System.out.println();
        }
    }
}

5. 构建人员关系图

构建图的关键在于识别“密切联系”并添加相应的边。如果简单地对所有人员进行两两比较，其时间复杂度将是O(N^2)，这对于大量人员的数据集来说效率低下。我们可以通过预处理来优化这个过程。

5.1 优化密切联系查找

我们可以创建辅助的映射来快速查找共享相同属性的人员。例如：

• Map> communityMembers: 键是社区名称，值是该社区的所有成员。
• Map> schoolMembers: 键是学校名称，值是该学校的所有成员。
• Map> employerMembers: 键是雇主名称，值是该雇主的所有员工。

在加载人员数据后，我们可以填充这些辅助映射。然后，在构建图时，对于每个人，我们只需查询这些映射来找到其潜在的密切联系人。

// 在 InfoReader 类中添加或在单独的 GraphBuilder 类中实现
public class GraphBuilder {
    private List allPersons;
    private RecommendationGraph graph;

    // 辅助映射
    private Map> communityMembers = new HashMap<>();
    private Map> schoolMembers = new HashMap<>();
    private Map> employerMembers = new HashMap<>();

    public GraphBuilder(List persons) {
        this.allPersons = persons;
        this.graph = new RecommendationGraph();
        initializeAuxiliaryMaps();
    }

    // 填充辅助映射
    private void initializeAuxiliaryMaps() {
        for (Person person : allPersons) {
            // 添加到社区成员映射
            communityMembers.computeIfAbsent(person.getCommunity(), k -> new ArrayList<>()).add(person);
            // 添加到学校成员映射
            schoolMembers.computeIfAbsent(person.getSchool(), k -> new ArrayList<>()).add(person);
            // 添加到雇主成员映射
            employerMembers.computeIfAbsent(person.getEmployer(), k -> new ArrayList<>()).add(person);
        }
    }

    // 构建图的逻辑
    public RecommendationGraph buildGraph() {
        for (Person currentPerson : allPersons) {
            graph.addPerson(currentPerson); // 确保每个人都在图中作为节点

            Set closeContactsSet = new HashSet<>(); // 使用Set避免重复添加

            // 查找共享社区的成员
            if (communityMembers.containsKey(currentPerson.getCommunity())) {
                closeContactsSet.addAll(communityMembers.get(currentPerson.getCommunity()));
            }
            // 查找共享学校的成员
            if (schoolMembers.containsKey(currentPerson.getSchool())) {
                closeContactsSet.addAll(schoolMembers.get(currentPerson.getSchool()));
            }
            // 查找共享雇主的成员
            if (employerMembers.containsKey(currentPerson.getEmployer())) {
                closeContactsSet.addAll(employerMembers.get(currentPerson.getEmployer()));
            }

            // 为当前人员添加所有密切联系的边
            for (Person contact : closeContactsSet) {
                graph.addEdge(currentPerson, contact);
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        // 1. 读取数据
        InfoReader reader = new InfoReader();
        reader.readInfo();
        List persons = reader.getPersons();

        // 2. 构建图
        GraphBuilder builder = new GraphBuilder(persons);
        RecommendationGraph graph = builder.buildGraph();

        // 3. 打印图结构进行验证
        System.out.println("\n构建的图结构:");
        graph.printGraph();
    }
}

6. 生成推荐与隐私考量

一旦图构建完成，生成推荐就相对简单了。对于一个目标人物，我们首先从图中获取其所有密切联系人。然后，根据隐私设置过滤这些联系人。

public class RecommendationSystem {

    private RecommendationGraph graph;

    public RecommendationSystem(RecommendationGraph graph) {
        this.graph = graph;
    }

    /**
     * 为指定人员生成推荐列表。
     * 推荐是其密切联系人中未请求隐私的用户。
     * @param targetPerson 目标人员
     * @return 推荐的人员列表
     */
    public List generateRecommendations(Person targetPerson) {
        List recommendations = new ArrayList<>();
        List closeContacts = graph.getCloseContacts(targetPerson);

        for (Person contact : closeContacts) {
            // 排除目标人员自己，并检查隐私设置
            if (!contact.equals(targetPerson) && "N".equalsIgnoreCase(contact.getPrivacy())) {
                recommendations.add(contact);
            }
        }
        return recommendations;
    }

    public static void main(String[] args) {
        // 1. 读取数据
        InfoReader reader = new InfoReader();
        reader.readInfo();
        List persons = reader.getPersons();

        // 2. 构建图
        GraphBuilder builder = new GraphBuilder(persons);
        RecommendationGraph graph = builder.buildGraph();

        // 3. 初始化推荐系统并生成推荐
        RecommendationSystem recSystem = new RecommendationSystem(graph);

        // 示例：为列表中的第一个人生成推荐
        if (!persons.isEmpty()) {
            Person personToRecommendFor = persons.get(0); // 例如：Winston William
            System.out.println("\n为 " + personToRecommendFor.getFirstname() + " " + personToRecommendFor.getLastname() + " 生成推荐:");
            List recommendations = recSystem.generateRecommendations(personToRecommendFor);

            if (recommendations.isEmpty()) {
                System.out.println("没有可用的推荐。");
            } else {
                for (Person recPerson : recommendations) {
                    System.out.println("- " + recPerson.getFirstname() + " " + recPerson.getLastname());
                }
            }
        }

        // 示例：查找一个隐私设置为'Y'的人，看看是否会被推荐
        Person privatePerson = persons.stream()
                                     .filter(p -> "Y".equalsIgnoreCase(p.getPrivacy()))