Need suggestions for an algorithm

[megafiddle]

I have a 1000 entry color table represented graphically by a long bar, 1000 pixels wide.
Each table entry is a vertical line 1 pixel wide and 20 pixels high.

Only a relatively small number of colors (minimun 2, maximum 56) are entered by the user.
These are what I call "nodes" and can be placed anywhere within the table. The rest of the
table entries, between the nodes, are calculated by the program. Just beneath the color bar
are small markers which show the actual node positions.

For editing purposes, the nodes are displayed as colored rectangles in a field just below the
color table.

It kind of looks like this, although with graphic elements, not text (and also not to scale):

||||||||||||||||||||||||||||||||||||||||||||||||||||||||    color table
^     ^      ^               ^^                        ^    node position markers

[ ]   [ ]   [ ]   [ ]   [ ]   [ ]                           nodes

What I would like to do is arrange the nodes in their field so that each corresponds as closely
as possible to it's actual table entry just above it. When the node positions are far enough apart,
this can be done exactly. But because the node rectangles are many pixels wide, some of these
rectangles will need to be displaced from the actual position above in the table when the positions
are too close.

The end result should look something like this:

||||||||||||||||||||||||||||||||||||||||||||||||||||||||    color table
^     ^      ^               ^^                        ^    node position markers

[ ]  [ ]    [ ]           [ ]  [ ]                   [ ]    nodes

In the above two illustrations, it was quite easy to do manually. I could also do it easily for some
other arrangement, manually. The main problem though, is that there are a huge number of possible
patterns. I can't think of a way to handle any possible arrangement. Is there something related to this
that could provide a useful algorithm?

I can scan through the nodes and collect all types of data, but I'm not sure what to with it next. It seems
that there is some judgement that needs to be made, and that's where I'm stuck.
How do I translate what I easily did above just by looking at it, into a general procedure?

[Subsonics]

You may be able to represent your nodes as a graph, where the distance between nodes (vertices) is the edge weight. Ideally I assume you would like to center your node directly under it's corresponding marker. With a graph you can examine the distance to adjacent nodes and determine if you need to add an offset to that ideal positioning (directly underneath the marker) or divide the available space amongst closely positioned nodes.

[megafiddle]

You may be able to represent your nodes as a graph, where the distance between nodes (vertices) is the edge weight. Ideally I assume you would like to center your node directly under it's corresponding marker. With a graph you can examine the distance to adjacent nodes and determine if you need to add an offset to that ideal positioning (directly underneath the marker) or divide the available space amongst closely positioned nodes.

Working with the space or distance between the nodes does seem like a better approach.
Is there anything in weighted graph theory that could be useful here? I have a basic idea of what a graph is,
but not familiar with the graph operations.
Also, would your suggestion be similar to my last idea below?

What I have thought of so far:

I believe this cannot simply be done by scaling. I thought of expanding the table positions by a factor of 18
(18 is my node rectangle pitch) to move the table entries at least 18 pixels apart. But now if I try to reduce
the space between them proportionately, certain spaces may reach their minimum limit of 18 and throw off
the ending size of the scaled down field.
The idea here was to add in the required space between nodes and keep everything proportional by expanding
it. Then reduce all the spaces proportionately. But some spaces scale and some don't. Possibly this might work
if several passes are made, redefining the parameters each time a space limit is encountered.

I also thought of simply placing them in position one by one, and adjusting them as necessary. But when room
needs to be made for the new node, a decision needs to be made concerning which ones to move. Not sure
how to determine this at that point in the procedure. Possibly the number of different cases that need to be handled
is not really that large. I have to think about this one some more.

My only other idea is some type of mutiple pass procedure that looks at errors from best position and repeats the
adjustments until the overall errors are minimum. This could be a possibility if I can figure out a way to weight the
errors to get groups to be centered, if possible.

[Subsonics]

Working with the space or distance between the nodes does seem like a better approach.
Is there anything in weighted graph theory that could be useful here? I have a basic idea of what a graph is,
but not familiar with the graph operations.

A "weight" can mean anything you want it to in order to fit a graph onto your problem, in this case distance in pixels would be the edge weight. It's not necessarily graph operations that could be useful (as far as I know, there may be graph algorithms that readily solves your problem), but the representation of your nodes as a "graph". I put that in quotes since it's basically a list, but you could easily create a data structure that holds a reference to a node and it's it's distance to adjacent nodes in pixels. After that step, knowing the minimum distance required you could easily update it by moving your node representations in your graph until the minimum space property is fulfilled. You could try to render after the new positioning and experiment with different ways of allocating/dividing space for competing nodes.

Also, would your suggestion be similar to my last idea below?

Not sure I follow you completely but the last paragraph seems to be most similar afaik.

[megafiddle]

A "weight" can mean anything you want it to in order to fit a graph onto your problem, in this case distance in pixels would be the edge weight. It's not necessarily graph operations that could be useful (as far as I know, there may be graph algorithms that readily solves your problem), but the representation of your nodes as a "graph". I put that in quotes since it's basically a list, but you could easily create a data structure that holds a reference to a node and it's it's distance to adjacent nodes in pixels. After that step, knowing the minimum distance required you could easily update it by moving your node representations in your graph until the minimum space property is fulfilled. You could try to render after the new positioning and experiment with different ways of allocating/dividing space for competing nodes.



