Computer: Algorithm
history graphs   (+12)  [vote for, against]
replace linear undo/redo history chains with a directed graph

The motivation for this idea came from editing drum patterns in rebirth, but it would apply to any "creative" application eg. Photoshop, Cubase, etc which provides "unlimited undo/redo".

Let's say I'm using a drum pattern editor. I'm playing with a drum pattern P, looking for new patterns. I make a modification that gives me pattern P1, which I don't like. So I undo back to P then make a modification which gives me pattern P2 which I like better and evolve to P3, P4 etc etc. But P1 has now disappeared.

With a history graph, the system would hold onto P1. At any point (say a few days later), I could ask for a visual representation of the history graph, which would show me a bifurcation at (P). I could then go back to P1, think "hey this ain't so bad", and generate a whole family of beats from it that would have been lost otherwise.

You could do this manually by saving files in the application, but this is clunky so most of the time you don't do it, especially when you don't like the current pattern. A system which did this for you automatically, and presented the history graph in a nice visual form, would help creative exploration. Sure, you do have to store more data, but we have bigger hard drives these days, and the system can always delete stuff past a certain date.
-- bumhat, Sep 09 2002

is this your link, oliverfuture? http://www.apple.com/shake/
[po, Sep 27 2006]

<Foghat>Sloooooooooooww Riiiiiiiiiiiiiidddde</Foghat>
-- thumbwax, Sep 09 2002


Some applications have what is known as a "history stack." The two that come to mind are Discreet's 3D Studio Max and Side Effects Houdini (and, prior to that, "PRISMS"). What the history stack allows a user to do is to, in essence, rearrange the construction history from a given point on. By rearrange I mean, if, at some point in the work flow, the user realizes that they should have done action Z before Y, well, they can go to the history stack and graphically rearrange action Z to come before action Y. All actions subsequent to that rearrangement are then recalculated to take into account the effect of re-ordering the workflow.

While these history stack mechanisms are not depicted as graphs they sound much like what you are describing in that they serve a similar persistant history/revision role.
-- bristolz, Sep 09 2002


Workflow reordering isn't similar to history graphs imho - it still works with a linear chain. The point of a graph is to help you in your search across the space of possible patterns, by remembering all search points and the relationships between them.
-- bumhat, Sep 10 2002


Ah, okay . . . sorry. I think I get it now. You are interested in preserving, and being able to freely recall, the context of a given moment--ANY given moment--in the course of creative creating.
-- bristolz, Sep 10 2002


I don't think of bloatware as a problem. I also think that complete contextual histories of a document or project will be a matter of course not too far in the future. I just don't think the data required to record the actions taken would be all that unwieldy.

Implemented as described here it might be a little geeky but the sentiments, the problems that a complete "paper trail" history solves are likely most useful for the non-geeks; those people who just want software to do the right thing and part of doing the right thing could be complete histories.

Of course, I am often wrong . . . .
-- bristolz, Sep 10 2002


I don't doubt the willingness of developers to do anything they set out to do. Seldom are people more tenacious than a developer in the throes of solving a problem.

Storage is cheap. Elegance is over-rated.
-- bristolz, Sep 10 2002


The initial implementation of this will (when I get the time) be in a program called mutator, a beat pattern editor like fruityloops or rebirth. Besides the normal editing tools, it will have "mutate" and "mate" operators, and use a history graph to let you develop "families" of beats and jump around them quickly. With a beat pattern editor, the data is so small that this can be done without significant bloat.

The generalisation to other applications is a little more difficult. I don't think all applications actually *need* such a feature - and UnaBubba, I'm definitely in your corner regarding bloatware. The key is to make such a system controllable by the user so it does what they need, and system resource use specs are part of this. But there are a number of ways to compress history graphs (storing differences rather than complete states, lossless compression of image data, pruning). I guess the interface considerations will be different for every application. I can see it being really useful for video editing software for example, with a different interface to the beat editor.
-- bumhat, Sep 10 2002


I don't see that this feature should require any great amount of storage or processing power. Effectively all your talking about is recording keystrokes to create a record of each session and then having an applet that enables you to run through the record and stop it at any point. Doesn't seem that complex to me.
-- DrBob, Sep 10 2002


sheesh, when you put it like that ... ;-)
-- bumhat, Sep 10 2002


Problem with DrBob's method would occur if you changed the program so that a particular keypress had a different effect. It would be better (and equally simple) to store some representation of the actual commands you invoked. This would be light on space, but time-inefficient as it would take time to roll forward from the initial state to an arbitrary state node. But of course the states could be cached.
-- bumhat, Sep 10 2002


//if you changed the program//

bumhat, if you mean by that 'hacking the software to make a keystroke mean something different to the program' then you're right only in so far as the applet that recorded and played back your keystrokes would have to be an entirely seperate program from your application software. But you'd need a program that can snapshot itself in order to get around that particular problem. Which means having, in effect, a seperate copy of the software for every hack that you've carried out.
If, on the other hand, you mean 'use a function from within the application to make keystrokes have a different meaning at different times' then it shouldn't be a problem because your recorded keystrokes would set the context automatically.

