view toolboxes/graph_visualisation/lib/lefty/dotty_edit.lefty @ 0:e9a9cd732c1e tip

first hg version after svn

#
# 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);
    node[dotty.keys.rect] = [
        0 = ['x' = pos.x - size.x / 2; 'y' = pos.y - size.y / 2;];
        1 = ['x' = pos.x + size.x / 2; 'y' = pos.y + size.y / 2;];
    ];
    node.draws = gt.simplenodedraw (node, pos, 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;
    gt.unpackedgeattr (gt, edge);
    edge.draws = gt.simpleedgedraw (edge, nodea.pos, nodeb.pos);
    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;
};