algorithm - java.lang.IllegalArgumentException: Tree must not already contain child -

algorithm - java.lang.IllegalArgumentException: Tree must not already contain child -

i have created next jung2 visualization. code visualizes text tree. using 2 inputs, 1 @ time:

/* * input 1 */ string text = "=if(a2=1;0;if(d2=d3;if(c2=1;true;false);4))"; /* * input 2 */ string text = "=if(a2=1;0;if(d2=d3;if(c2=1;true;false);true))";

my problem is, first input works expected, when using input 2, different in lastly element 4 instead of true, error:

exception in thread "main" java.lang.illegalargumentexception: tree must not contain kid d2=d3 @ edu.uci.ics.jung.graph.delegatetree.addchild(delegatetree.java:182) @ edu.uci.ics.jung.graph.delegatetree.addedge(delegatetree.java:102) @ edu.uci.ics.jung.graph.delegatetree.addedge(delegatetree.java:346) @ edu.uci.ics.jung.graph.util.treeutils.growsubtree(treeutils.java:76) @ edu.uci.ics.jung.graph.util.treeutils.growsubtree(treeutils.java:80) @ edu.uci.ics.jung.graph.delegateforest.gettrees(delegateforest.java:295) @ edu.uci.ics.jung.graph.util.treeutils.getroots(treeutils.java:34) @ edu.uci.ics.jung.algorithms.layout.treelayout.buildtree(treelayout.java:102) @ edu.uci.ics.jung.algorithms.layout.treelayout.<init>(treelayout.java:97) @ edu.uci.ics.jung.algorithms.layout.treelayout.<init>(treelayout.java:75) @ justdelete.me.codetestingpackage.test.<init>(test.java:131) @ justdelete.me.codetestingpackage.test.main(test.java:396)

the confusing thing string parsed correctly , used programme correctly like:

[if, a2=1, 0, if, d2=d3, if, c2=1, true, false, true]

here version of programme runnable input 2(the "broken" input) in comments:

