javagraph-traversaljgrapht

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

I am using JGrapht for an in-memory representation of the employee hierarchy of an organization (SimpleDirectedGraph).

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

Every employee is represented as an instance of an 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);
        }
    }

Now, each pair of employees is connected through 2 edges:

To handle these, I have specialized an edge:

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 + ")";
        }

    }

I intialize the graph, this way:

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
});

For this data set:

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))
        );
    }

This is the graph that is created:

Hiearchy as seen by DOT representation

Two edges per pair are self-explanatory, I assume.

Now, given an employee, I want to find out all the employees, who she isBossOf!

Going by the dataset and the picture, given an employee '3', I should see:

[10, 1, 2, 6, 7]-these are the employees she supervises (isBossOf) directly or indirectly.

When I am using DepthFirstIterator, the result contains 5,4 and 11 as well. This is correct because the traversal is not restricted to the use of edge 'isBossOf'. Conceptually, I need to look at the subgraph which has nodes from 3 onward and only the edges with the label 'isBossOf'. If I can exclude the edges with the label 'reportsTo', then I cannot reach 4,5 and 11.

This is what I am stuck at. I am unable to arrive at the right view of the graph and the API(s)/Data Structures/Graph Type, that I need to use, to prepare that view.

Is this even the right type of graph? Am I supposed to create a SimpleMultiGraph instead? I cannot conclude. Obviously, there exists a gap in my understanding. I cannot find it.

Any help, appreciated.

-------------------------- Update ------------------------

Following the suggestion given by @joris-kinabel below, I have implemented a solution, the sample of which is in 'Answer Your Question' below.

Solution

  • It seems you are making this a little more complicated than necessary. The problem is that you have two opposing arcs for every vertex pair. As such, indeed a DepthFirstIterator will iterate over all vertices that are reachable from the vertex on which you start the iterator. I would propose the following changes.

    1. Create a Graph<Employee,DefaultEdge> org= new SimpleDirectedGraph<Employee,DefaultEdge>(DefaultEdge.class)
    2. Populate your graph with all the Employees. Add arcs to the graph, where an arc (v1,v2) between two employees v1 and v2 implies that v1 supervices v2. In other words, we only add the isBossOf arcs; we do not add the reportsTo arcs.

    To determine for a given employee who he/she supervices, or to whom he/she reports, we can write two simple functions.

    To get the list of employees that are superviced by a given supervices:

    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;
}

    To find out who someone reports to, we need to walk the graph in the reverse direction. For simplicity I hereby assume that every employee only has 1 boss, that is, the same person cannot be superviced by two people. To get the boss of a given employee v, we need to look at the incoming arcs of vertex v. If v does not have any incoming arcs, that means that he's the CEO of the org. Otherwise, v must have exactly one incoming arc. Once we obtained the boss of v, say u, we proceed by looking for the boss of u, until we reached the 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;
}

    An alternative way of writing the above method using recursion:

    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;
  }
}

    If you really insist to maintain your double EmployeeRelationship arcs, you would have to adjust the above methods to only use bossOf or reportsTo arcs.