[jgrapht-users] Bug help

[Karim K. <kar...@ho...>]

Dear All,


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):

        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):

for (Node node : graphCopy.vertexSet()) {
           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 original graph and graphCopy is the copy that I use to modify, without affecting the original graph as I need it for further processing, Thank you for your time and hope to hear from you soon.

Best Regards,
Karim Khalifa

Ms.c Student
Cognitive Technical Systems
Department of Computer Science
Albert-Ludwigs-Universität Freiburg
Freiburg im Breisgau - Germany

email: kar...@ju...<mailto:kar...@ju...>