使用 JGrapht 的 BreadthFirstIterator，通过选择一种特定的边类型

Question

我正在使用 JGrapht 在内存中表示组织的员工层次结构 (SimpleDirectedGraph)。

var org = new SimpleDirectedGraph<Employee, EmployeeRelationship>(EmployeeRelationship.class);

每个员工都表示为 Employee 的一个实例 class:

public class Employee {
        private final Integer empID;
        private Option<String> extraInfo;

        public Employee(Integer empID) {
            this.empID = empID;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Employee employee = (Employee) o;
            return empID.equals(employee.empID);
        }

        @Override
        public int hashCode() {
            return Objects.hash(empID);
        }
    }

现在，每对员工通过 2 条边连接：

reportsTo（如 Emp(10) reportsTo Emp(11)）
isBossOf（如 Emp(11) isBossOf Emp(10)）

为了处理这些，我特化了一条边：

public class EmployeeRelationship extends DefaultEdge {

        private final String edgeLabel;

        public EmployeeRelationship(String edgeLabel) {
            this.edgeLabel = edgeLabel;
        }

        public String getLabel() {
            return edgeLabel;
        }

        @Override
        public String toString() {
            return "(" + getSource() + " : " + getTarget() + " : " + edgeLabel + ")";
        }

    }

我用这种方式初始化图形：

bunchOfPlayers.forEach(next2Players -> {
    empGraph.addVertex(next2Emps._1); // fromEmp
    empGraph.addVertex(next2Emps._2); // toEmp
    empGraph.addEdge(next2Emps._1, next2Emps._2, new EmployeeRelationship("reportsTo")); // fromEmp reports toEmp
    empGraph.addEdge(next2Emps._2, next2Emps._1, new EmployeeRelationship("isBossOf")); // toEmp isBossOf fromEmp
});

对于这个数据集：

private io.vavr.collection.List<Tuple2<Employee, Employee>> getTupleOfHierarchy(){
        return io.vavr.collection.List.of(
                Tuple.of(new Employee(1), new Employee(2)),
                Tuple.of(new Employee(2), new Employee(3)),
                Tuple.of(new Employee(3), new Employee(4)),
                Tuple.of(new Employee(4), new Employee(5)),
                Tuple.of(new Employee(6), new Employee(2)),
                Tuple.of(new Employee(7), new Employee(2)),
                Tuple.of(new Employee(10), new Employee(3)),
                Tuple.of(new Employee(11), new Employee(4)),
                Tuple.of(new Employee(21), new Employee(22)),
                Tuple.of(new Employee(19), new Employee(22)),
                Tuple.of(new Employee(18), new Employee(22)),
                Tuple.of(new Employee(22), new Employee(23))
        );
    }

这是创建的图表：

我假设每对两条边是不言自明的。

现在，给定一名员工，我想找出所有员工，她 isBossOf!

根据数据集和图片，给定员工“3”，我应该看到：

[10, 1, 2, 6, 7]-这些是她直接或间接监管的员工(isBossOf)。

当我使用 DepthFirstIterator 时，结果也包含 5,4 和 11。这是正确的，因为遍历不限于使用边'isBossOf'。从概念上讲，我需要查看具有从 3 开始的节点的子图和 仅具有标签 'isBossOf' 的边。如果我可以排除带有标签 'reportsTo' 的边缘，那么我无法达到 4,5 和 11.

这就是我所坚持的。我无法获得图表的正确视图和我需要使用的 API(s)/Data Structures/Graph 类型来准备该视图。

这是否是正确的图表类型？我应该改为创建一个 SimpleMultiGraph 吗？我无法下结论。显然，我的理解存在差距。我找不到它。

任何帮助，不胜感激。

------------------------更新---------------- ------

根据下面@joris-kinabel 的建议，我实现了一个解决方案，其示例在下面的'Answer Your Question'中。

Answer 1

看来你把事情搞得有点复杂了。问题是每个顶点对都有两条相反的弧。因此，实际上 DepthFirstIterator 将遍历从您启动迭代器的顶点可到达的所有顶点。我会提出以下更改。

创建 Graph<Employee,DefaultEdge> org= new SimpleDirectedGraph<Employee,DefaultEdge>(DefaultEdge.class)
用所有员工填充图表。向图中添加弧线，其中两个员工 v1 和 v2 之间的弧线 (v1,v2) 表示 v1 supervices v2.换句话说，我们只添加了isBossOf个弧线；我们不添加 reportsTo 弧。

要确定 he/she 监督或向 he/she 报告的给定员工，我们可以编写两个简单的函数。

获取受给定主管监督的员工列表：

public Set<Employee> getSupervicedEmployees(Employee superviser){
  Set<Employee> employees = new HashSet<>();
  Iterator<Employee> bfs = new BreadthFirstIterator(org, supervisor);
  while (iterator.hasNext()) {
    employees.add(iterator.next());
  }
  return employees;
}

要找出某人向谁报告，我们需要反向遍历图表。为简单起见，我假设每个员工只有一个老板，即同一个人不能被两个人监管。要获得给定员工 v 的老板，我们需要查看顶点 v 的传入弧。如果 v 没有任何传入弧，则表示他是组织的首席执行官。否则，v 必须恰好有一个传入弧。一旦我们获得了 v 的老板，比如说 u，我们继续寻找 u 的老板，直到找到 CEO。

public Set<Employee> getBosses(Employee employee){
  Set<Employee> bosses = new HashSet<>();
  while(!org.getIncomingEdgesOf(employee).isEmpty()){
    Employee boss=org.getIncomingEdgesOf(employee).iterator().next();
    bosses.add(boss);
    employee=boss;
  }
  return bosses;
}

使用递归编写上述方法的另一种方法：

public Set<Employee> getBosses(Employee employee){
  if(org.getIncomingEdgesOf(employee).isEmpty()){
    return Collections.emptySet(); //this employee is the CEO
  }else{
    Employee boss=org.getIncomingEdgesOf(employee).iterator().next();
    Set<Employee> bosses = new HashSet<>(Arrays.asList(boss));
    bosses.addAll(getBosses(boss)); //Get the bosses of the boss
    return bosses;
  }
}

如果你真的坚持要保持你的双EmployeeRelationship弧线，你将不得不调整上述方法只使用bossOf或reportsTo弧线。

Answer 2

根据上面@joris-kinabel 的建议，下面是我为查找任何员工的下属而实现的：

private io.vavr.collection.List<Employee> pickAllSubordinates(Graph<Employee,EmployeeReportsToRelationship> g, Employee herSelf) {

    Set<EmployeeReportsToRelationship> allIncomings = io.vavr.collection.HashSet.ofAll(g.incomingEdgesOf(herSelf));
    var allReportingToThisEmployee = allIncomings.map(relation -> g.getEdgeSource(relation));

    if (allReportingToThisEmployee.isEmpty()) {
        return (io.vavr.collection.List.empty());
    }
    else {
        io.vavr.collection.List<Employee> accumulatorOfSubordinates = io.vavr.collection.List.empty();
        for (Employee nextEmployee: allReportingToThisEmployee) { 
            accumulatorOfSubordinates = accumulatorOfSubordinates.append(nextEmployee).appendAll(pickAllSubordinates(g,nextEmployee));
         
        }
        return (accumulatorOfSubordinates);
    }
}

我需要一个列表用于应用程序中的后续流程；因此，列表而不是集合。

以防万一，对大家有帮助。

使用 JGrapht 的 BreadthFirstIterator，通过选择一种特定的边类型

Using JGrapht's BreadthFirstIterator, by choosing one particular edge type

java

graph-traversal

jgrapht