Bug help

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Bug help

Karim Khalifa
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: [hidden email] 


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bug help

John Sichi
Administrator

Since you are overriding equals/hashCode, you are opting for object value semantics rather than object identity semantics.  As a result, there can be multiple equivalent objects floating around for the same vertex.  This doesn't play well together with having additional data (such as the children array) hanging off of those objects.

So to fix your bug, you have two options:

a) remove both equals and hashCode to make sure your vertex objects are unique

or

b) use a String for your vertex type, and keep a separate map from String to Node


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...