# # dotty_edit: editing functions and data structures # dotty.protogt.getnodesbyattr = function (gt, key, val) { local nid, node, nlist; nlist = []; for (nid in gt.graph.nodes) { node = gt.graph.nodes[nid]; if (node.attr[key] == val) nlist[nid] = node; } return nlist; }; dotty.protogt.reachablenodes = function (gt, node) { local nlist, stack, eid, edge, i; stack[0] = node; i = 1; while (i > 0) { node = stack[i - 1]; i = i - 1; nlist[node.nid] = node; for (eid in node.edges) { edge = node.edges[eid]; if (~nlist[edge.head.nid]) { nlist[edge.head.nid] = edge.head; stack[i] = edge.head; i = i + 1; } } } return nlist; }; dotty.protogt.mergegraph = function (gt, graph, show) { local nameid, onode, pos, size, eid, eid2, tnode, hnode, oedge; if (~gt.noundo) gt.startadd2undo (gt); for (nameid in graph.nodedict) { pos = null; size = null; onode = graph.nodes[graph.nodedict[nameid]]; if (onode.pos) pos = node.pos; if (onode.size) size = node.size; if (~(gt.graph.nodedict[nameid] >= 0)) { pos = null; size = null; if (onode.pos) pos = node.pos; if (onode.size) size = node.size; gt.insertnode (gt, pos, size, nameid, onode.attr, show); } } for (eid in graph.edges) { oedge = graph.edges[eid]; tnode = gt.graph.nodes[gt.graph.nodedict[oedge.tail.name]]; hnode = gt.graph.nodes[gt.graph.nodedict[oedge.head.name]]; for (eid2 in tnode.edges) if (tnode.edges[eid2].tail == tnode & tnode.edges[eid2].head == hnode) { oedge = null; break; } if (oedge) gt.insertedge (gt, tnode, null, hnode, null, oedge.attr, show); } if (~gt.noundo) gt.endadd2undo (gt); }; dotty.protogt.insertsgraph = function (gt, name, attr, show) { local gid, sgraph, aid; if (~gt) return null; gid = gt.graph.maxgid; if (~name) { while (gt.graph.graphdict[(name = concat ('g', gid))] >= 0) gid = gid + 1; } else if (gt.graph.graphdict[name]) { dotty.message (0, concat ('graph: ', name, ' exists')); return null; } gt.graph.graphdict[name] = gid; gt.graph.maxgid = gid + 1; gt.graph.graphs[gid] = [ dotty.keys.gid = gid; dotty.keys.name = name; dotty.keys.gattr = copy (gt.graph.graphattr); dotty.keys.nattr = copy (gt.graph.nodeattr); dotty.keys.eattr = copy (gt.graph.edgeattr); ]; sgraph = gt.graph.graphs[gid]; if (~attr) attr = []; if (~attr.label) attr.label = '\N'; for (aid in attr) sgraph.graphattr[aid] = attr[aid]; gt.unpacksgraphattr (gt, sgraph); if (show) gt.drawsgraph (gt, gt.views, sgraph); return sgraph; }; dotty.protogt.removesgraph = function (gt, sgraph) { gt.undrawsgraph (gt, gt.views, sgraph); remove (sgraph.name, gt.graph.graphdict); remove (sgraph.gid, gt.graph.graphs); }; dotty.protogt.insertnode = function (gt, pos, size, name, attr, show) { local nid, node, aid; nid = gt.graph.maxnid; if (~name) { while (gt.graph.nodedict[(name = concat ('n', nid))] >= 0) nid = nid + 1; } else if (gt.graph.nodedict[name] >= 0) { dotty.message (0, concat ('node: ', name, ' exists')); return null; } gt.graph.nodedict[name] = nid; gt.graph.maxnid = nid + 1; gt.graph.nodes[nid] = [ dotty.keys.nid = nid; dotty.keys.name = name; dotty.keys.attr = copy (gt.graph.nodeattr); dotty.keys.edges = []; ]; node = gt.graph.nodes[nid]; if (~attr) attr = []; if (~attr.label) attr.label = '\N'; for (aid in attr) node.attr[aid] = attr[aid]; gt.unpacknodeattr (gt, node); if (~pos) pos = ['x' = 10; 'y' = 10;]; node[dotty.keys.pos] = copy (pos); if (~size) size = ['x' = strlen (attr.label) * 30; 'y' = 30;]; if (size.x == 0) size.x = 30; node[dotty.keys.size] = copy (size); if (show) gt.drawnode (gt, gt.views, node); if (~gt.noundo) { gt.startadd2undo (gt); gt.currundo.inserted.nodes[nid] = node; gt.endadd2undo (gt); } return node; }; dotty.protogt.removenode = function (gt, node) { local eid, list, edge, gid; if (~gt.noundo) gt.startadd2undo (gt); for (eid in node.edges) list[eid] = node.edges[eid]; for (eid in list) gt.removeedge (gt, list[eid]); gt.undrawnode (gt, gt.views, node); for (gid in gt.graph.graphs) remove (node.nid, gt.graph.graphs[gid].nodes); remove (node.name, gt.graph.nodedict); remove (node.nid, gt.graph.nodes); if (~gt.noundo) { gt.currundo.deleted.nodes[node.nid] = node; gt.endadd2undo (gt); } }; dotty.protogt.insertedge = function (gt, nodea, porta, nodeb, portb, attr, show) { local eid, edge, aid, tport, hport; if (~nodea | ~nodeb) return null; if (porta) tport = porta; if (portb) hport = portb; eid = gt.graph.maxeid; while (gt.graph.edges[eid]) eid = eid + 1; gt.graph.maxeid = eid + 1; gt.graph.edges[eid] = [ dotty.keys.eid = eid; dotty.keys.tail = nodea; dotty.keys.tport = porta; dotty.keys.head = nodeb; dotty.keys.hport = portb; dotty.keys.attr = copy (gt.graph.edgeattr); ]; edge = gt.graph.edges[eid]; if (~attr) attr = []; for (aid in attr) edge.attr[aid] = attr[aid]; nodea.edges[eid] = edge; nodeb.edges[eid] = edge; edge[dotty.keys.points] = [ 0 = copy (nodea.pos); 1 = copy (nodea.pos); 2 = copy (nodeb.pos); 3 = copy (nodeb.pos); ]; gt.unpackedgeattr (gt, edge); if (show) gt.drawedge (gt, gt.views, edge); if (~gt.noundo) { gt.startadd2undo (gt); gt.currundo.inserted.edges[eid] = edge; gt.endadd2undo (gt); } return edge; }; dotty.protogt.removeedge = function (gt, edge) { local head, tail; if (~gt.noundo) gt.startadd2undo (gt); if (edge.head.attr.support == 1) head = edge.head; if (edge.tail.attr.support == 1) if (head ~= edge.tail) tail = edge.tail; gt.undrawedge (gt, gt.views, edge); remove (edge.eid, edge.head.edges); remove (edge.eid, edge.tail.edges); remove (edge.eid, gt.graph.edges); if (head & tablesize (head.edges) == 0) gt.removenode (gt, head); if (tail & tablesize (tail.edges) == 0) gt.removenode (gt, tail); if (~gt.noundo) { gt.currundo.deleted.edges[edge.eid] = edge; gt.endadd2undo (gt); } }; dotty.protogt.swapedgeids = function (gt, edge1, edge2) { local eid1, eid2; if (edge1.eid == edge2.eid) return; if (~gt.noundo) gt.startadd2undo (gt); eid1 = edge1.eid; eid2 = edge2.eid; gt.graph.edges[eid1] = edge2; gt.graph.edges[eid2] = edge1; remove (eid1, edge1.tail.edges); remove (eid1, edge1.head.edges); remove (eid2, edge2.tail.edges); remove (eid2, edge2.head.edges); edge1.tail.edges[eid2] = edge1; edge1.head.edges[eid2] = edge1; edge2.tail.edges[eid1] = edge2; edge2.head.edges[eid1] = edge2; edge1.eid = eid2; edge2.eid = eid1; if (~gt.noundo) { gt.currundo.swapped.edges[eid1] = edge1; gt.currundo.swapped.edges[eid2] = edge2; gt.endadd2undo (gt); } }; dotty.protogt.removesubtree = function (gt, obj) { local nlist, node, head, nid, edge, eid; if (~gt.noundo) gt.startadd2undo (gt); if (obj.nid >= 0) node = obj; else if (obj.eid >= 0) { node = obj.head; gt.removeedge (gt, obj); if (~gt.graph.nodes[node.nid]) { if (~gt.noundo) gt.endadd2undo (gt); return; } for (eid in node.edges) { edge = node.edges[eid]; if (edge.head == node & edge.tail ~= node) { if (~gt.noundo) gt.endadd2undo (gt); return; } } } else { dotty.message (0, 'bad object type in gt.removesubtree'); return; } nlist = [node.nid = node;]; while (node) { for (eid in node.edges) { head = node.edges[eid].head; if (head ~= node) nlist[head.nid] = head; } gt.removenode (gt, node); remove (node.nid, nlist); node = null; for (nid in nlist) { node = nlist[nid]; for (eid in node.edges) { edge = node.edges[eid]; if (edge.head == node & edge.tail ~= node) { node = null; break; } } if (node) break; } } if (~gt.noundo) gt.endadd2undo (gt); }; dotty.protogt.removenodesbyattr = function (gt, key, val) { local nlist, nid; if (~gt.noundo) gt.startadd2undo (gt); nlist = gt.getnodesbyattr (gt, key, val); for (nid in nlist) gt.removenode (gt, nlist[nid]); if (~gt.noundo) gt.endadd2undo (gt); }; dotty.protogt.removesubtreesbyattr = function (gt, key, val) { local nlist, nid; if (~gt.noundo) gt.startadd2undo (gt); nlist = gt.getnodesbyattr (gt, key, val); for (nid in nlist) if (gt.graph.nodes[nid]) gt.removesubtree (gt, nlist[nid]); if (~gt.noundo) gt.endadd2undo (gt); }; dotty.protogt.groupnodes = function (gt, nlist, gnode, pos, size, attr, keepmulti, show) { local nid, node, elist, eid, edge, nodea, nodeb, inlist, outlist; if (~nlist | tablesize (nlist) == 0) return; if (gnode.attr.support) { dotty.message (0, 'cannot group nodes in a support node'); return; } if (~gt.noundo) gt.startadd2undo (gt); if (~gnode) gnode = gt.insertnode (gt, pos, size, null, attr, show); inlist = []; outlist = []; for (nid in nlist) { if ((node = nlist[nid]) == gnode) continue; elist = []; for (eid in node.edges) elist[eid] = node.edges[eid]; for (eid in elist) { edge = elist[eid]; if (edge.head == node) { nodea = edge.tail; nodeb = gnode; if (~keepmulti) { if (inlist[nodea.nid]) continue; inlist[nodea.nid] = nodea; if (nodea == gnode) outlist[nodea.nid] = nodea; } } else { nodea = gnode; nodeb = edge.head; if (~keepmulti) { if (outlist[nodeb.nid]) continue; outlist[nodeb.nid] = nodeb; if (nodeb == gnode) inlist[nodeb.nid] = nodeb; } } gt.insertedge (gt, nodea, null, nodeb, null, edge.attr, show); } gt.removenode (gt, node); } if (~gt.noundo) gt.endadd2undo (gt); return gnode; }; dotty.protogt.groupnodesbyattr = function (gt, key, val, attr, keepmulti, show) { local nlist, nid, pos, size; pos = null; size = null; nlist = gt.getnodesbyattr (gt, key, val); if (show) for (nid in nlist) { pos = nlist[nid].pos; size = nlist[nid].size; break; } return gt.groupnodes (gt, nlist, null, pos, size, attr, keepmulti, show); }; dotty.protogt.cut = function (gt, obj, set, mode, op) { local clipgt, list, node, nid, edge, eid, clipnode; clipgt = dotty.clipgt; clipgt.graph = copy (dotty.protogt.graph); if (obj.eid >= 0) { # it's an edge list.edges[obj.eid] = obj; node = obj.head; } else if (obj.nid >= 0) { list.nodes[obj.nid] = obj; node = obj; for (eid in node.edges) list.edges[eid] = node.edges[eid]; } else { dotty.message (0, 'unknown object type in gt.cut'); return; } if (set == 'reachable') { list.nodes = gt.reachablenodes (gt, node); for (nid in list.nodes) { node = list.nodes[nid]; for (eid in node.edges) { edge = node.edges[eid]; list.edges[edge.eid] = edge; } } } if (mode == 'support') { for (eid in list.edges) { edge = list.edges[eid]; if (~list.nodes[edge.tail.nid]) { list.support[edge.tail.nid] = edge.tail; list.nodes[edge.tail.nid] = edge.tail; } if (~list.nodes[edge.head.nid]) { list.support[edge.head.nid] = edge.head; list.nodes[edge.head.nid] = edge.head; } } } for (nid = 0; nid < gt.graph.maxnid; nid = nid + 1) { if (~list.nodes[nid]) continue; node = list.nodes[nid]; clipnode = gt.insertnode (clipgt, null, null, node.name, node.attr, 0); if (list.support[nid]) clipnode.support = 1; list.clipnodes[nid] = clipnode; } for (eid = 0; eid < gt.graph.maxeid; eid = eid + 1) { if (~list.edges[eid]) continue; edge = list.edges[eid]; if (~list.nodes[edge.tail.nid] | ~list.nodes[edge.head.nid]) continue; gt.insertedge (clipgt, list.clipnodes[edge.tail.nid], null, list.clipnodes[edge.head.nid], null, edge.attr, 0); } if (op ~= 'cut') return; if (~gt.noundo) gt.startadd2undo (gt); for (eid in list.edges) gt.removeedge (gt, list.edges[eid]); for (nid in list.nodes) if (~list.support[nid] & gt.graph.nodes[nid]) gt.removenode (gt, list.nodes[nid]); if (~gt.noundo) gt.endadd2undo (gt); }; dotty.protogt.paste = function (gt, pos, show) { local clipgt, offset, center, nid, node, eid, edge, nodes; if (~gt.noundo) gt.startadd2undo (gt); clipgt = dotty.clipgt; if (clipgt.graph.rect) center = [ 'x' = (clipgt.graph.rect[1].x + clipgt.graph.rect[0].x) / 2; 'y' = (clipgt.graph.rect[1].y + clipgt.graph.rect[0].y) / 2; ]; else center = pos; offset = [ 'x' = center.x - pos.x; 'y' = center.y - pos.y; ]; for (nid = 0; clipgt.graph.nodes[nid]; nid = nid + 1) { node = clipgt.graph.nodes[nid]; if (node.attr.label == '\N' | ~node.attr.label) node.attr.label = node.name; if (node.support == 1) nodes[nid] = gt.insertnode (gt, [ 'x' = node.pos.x - offset.x; 'y' = node.pos.y - offset.y; ], null, null, [ 'support' = 1; 'shape' = 'circle'; 'label' = ''; 'width' = 0.2; ], show); else nodes[nid] = gt.insertnode (gt, [ 'x' = node.pos.x - offset.x; 'y' = node.pos.y - offset.y; ], node.size, null, node.attr, show); } for (eid = 0; clipgt.graph.edges[eid]; eid = eid + 1) { edge = clipgt.graph.edges[eid]; gt.insertedge (gt, nodes[edge.tail.nid], null, nodes[edge.head.nid], null, edge.attr, show); } if (~gt.noundo) gt.endadd2undo (gt); }; dotty.protogt.startadd2undo = function (gt) { if (~gt.undoarray.level) gt.currundo = (gt.undoarray.entries[tablesize (gt.undoarray.entries)] = []); gt.undoarray.level = gt.undoarray.level + 1; }; dotty.protogt.endadd2undo = function (gt) { gt.undoarray.level = gt.undoarray.level - 1; }; dotty.protogt.undo = function (gt, show) { local entry, n, eid, edge, nid, node, edges; if ((n = tablesize (gt.undoarray.entries)) < 1) return; entry = gt.undoarray.entries[n - 1]; remove (n - 1, gt.undoarray.entries); remove ('currundo', gt); gt.noundo = 1; # hardwire nodes and edges back with the same id's as the originals for (nid in entry.deleted.nodes) { node = entry.deleted.nodes[nid]; gt.graph.nodedict[node.name] = node.nid; gt.graph.nodes[node.nid] = node; node.edges = []; if (show) gt.drawnode (gt, gt.views, node); } for (eid in entry.deleted.edges) { edge = entry.deleted.edges[eid]; gt.graph.edges[edge.eid] = edge; edge.head.edges[edge.eid] = edge; edge.tail.edges[edge.eid] = edge; if (show) gt.drawedge (gt, gt.views, edge); } if (entry.swapped.edges) { if (tablesize (entry.swapped.edges) == 2) { n = 0; for (eid in entry.swapped.edges) { edges[n] = entry.swapped.edges[eid]; n = n + 1; } gt.swapedgeids (gt, edges[0], edges[1]); } else dotty.message (0, 'cannot handle undoing swap of > 2 edges'); } for (eid in entry.inserted.edges) { edge = entry.inserted.edges[eid]; gt.removeedge (gt, edge); } for (nid in entry.inserted.nodes) { node = entry.inserted.nodes[nid]; gt.removenode (gt, node); } gt.noundo = 0; };