The closest example to this that I can give you is the macro recording function in Excel and other spreadsheets which you can switch on to record your keystrokes as a small Visual Basic program. VB can also be used to launch other applications so, I guess, in theory, you should be able to create a stand alone VB program that can record all of your keystrokes from the moment that you boot into Windows (or whatever). In fact, I wouldn't be surprised if such a thing existed already - there's probably a copy secretly installed on everyone's PC by the CIA.
-- DrBob, Sep 11 2002


I'm all in favor of this, if you only store the instruction sequences that get you to each point, then you only need a total snapshot of the system at the begining in order to recreate any decision point (unless you were calling external data at any time). Wish I had this for web searches!
-- pfperry, Sep 11 2002


Opera *snicker*
-- thumbwax, Sep 11 2002


a great idea - I've subconsciously wished for something like this - mainly in IE and Photoshop.

An longtime 3DSMax user, I can confirm that a their "stack" (and editable list of modifications e.g. "box, stretch, divide, warp") is not the same thing. Further it can make trouble - in the form of interdependent edits that cause crashes.

Undo/Redo is better. It's more understandable to artists - it's linear, and familiar.

I have sometimes wished for a history graph, usually when I'm at a major juncture in editing, and want to try several variations. I usually save a different filename, then work through the variations, using undo for the failures and saving another name for the possible successes. This system works OK though it does generate a few files - without good naming conventions, my working directory gets very confusing. I use this system in Photoshop, Max, and audio editing tools.

I wonder: would the history graph be worth the complexity it would add to the interface? It could - I'd have to try it to know.
-- white, Sep 11 2002


I'm going to join the Luddites on this one. I haven't even really understood why it generated this plausible discussion. If you're really that serious about a project, why can't you keep saving different states? It's not like you enter a wild supra-conscious frenzy designing drumbeats or whatever where Shift+Ctrl+S would just *kill* your flow.
-- General Washington, Sep 12 2002


// why can't you keep saving different states //

Because, you don't. You are at A. You think, "I want to get to B". You try to get to B and get to C. You think, SHIT. UNDO. You try to get to B again and get to D. You think, SHIT, UNDO. again, get to E. ad infinitum. Finally you think, right, we've got to Z, maybe C wasn't so bad. But what was C ??? Without history graph, tough shit, C is gone - you weren't thinking about saving so it didn't get saved. With history graph, they *all* get saved automatically so maybe you discover something new. Because now you can compare C with D with E .. etc

Point is, we're trying to make it easy to search a space of possible "solutions". I.e., let you do breadth-first instead of depth-first searches.
-- bumhat, Sep 12 2002


I have no idea how the fsck this would work, but i'm voting for it.
-- sadie, Sep 12 2002


// I wonder: would the history graph be worth the complexity it would add to the interface? It could - I'd have to try it to know. //

This is the interesting part - where an idea gets actually implemented and developed. When I get through writing mutator I'll post a copy for people to play with...
-- bumhat, Sep 13 2002


Ah, [UnaBubba], the space is going to store the raster info (huge) and the state info (small). All that is needed for history is the instructions for the app to re-create everything at a given point in time. Such an app used to exist, I can't remember what it was called, but it was intended as a photo editor and compositor designed to work on high resolution images back in the days when computers were slow and RAM was really, really expensive (about 6-8 years ago).

The model for this app was that you would work on a low resolution (screen resolution) proxy of the real image and when you were all done you would tell the app to go do whatever you did to the proxy image to the real, hi-rez image. In essence rendering the real results at 300, 600 or in the case of art books, 1200dpi. In order for the app to do this work, it had to record and store a complete history of all of the actions you had taken in the course of editing the photo and replay them at render time (presumably while you were off sleeping or whatever).

I think that Macromedia sold this product for a while. Oh, I remember what it was called now: 'X-Res."
-- bristolz, Sep 13 2002


It's not really a graph, it's a tree structure, very similar to a cactus stack (http://c2.com/cgi/wiki?CactusStack). I vaguely recall reading a paper with this idea, but unfortunately I have been unable to recover the reference. (yeah, yeah, I know that is rather unhelpfull...) The core problem, as I see it, isn't memory usage, it is what is hidden in the phrase "a visual representation of the history graph". When I use regular undo/redo I am remembering what I have done recently, but to navigate in a tree/graph I will need some representation of what I did. The question then becomes whether the representation will evoke my memory properly.
-- CheapTalk, Jul 27 2004


for 2d graphics, Shake http:// www.apple.com/shake/ effectively does this. In the workflow, you explicitly build a graph; dead ends represent early versions. Ironically one of the most common complaints about it is its flakey "undo". Otherwise it has no equal.
-- oliverfuture, Sep 26 2006



random, halfbakery