JGraphT graph update not working correctly

Question

I'm trying to implement a sort of graph summarization technique, where I check if a node has any children or not, if not, then the node is collapsed into it's parent. I've got 2 code snippets to do that, but one of them isn't working due to a bug in getEdgeSource, or atleast I think so. When using the 1st implementation, I can tag the nodes that should be collapsed, after that I loop over all the nodes in the graph again and add them to their respective parent, then delete them. This works perfectly. The other code snippet should do the same, but the nodes are not added to the parent, they only get deleted. Here are the snippets bellow: First here is my Node class:

public class Node implements Serializable{
    private static final long serialVersionUID = 1L;
    public String nodeID;
    public String timestamp;
    public ArrayList<Node> children = new ArrayList<Node>();
    public boolean tagged;
    public boolean isRoot;

    public Node(String a) {
        nodeID = a;
    }

    public void addChild(Node a){
        children.add(a);
    }

    public int getSize(){
        return children.size();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof Node)) {
            return false;
        }
        Node other = (Node) obj;
        return this.nodeID.equals(other.nodeID);
    }
    @Override
    public int hashCode() {
        return nodeID.hashCode();
    }
}

(Working code but more time complexity):

    public void oneLevelCollapse(DirectedGraph<Node, Edge> graph) {
    graphCopy = (DirectedGraph<Node, Edge>) ((AbstractBaseGraph<Node, Edge>)graph).clone();

    // iterate over every node and tag nodes to collapse
    for (Node node : graphCopy.vertexSet()) {
        // remove node if it has no children and only one parent
        if (graphCopy.outDegreeOf(node) == 0 && graphCopy.inDegreeOf(node) == 1) {
            node.tagged = true;
        }
    }
    // iterate over every node again and collapse/delete
    for (Node node : graphCopy.vertexSet()) {
        for (Edge edge : graphCopy.outgoingEdgesOf(node)) {
            Node child = graph.getEdgeTarget(edge);
            if (child.tagged) {
                node.addChild(child);
                graph.removeVertex(child);
            }
        }
    }
}

(The code that should work, but doesn't):

public void oneLevelCollapse(DirectedGraph<Node, Edge> graph) {
    graphCopy = (DirectedGraph<Node, Edge>) ((AbstractBaseGraph<Node, Edge>)graph).clone();

    // iterate over every node and tag nodes to collapse
    for (Node node : graphCopy.vertexSet()) {
        // remove node if it has no children and only one parent
        if (graphCopy.outDegreeOf(node) == 0 && graphCopy.inDegreeOf(node) == 1) {
            for (Edge edge : graphCopy.incomingEdgesOf(node)) {
                graph.getEdgeSource(edge).addChild(node);
                graph.removeVertex(node);
            }
        }
    }

}

The graph has no self-loops, graph is the graph I modify while keeping a copy of the original graph which is graphCopy.

Answer 1

You didn't provide the code for your Edge class, but with DefaultEdge for the edge class, both of your implementations of oneLevelCollapse(...) work and will pass this unit test:

public void testJgraph() {
    DirectedGraph<Node, DefaultEdge> graph = new SimpleDirectedGraph<>(DefaultEdge.class);
    Node v1 = new Node("a");
    Node v2 = new Node("b");
    Node v3 = new Node("c");
    graph.addVertex(v1);
    graph.addVertex(v2);
    graph.addVertex(v3);

    graph.addEdge(v1, v2);
    graph.addEdge(v2, v3);

    oneLevelCollapse(graph);

    assertEquals(2, graph.vertexSet().size());
    assertTrue(graph.vertexSet().contains(v1));
    assertTrue(graph.vertexSet().contains(v2));
    assertEquals(v3, v2.children.get(0));

}