Not sure I follow you completely but the last paragraph seems to be most similar afaik.

Ok, thanks. I'm going to try that. And rendering to observe the progress is a good idea.

[brewbuck]

Implement a repulsive force between the markers which drops to zero beyond a certain distance, and an attractive force between each marker and its corresponding entry in the color table. Minimize the total potential energy. Play with the parameters (basically, the strength of the two kinds of forces) until you get a pleasing result.

[megafiddle]

Implement a repulsive force between the markers which drops to zero beyond a certain distance, and an attractive force between each marker and its corresponding entry in the color table. Minimize the total potential energy. Play with the parameters (basically, the strength of the two kinds of forces) until you get a pleasing result.

That's an interesting idea also. Could be pretty neat if the nodes were modeled as cellular automata. They could adjust themselves.
(I have also been working on another program, John Conway's "Life". It gave me that idea).

Anyway, still working on it.

[megafiddle]

I came up with something that seems to work.

The ideas from subsonics and brewbuck are more interesting approaches, but I could not find a way to impliment them.
The main problem was anticipating and handling the various patterns that could occur. Things became much simpler
when I handled the lower and upper ends of the node field independantly from the inner region.
Groups at the lower and upper ends cannot be centered as groups in the inner region can be. At best you can only
left justify or right justify the groups. The node field ends at the lower and upper limits of the color table.
(A group is any sequence of nodes which are too close to each other to align with their actual positions; they would
have to overlap. So they need to be separated, or expanded)

After the ends are aligned, the inner groups (if any) are all handled in a consistant way. The groups will be centered
and if a group impinges on an adjacent node or group, it will merge with it and form a new larger group on the next
pass of the algorithm.

It looks like this:

void setnodefields(void)
{   int n,  n1, n2, gsize, center, g1, g2, x;

    for( n = 0; n < nnodes; n++ )                                       // set initial field positions to actual table positions
        nodef[n] = nodep[n];

    g1 = 1;
    while( g1 )                                                 // repeat until all groups expanded and aligned
    {   n = 1;
        n1 = 1;
        while( nodef[n]-nodef[n-1] <= NODEPITCH && n < nnodes-1 )       // align any group at left end
        {   nodef[n] = nodef[n-1]+NODEPITCH;
            n1 = ++n;
        }

        n = nnodes-2;                                               // align any group at right end
        n2 = nnodes-2;
        while( nodef[n+1]-nodef[n] <= NODEPITCH && n > 0 )
        {   nodef[n] = nodef[n+1]-NODEPITCH;
            n2 = --n;
        }

        n = n1;
        g1 = 0;
        while( ! g1 && n < n2 )                                     // locate internal group
        {   if( nodef[n+1]-nodef[n] < NODEPITCH )
            {   g1 = n;
                while( nodef[n+1]-nodef[n] < NODEPITCH && n < n2 )
                    g2 = ++n;

                gsize = g2+1-g1;                                    // expand and center group
                center = ( nodep[g2]+nodep[g1] )/2;
                nodef[g1] = center-( gsize*NODEPITCH-NODEGAP )/2;
                for( n = g1+1; n <= g2; n++ )
                    nodef[n] = nodef[n-1]+NODEPITCH;
            }

            n++;
        }
    }

    for(n = 0; n < nnodes; n++)                                // set node rectangles
    {   x = n*NODEPITCH;
        nsubfield[n].top = 0;
        asubfield[n].top = NODEHEIGHT/2;
        asubfield[n].bottom = NODEHEIGHT;


        if(link[n] == LINK1)
            asubfield[n].left = nsubfield[n].left = x+2;
        else if(link[n] == LINK2)
            asubfield[n].left = nsubfield[n].left = x-2;
        else
            asubfield[n].left = nsubfield[n].left =  nodef[n];

        asubfield[n].right = nsubfield[n].right = nsubfield[n].left+NODEWIDTH;

        if(altnode[n])
            nsubfield[n].bottom = nfield.top+NODEHEIGHT/2;
        else
            nsubfield[n].bottom = nfield.top+NODEHEIGHT;
    }
}

[brewbuck]

Nice work.

[megafiddle]

Thanks!

It does have your repulsive force to the extent that it causes a minimum separation between nodes.
The attractive force is limited though to the very end nodes in a group, not so much the individual
nodes within a group. More of a simple "centering". It does work out nicely though for isolated
symmetrical groups.

Also it incorporates Subsonic's ideas to an extent,, analyzing the spacing.

Anyway, it seems to work without problems.

[megafiddle]

Ok, doesn't quite work without problems.

While moving the nodes around to test it further, certain patterns can cause it to oscillate between two different alignments.
Fix was simple though - changed this:

while( nodef[n+1]-nodef[n] < NODEPITCH && n < n2 )

to this:

while( nodef[n+1]-nodef[n] <= NODEPITCH && n < n2 )