@suppresswarnings("serial") public class test extends japplet { /** * graph */ forest<string,integer> graph; private static final logger log = logger.getlogger(test.class); factory<directedgraph<string,integer>> graphfactory = new factory<directedgraph<string,integer>>() { public directedgraph<string, integer> create() { homecoming new directedsparsemultigraph<string,integer>(); } }; factory<tree<string,integer>> treefactory = new factory<tree<string,integer>> () { public tree<string, integer> create() { homecoming new delegatetree<string,integer>(graphfactory); } }; factory<integer> edgefactory = new factory<integer>() { int i=0; public integer create() { homecoming i++; }}; factory<string> vertexfactory = new factory<string>() { int i=0; public string create() { homecoming "v"+i++; }}; /** * visual component , renderer graph */ visualizationviewer<string,integer> vv; visualizationserver.paintable rings; string root; treelayout<string,integer> layout; @suppresswarnings("unchecked") frlayout layout1; treecollapser collapser; radialtreelayout<string,integer> radiallayout; @suppresswarnings("unchecked") public test() { // create simple graph demo graph = new delegateforest<string,integer>(); createtree(); layout = new treelayout<string,integer>(graph); collapser = new treecollapser(); radiallayout = new radialtreelayout<string,integer>(graph); radiallayout.setsize(new dimension(600,600)); vv = new visualizationviewer<string,integer>(layout, new dimension(600,600)); vv.setbackground(color.white); vv.getrendercontext().setedgeshapetransformer(new edgeshape.line()); vv.getrendercontext().setvertexlabeltransformer(new tostringlabeller()); vv.getrendercontext().setvertexshapetransformer(new clustervertexshapefunction()); // add together listener tooltips vv.setvertextooltiptransformer(new tostringlabeller()); vv.getrendercontext().setarrowfillpainttransformer(new constanttransformer(color.lightgray)); rings = new rings(); container content = getcontentpane(); final graphzoomscrollpane panel = new graphzoomscrollpane(vv); content.add(panel); final defaultmodalgraphmouse graphmouse = new defaultmodalgraphmouse(); vv.setgraphmouse(graphmouse); jcombobox modebox = graphmouse.getmodecombobox(); modebox.additemlistener(graphmouse.getmodelistener()); graphmouse.setmode(modalgraphmouse.mode.transforming); final scalingcontrol scaler = new crossoverscalingcontrol(); jbutton plus = new jbutton("+"); plus.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { scaler.scale(vv, 1.1f, vv.getcenter()); } }); jbutton minus = new jbutton("-"); minus.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { scaler.scale(vv, 1/1.1f, vv.getcenter()); } }); jtogglebutton radial = new jtogglebutton("radial"); radial.additemlistener(new itemlistener() { public void itemstatechanged(itemevent e) { if(e.getstatechange() == itemevent.selected) { // layout.setradial(true); vv.setgraphlayout(radiallayout); vv.getrendercontext().getmultilayertransformer().settoidentity(); vv.addprerenderpaintable(rings); } else { // layout.setradial(false); vv.setgraphlayout(layout); vv.getrendercontext().getmultilayertransformer().settoidentity(); vv.removeprerenderpaintable(rings); } vv.repaint(); }}); jbutton collapse = new jbutton("collapse"); collapse.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { collection picked =new hashset(vv.getpickedvertexstate().getpicked()); if(picked.size() == 1) { object root = picked.iterator().next(); forest ingraph = (forest)layout.getgraph(); seek { collapser.collapse(vv.getgraphlayout(), ingraph, root); } grab (instantiationexception e1) { // todo auto-generated grab block e1.printstacktrace(); } grab (illegalaccessexception e1) { // todo auto-generated grab block e1.printstacktrace(); } vv.getpickedvertexstate().clear(); vv.repaint(); } }}); jbutton expand = new jbutton("expand"); expand.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { collection picked = vv.getpickedvertexstate().getpicked(); for(object v : picked) { if(v instanceof forest) { forest ingraph = (forest)layout.getgraph(); collapser.expand(ingraph, (forest)v); } vv.getpickedvertexstate().clear(); vv.repaint(); } }}); jpanel scalegrid = new jpanel(new gridlayout(1,0)); scalegrid.setborder(borderfactory.createtitledborder("zoom")); jpanel controls = new jpanel(); scalegrid.add(plus); scalegrid.add(minus); controls.add(radial); controls.add(scalegrid); controls.add(modebox); controls.add(collapse); controls.add(expand); content.add(controls, borderlayout.south); } class rings implements visualizationserver.paintable { collection<double> depths; public rings() { depths = getdepths(); } private collection<double> getdepths() { set<double> depths = new hashset<double>(); map<string,polarpoint> polarlocations = radiallayout.getpolarlocations(); for(string v : graph.getvertices()) { polarpoint pp = polarlocations.get(v); depths.add(pp.getradius()); } homecoming depths; } public void paint(graphics g) { g.setcolor(color.lightgray); graphics2d g2d = (graphics2d)g; point2d center = radiallayout.getcenter(); ellipse2d ellipse = new ellipse2d.double(); for(double d : depths) { ellipse.setframefromdiagonal(center.getx()-d, center.gety()-d, center.getx()+d, center.gety()+d); shape shape = vv.getrendercontext(). getmultilayertransformer().gettransformer(layer.layout).transform(ellipse); g2d.draw(shape); } } public boolean usetransform() { homecoming true; } } /** * create tree */ private void createtree() { /* * input 1 */ // string text = "=if(a2=1;0;if(d2=d3;if(c2=1;true;false);4))"; /* * input 2 */ string text = "=if(a2=1;0;if(d2=d3;if(c2=1;true;false);true))"; text.touppercase(); //start string[] operands = text.substring(1, text.length()).split("[;()]+"); system.out.println(arrays.tostring(operands)); int numifs = operands.length / 3; // (operands.length - 1) / 3 int partition makes same string[] nodes = new string[numifs]; // stores nodes (test strings) int[] operandnos = new int[numifs]; // stores number of operands if has int nodesindex = -1; // index of if node parsed (string s : operands) { if (s.equals("if")) { // new if found -> increment position in "stack" (nodes) operandnos[++nodesindex] = 0; } else { // addvertex(s); graph.addvertex(s); switch (operandnos[nodesindex]++) { case 0: // first operand = node name nodes[nodesindex] = s; break; case 1: // sec operand found -> add together border graph.addedge(edgefactory.create(), s, nodes[nodesindex]); break; case 2: // lastly operand found -> add together border , go { graph.addedge(edgefactory.create(), s, nodes[nodesindex]); s = nodes[nodesindex--]; } while (nodesindex >= 0 && operandnos[nodesindex]++ == 2); if (nodesindex >= 0) { // not lastly operand of if graph.addedge(edgefactory.create(), s, nodes[nodesindex]); } } } } //end } class clustervertexshapefunction<v> extends ellipsevertexshapetransformer<v> { clustervertexshapefunction() { setsizetransformer(new clustervertexsizefunction<v>(20)); } @suppresswarnings("unchecked") @override public shape transform(v v) { if(v instanceof graph) { int size = ((graph)v).getvertexcount(); if (size < 8) { int sides = math.max(size, 3); homecoming factory.getregularpolygon(v, sides); } else { homecoming factory.getregularstar(v, size); } } homecoming super.transform(v); } } /** * demo class create vertices larger if represent * collapsed collection of original vertices * @author tom nelson * * @param <v> */ class clustervertexsizefunction<v> implements transformer<v,integer> { int size; public clustervertexsizefunction(integer size) { this.size = size; } public integer transform(v v) { if(v instanceof graph) { homecoming 30; } homecoming size; } } /** * driver demo */ public static void main(string[] args) { jframe frame = new jframe(); container content = frame.getcontentpane(); frame.setdefaultcloseoperation(jframe.exit_on_close); content.add(new test()); frame.pack(); frame.setvisible(true); } }

when executing code input 2, posted error. recommendations why case? guess strings same, though kind of ridiculous because leaves of tree should unique. hence, how deal problem?

i appreciate answer!

the problem same vertex should appear multiple times.

one go far explaining details, give idea: imagine graph in jung internally maintained bunch of maps. example, map<v, set<e>> maps each vertex set of edges start @ vertex. now, defined type of vertex string. , when there multiple vertices should identified same string, particular graph (which should tree) may become inconsistent.

even more suggestive: want create tree looks this:

tree.getnode("a").addchild("true"); tree.getnode("b").addchild("true");

this mean node corresponds string "true" have two parents, namely node "a" , node "b". (the actual situation in case different, did not analyze parsing in detail - in case, message "tree must not contain kid d2=d3" indicates "this kind of problem".

the solution rather simple, although may bit inconvenient: have create sure there may multiple vertices same string, still considered beingness different vertices. in particular: equals method of these vertices must homecoming false when objects should distinct vertices.

this can achieved introducing simple vertex class. sketched here, , seems work, again: did not analyze parser doing there, , should check whether there still places vertices assumed strings , should changed utilize vertex objects instead (and code need cleanup, way). however, should show basic approach solving this:

package stackoverflow; import java.awt.borderlayout; import java.awt.color; import java.awt.container; import java.awt.dimension; import java.awt.graphics; import java.awt.graphics2d; import java.awt.gridlayout; import java.awt.shape; import java.awt.event.actionevent; import java.awt.event.actionlistener; import java.awt.event.itemevent; import java.awt.event.itemlistener; import java.awt.geom.ellipse2d; import java.awt.geom.point2d; import java.util.arrays; import java.util.collection; import java.util.hashset; import java.util.map; import java.util.set; import javax.swing.borderfactory; import javax.swing.japplet; import javax.swing.jbutton; import javax.swing.jcombobox; import javax.swing.jframe; import javax.swing.jpanel; import javax.swing.jtogglebutton; import org.apache.commons.collections15.factory; import org.apache.commons.collections15.transformer; import org.apache.commons.collections15.functors.constanttransformer; import edu.uci.ics.jung.algorithms.layout.frlayout; import edu.uci.ics.jung.algorithms.layout.polarpoint; import edu.uci.ics.jung.algorithms.layout.radialtreelayout; import edu.uci.ics.jung.algorithms.layout.treelayout; import edu.uci.ics.jung.graph.delegateforest; import edu.uci.ics.jung.graph.delegatetree; import edu.uci.ics.jung.graph.directedgraph; import edu.uci.ics.jung.graph.directedsparsemultigraph; import edu.uci.ics.jung.graph.forest; import edu.uci.ics.jung.graph.graph; import edu.uci.ics.jung.graph.tree; import edu.uci.ics.jung.visualization.graphzoomscrollpane; import edu.uci.ics.jung.visualization.layer; import edu.uci.ics.jung.visualization.visualizationserver; import edu.uci.ics.jung.visualization.visualizationviewer; import edu.uci.ics.jung.visualization.control.crossoverscalingcontrol; import edu.uci.ics.jung.visualization.control.defaultmodalgraphmouse; import edu.uci.ics.jung.visualization.control.modalgraphmouse; import edu.uci.ics.jung.visualization.control.scalingcontrol; import edu.uci.ics.jung.visualization.decorators.edgeshape; import edu.uci.ics.jung.visualization.decorators.ellipsevertexshapetransformer; import edu.uci.ics.jung.visualization.decorators.tostringlabeller; import edu.uci.ics.jung.visualization.sublayout.treecollapser; class vertex { private static int idcounter = 0; private final string name; private final int id; vertex(string name) { this.name = name; this.id = idcounter++; } string getname() { homecoming name; } @override public string tostring() { homecoming name; } @override public int hashcode() { final int prime = 31; int result = 1; result = prime * result + id; result = prime * result + ((name == null) ? 0 : name.hashcode()); homecoming result; } @override public boolean equals(object obj) { if (this == obj) homecoming true; if (obj == null) homecoming false; if (getclass() != obj.getclass()) homecoming false; vertex other = (vertex) obj; if (id != other.id) homecoming false; if (name == null) { if (other.name != null) homecoming false; } else if (!name.equals(other.name)) homecoming false; homecoming true; } } @suppresswarnings("serial") public class jungtree extends japplet { /** * graph */ forest<vertex, integer> graph; factory<directedgraph<vertex, integer>> graphfactory = new factory<directedgraph<vertex, integer>>() { public directedgraph<vertex, integer> create() { homecoming new directedsparsemultigraph<vertex, integer>(); } }; factory<tree<vertex, integer>> treefactory = new factory<tree<vertex, integer>>() { public tree<vertex, integer> create() { homecoming new delegatetree<vertex, integer>(graphfactory); } }; factory<integer> edgefactory = new factory<integer>() { int = 0; public integer create() { homecoming i++; } }; factory<vertex> vertexfactory = new factory<vertex>() { int = 0; public vertex create() { homecoming new vertex("v" + i++); } }; /** * visual component , renderer graph */ visualizationviewer<vertex, integer> vv; visualizationserver.paintable rings; string root; treelayout<vertex, integer> layout; @suppresswarnings("unchecked") frlayout layout1; treecollapser collapser; radialtreelayout<vertex, integer> radiallayout; @suppresswarnings("unchecked") public jungtree() { // create simple graph demo graph = new delegateforest<vertex, integer>(); createtree(); layout = new treelayout<vertex, integer>(graph); collapser = new treecollapser(); radiallayout = new radialtreelayout<vertex, integer>(graph); radiallayout.setsize(new dimension(600, 600)); vv = new visualizationviewer<vertex, integer>(layout, new dimension(600, 600)); vv.setbackground(color.white); vv.getrendercontext().setedgeshapetransformer(new edgeshape.line()); vv.getrendercontext().setvertexlabeltransformer(new tostringlabeller()); vv.getrendercontext().setvertexshapetransformer( new clustervertexshapefunction()); // add together listener tooltips vv.setvertextooltiptransformer(new tostringlabeller()); vv.getrendercontext().setarrowfillpainttransformer( new constanttransformer(color.lightgray)); rings = new rings(); container content = getcontentpane(); final graphzoomscrollpane panel = new graphzoomscrollpane(vv); content.add(panel); final defaultmodalgraphmouse graphmouse = new defaultmodalgraphmouse(); vv.setgraphmouse(graphmouse); jcombobox modebox = graphmouse.getmodecombobox(); modebox.additemlistener(graphmouse.getmodelistener()); graphmouse.setmode(modalgraphmouse.mode.transforming); final scalingcontrol scaler = new crossoverscalingcontrol(); jbutton plus = new jbutton("+"); plus.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { scaler.scale(vv, 1.1f, vv.getcenter()); } }); jbutton minus = new jbutton("-"); minus.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { scaler.scale(vv, 1 / 1.1f, vv.getcenter()); } }); jtogglebutton radial = new jtogglebutton("radial"); radial.additemlistener(new itemlistener() { public void itemstatechanged(itemevent e) { if (e.getstatechange() == itemevent.selected) { // layout.setradial(true); vv.setgraphlayout(radiallayout); vv.getrendercontext().getmultilayertransformer() .settoidentity(); vv.addprerenderpaintable(rings); } else { // layout.setradial(false); vv.setgraphlayout(layout); vv.getrendercontext().getmultilayertransformer() .settoidentity(); vv.removeprerenderpaintable(rings); } vv.repaint(); } }); jbutton collapse = new jbutton("collapse"); collapse.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { collection picked = new hashset(vv.getpickedvertexstate().getpicked()); if (picked.size() == 1) { object root = picked.iterator().next(); forest ingraph = (forest) layout.getgraph(); seek { collapser.collapse(vv.getgraphlayout(), ingraph, root); } grab (instantiationexception e1) { // todo auto-generated grab block e1.printstacktrace(); } grab (illegalaccessexception e1) { // todo auto-generated grab block e1.printstacktrace(); } vv.getpickedvertexstate().clear(); vv.repaint(); } } }); jbutton expand = new jbutton("expand"); expand.addactionlistener(new actionlistener() { public void actionperformed(actionevent e) { collection picked = vv.getpickedvertexstate().getpicked(); (object v : picked) { if (v instanceof forest) { forest ingraph = (forest) layout.getgraph(); collapser.expand(ingraph, (forest) v); } vv.getpickedvertexstate().clear(); vv.repaint(); } } }); jpanel scalegrid = new jpanel(new gridlayout(1, 0)); scalegrid.setborder(borderfactory.createtitledborder("zoom")); jpanel controls = new jpanel(); scalegrid.add(plus); scalegrid.add(minus); controls.add(radial); controls.add(scalegrid); controls.add(modebox); controls.add(collapse); controls.add(expand); content.add(controls, borderlayout.south); } class rings implements visualizationserver.paintable { collection<double> depths; public rings() { depths = getdepths(); } private collection<double> getdepths() { set<double> depths = new hashset<double>(); map<vertex, polarpoint> polarlocations = radiallayout.getpolarlocations(); (vertex v : graph.getvertices()) { polarpoint pp = polarlocations.get(v); depths.add(pp.getradius()); } homecoming depths; } public void paint(graphics g) { g.setcolor(color.lightgray); graphics2d g2d = (graphics2d) g; point2d center = radiallayout.getcenter(); ellipse2d ellipse = new ellipse2d.double(); (double d : depths) { ellipse.setframefromdiagonal(center.getx() - d, center.gety() - d, center.getx() + d, center.gety() + d); shape shape = vv.getrendercontext().getmultilayertransformer() .gettransformer(layer.layout).transform(ellipse); g2d.draw(shape); } } public boolean usetransform() { homecoming true; } } /** * create tree */ private void createtree() { /* * input 1 */ //string text = "=if(a2=1;0;if(d2=d3;if(c2=1;true;false);4))"; /* * input 2 */ string text = "=if(a2=1;0;if(d2=d3;if(c2=1;true;false);true))"; text.touppercase(); // start string[] operandstrings = text.substring(1, text.length()).split("[;()]+"); vertex[] operands = new vertex[operandstrings.length]; (int i=0; i<operandstrings.length; i++) { operands[i] = new vertex(operandstrings[i]); } system.out.println(arrays.tostring(operands)); int numifs = operands.length / 3; // (operands.length - 1) / 3 // int partition makes same vertex[] nodes = new vertex[numifs]; // stores nodes (test strings) int[] operandnos = new int[numifs]; // stores number of operands // if has int nodesindex = -1; // index of if node parsed (vertex s : operands) { if (s.getname().equals("if")) { // new if found -> increment position in "stack" (nodes) operandnos[++nodesindex] = 0; } else { // addvertex(s); graph.addvertex(s); switch (operandnos[nodesindex]++) { case 0: // first operand = node name nodes[nodesindex] = s; break; case 1: // sec operand found -> add together border graph.addedge(edgefactory.create(), s, nodes[nodesindex]); break; case 2: // lastly operand found -> add together border , go { graph.addedge(edgefactory.create(), s, nodes[nodesindex]); s = nodes[nodesindex--]; } while (nodesindex >= 0 && operandnos[nodesindex]++ == 2); if (nodesindex >= 0) { // not lastly operand of if graph.addedge(edgefactory.create(), s, nodes[nodesindex]); } } } } // end } class clustervertexshapefunction<v> extends ellipsevertexshapetransformer<v> { clustervertexshapefunction() { setsizetransformer(new clustervertexsizefunction<v>(20)); } @suppresswarnings("unchecked") @override public shape transform(v v) { if (v instanceof graph) { int size = ((graph) v).getvertexcount(); if (size < 8) { int sides = math.max(size, 3); homecoming factory.getregularpolygon(v, sides); } else { homecoming factory.getregularstar(v, size); } } homecoming super.transform(v); } } /** * demo class create vertices larger if represent collapsed * collection of original vertices * * @author tom nelson * * @param <v> */ class clustervertexsizefunction<v> implements transformer<v, integer> { int size; public clustervertexsizefunction(integer size) { this.size = size; } public integer transform(v v) { if (v instanceof graph) { homecoming 30; } homecoming size; } } /** * driver demo */ public static void main(string[] args) { jframe frame = new jframe(); container content = frame.getcontentpane(); frame.setdefaultcloseoperation(jframe.exit_on_close); content.add(new jungtree()); frame.pack(); frame.setvisible(true); } }

java algorithm jung jung2