easytiger / canviz Goto Github PK

We're still using Prototype 1.5.0. Version 1.5.1 was already loaded into the 
repository, but we need 
to update to 1.6.x for issue #20.

All occurrences of Hash#merge will need to be replaced with Hash#update.

Some time in the Graphviz 2.21.x development cycle the official extension for 
Graphviz files 
changed from .dot to .gv and the example filenames changed. generate.sh and 
index.php need to 
be updated to recognize these files. Canviz should support both .dot and .gv 
extensions.

Graphviz documentation talks about nodes and edges having "attributes" but in 
the Canviz code we 
call them "parameters". Canviz should use the same basic terminology as the 
Graphviz 
documentation.

http://graphviz.org/doc/info/lang.html

We go to the effort of making the canvas graphics context a parameter to the 
Graph initialize() 
method, but then the Graph draw() method references divs named "graph_texts" 
and 
"graph_container". That's not good. It certainly prevents having multiple 
graphs on one page, and 
there's no reason we should prevent that.

Perhaps it would be best to make the caller supply just the name of an empty 
div when making a 
new Graph. Then Canviz would take care of creating the canvas and the text divs 
inside it.

Canviz currently only handles whitespace between HSV color components (regex 
\s+). The docs say 
we need to match the regex [, ]+ but it also says "separated by whitespace or 
commas". I think we 
should match the regex [\s,]+.

http://graphviz.org/doc/info/attrs.html#k:color

The Graphviz documentation says color names are case-insensitive, but Canviz is 
currently treating 
them case-sensitively.

Solution: All the color names in gvcolors.js are specified in lowercase, so 
convert the graph's color 
names to lowercase before looking them up in the gvcolors array.

Canviz doesn't support the HREF/URL dot attribute to allow clicking things in 
the graph. I've 
received several patches implementing this, but they all go the route of adding 
an "a" tag to the 
text divs. This means all click regions are rectangular, and you must click on 
the text label itself.

But I'd like to be able to have the click region for nodes be the shape of the 
node, and for edges 
I'd like to be able to click on the edges themselves. This will require some 
involved hit-testing 
code in path.js. I hope it will be fast enough. Here is some material I have 
been reading on this 
topic:

Determining if a point is in a polygon:

http://en.wikipedia.org/wiki/Point_in_polygon
http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
http://alienryderflex.com/polygon/

Determining if a point is on a line or curve:

http://msdn.microsoft.com/en-us/library/ms969920.aspx

Following on the heels of issue #30, Canviz can't find a graph's images to
use them when drawing. Any images found during "make examples" need to be
copied to the graph images directory for use by Canviz.

(None of the existing sample graphs use images, but if you add a graph that
does, then you run into this problem.)

If a graph uses an image multiple times, only the first occurrence of the image 
gets drawn. I think I 
over-optimized something.

Support all the colors listed here:

http://graphviz.org/doc/info/colors.html

We currently only have the X11 color scheme in gvcolors.js. Should probably put 
the ColorBrewer 
colors into a new JavaScript file brewercolors.js rather than including them in 
gvcolors.js, so 
gvcolors.js doesn't get too large.

There should be an automatic way to convert from lib/common/brewer_colors to 
brewercolors.js, 
via a script. Implement #1 first, but the format of brewer_colors is different 
from the format of 
color_names so it will need a different script.

Note the need to include their licensing verbiage in our documentation.

dot/xdot files can contain more than one graph, as in the regression test graph 
multi.gv in 
(graphviz-src)/rtest/graphs. Canviz draws both graphs, one on top of the other. 
Graphviz itself 
renders only the first graph, when using -Tpng or -Tpdf, so that seems like a 
good thing to do in 
Canviz as well for now.

Color names can be preceded by one or two slashes, and a color scheme name can 
be placed 
between the two slashes. See the documentation:

http://graphviz.org/doc/info/attrs.html#k:color

Fix issue #2 first.

Some colors in the X11 color scheme (invis, none and transparent) are 
non-opaque (are, in fact, 
totally transparent) but we're not recording that in gvcolors.js.

I made gvcolors.js by manually munging the file lib/common/color_names from the 
Graphviz 
source in a text editor. Write a script to do so automatically so gvcolors.js 
can be regenerated if 
needed.

There's a mistake in the handling of non-ASCII strings in the tokenizer. The 
xdot format tells us 
how many bytes long a string will be, but I hand that count to the substr 
function, which counts in 
characters, not bytes. I also wrongly named our variable "chars" instead of 
"bytes". (Actually the 
mistake was in the Graphviz documentation which said the xdot format counted 
characters; I 
submitted a patch to fix the documentation.)

None of the sample graphs exhibit the problem. You only see the problem if you 
have a single label 
which results in more than one text draw command, such as a multiline label, or 
a record or HTML-
like table. Here's an example:

digraph utf8 {
    a [label="ää\nb"]
}

Result in Canviz:

unknown token 14.000000

This was originally reported to me by email by Jan Wielemaker in November 2007 
and he provided a 
patch in his repository:

http://gollem.science.uva.nl/git/ClioPatria.git?
a=commitdiff;h=1669b252b25b6e75ced28be39b0449e9d13a62d3

I can't find any JavaScript string functions that work on bytes instead of 
characters so the method 
proposed in this patch seems to be the way to go.

Using named colors in graphs that will be drawn by Canviz is not recommended 
because then you 
must include the color lookup table gvcolors.js which is an extra thing that 
needs to be sent to the 
browser. Better to not use named colors. But Graphviz itself uses the color 
names "black" and 
"white" all over the graph even though you didn't tell it to. So that you can 
actually use Canviz 
without loading gvcolors.js, we should define a tiny 2-entry gvcolors array in 
canviz.js itself, just 
for black and white.

The regression test graph cairo.gv in (graphviz-src)/rtest/graphs doesn't 
render in Canviz. It's 
completely blank. Looks like the reason is that my parser skips over everything 
up to whitespace 
and an open square bracket to find the beginning of the attributes, and 
cairo.gv's node names 
happen to contain whitespace followed by an open square bracket. We need to 
handle this more 
correctly.

Drawing the graph to a single canvas is fine for small and medium-sized graphs, 
but if the graph is 
thousands of pixels tall and/or wide, the computer slows to a crawl as the 
browser tries to allocate 
the tons of virtual memory it needs to make such a huge canvas. One solution 
might be to slice the 
graph into fixed-size tiles of say a few hundred pixels square, where each tile 
is a canvas, and 
create only those canvases necessary to draw the visible portion of the graph. 
As you scroll around 
to reveal other portions of the graph, those canvases get created and drawn, 
while the canvases you 
scrolled off the screen get deleted. This would be similar to the method Google 
Maps appears to 
employ.

Canviz doesn't work so well in Internet Explorer right now. Last I heard, in IE 
6 and 7, you get the 
graph drawn, but no text overlays; and in IE 8, you get the text but no graph.

See if it helps to update from ExplorerCanvas 0001 to 0002 (it's already been 
imported into 
/vendor/excanvas in the repository).

It's possible MooCanvas may work better than ExplorerCanvas. However MooCanvas 
requires 
MooTools, and Canviz already uses Prototype. I'm not sure how MooTools and 
Prototype compare, 
or if they would interfere with one another.

Canviz is treating the xdotversion graph attribute as if it were a floating 
point number, but it should 
be treated as a dotted decimal.

https://mailman.research.att.com/pipermail/graphviz-interest/2008q4/005721.html

The current example uses PHP on the server side to build the list of graphs and 
to compress the 
xdot files, but this introduces complexity (users must set up a web server with 
PHP support) and 
confusion (some people think Canviz requires PHP).

Change the example so it's pure JavaScript. generate.sh can write the list of 
graph names and 
engine names to a JavaScript file. And we can ignore compression for the sake 
of this example; that 
can be shown again in a more advanced example in the future.

Canviz isn't just for showing static graphs. It's supposed to be used to build 
graph editors, where a 
graph evolves as someone edits it. Nodes and edges get created and deleted, and 
at each stage, 
Graphviz rerenders it, possibly drastically repositioning existing elements. If 
the new graph revision 
is simply drawn to the screen, replacing the old graph revision, it's easy to 
lose track of elements 
when such repositioning occurs. There should be a way for Canviz to animate 
between revisions, 
smoothly moving common nodes and edges, fading in new elements and fading out 
deleted ones.

Some time in the Graphviz 2.21.x development cycle, the xdot output changed 
subtly. There is now a space before each comma in the attribute lists of nodes 
and edges, and Canviz isn't robust enough 
to handle that. Canviz should match the regex [\s,]+ in between attributes 
instead of ,\s* as currently.

Input:

digraph G { a }

Output with Graphviz 2.20.2:

digraph G {
    node [label="\N"];
    graph [bb="0,0,54,36",
        _draw_="c 5 -white C 5 -white P 4 0 0 0 36 54 36 54 0 ",
        xdotversion="1.2"];
    a [pos="27,18", width="0.75", height="0.50", _draw_="c 5 -black e 27 18 27 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 5 -black T 27 10 0 5 1 -a "];
}

Output with Graphviz 2.21.20080918.0445:

digraph G {
    node [label="\N"];
    graph [bb="0,0,54,36",
        _draw_="c 5 -white C 5 -white P 4 0 -1 0 36 55 36 55 -1 ",
        xdotversion="1.2"];
    a [pos="27,18" , width="0.75" , height="0.5" , _draw_="c 5 -black e 27 18 27 18 " , _ldraw_="F 14.000000 11 -Times-Roman c 5 -black T 27 10 0 5 1 -a " ];
}

Units in xdot output are measured in PostScript points, which are always 72 
dpi. Graphviz produces 
PNG and other bitmapped output at 96 dpi by default. Canviz is supposed to 
replace using PNGs in 
web pages, and I wanted developers to have as seamless a transition as 
possible, so there's this 
curious variable "this.systemScale = 4/3" which should more properly be written 
"this.systemScale = 
96/72" to convert 72-dpi points to 96-dpi pixels so that Canviz output matches 
the size of PNG 
output.

But the graph could specify a different dpi. PNG output respects this setting 
(rendering a larger 
graph for larger dpi values) so we should do the same in Canviz.

If the xdot file has DOS line endings it doesn't get rendered at all. Only xdot 
files with UNIX line 
endings get rendered.

Jan Wielemaker reported this to me by email on November 29, 2007 and provided a 
patch in his 
repository:

http://gollem.science.uva.nl/git/ClioPatria.git?
a=commitdiff;h=1069bfc01ad81ee7e747ca210c88482ff61a2ded

The generate.sh script which renders the Graphviz sample graphs into xdot 
format for each layout 
algorithm should be rewritten as a Makefile, so that it can be run with "make 
examples". The 
motivation is to allow multiple graphs to be generated in parallel using the 
"-j" make option (e.g. 
"make -j 2 examples").

The docs say the pairs of hexadecimal digits that make up RGB and RGBA colors 
can be separated 
by whitespace.

http://graphviz.org/doc/info/attrs.html#k:color

Canviz and Path both need LICENSE.txt files.

It's possible to change the current color scheme by using the colorscheme 
attribute.

http://www.graphviz.org/doc/info/attrs.html#d:colorscheme

But it's tricky to do with the way Canviz is currently written, because in the 
parse() method it just 
gathers draw commands, but the color names in the draw commands depend on 
knowing the 
current color scheme, which is not encoded into the draw commands and 
furthermore can be 
different for nodes, edges, clusters, and the graph.

This is related to issue #2 and issue #3 (which will both be much easier to 
implement than this).

Currently if you want to use named colors in a graph, you have to know this 
ahead of time and 
include x11colors.js and/or brewercolors.js. It would be nicer if Canviz would 
dynamically load the 
appropriate color scheme file if necessary for the graph being rendered.

A method for dynamically loading scripts is described here:

http://www.codehouse.com/javascript/articles/external/

Currently Canviz parses the xdot file and stores all _*draw_ commands in a flat 
array, which is 
later drawn to the canvas. Franck Tabary suggested that the graph 
representation should persist 
in memory as JavaScript objects.

http://groups.google.com/group/canviz/browse_thread/thread/9d2c3626bef5fb3f/1bf4
6c265f
0ce778

The suggestion was based on the misperception that Canviz does the graph layout 
itself; in fact 
Graphviz does the layout, encodes node positions and sizes and draw commands 
into the xdot 
file, and Canviz just dumbly reads that and draws what the file says to draw. 
But having the 
graph representation in memory is still a good idea because:

 * all the attributes would be there in memory, which those writing a graph editor would 
probably need
 * we could take advantage of attributes which aren't encoded into the _*draw_ commands, like 
the colorscheme attribute; that would let us fix issue #13
 * we would have a structure in memory which lets us associate e.g. node URLs with the draw 
commands used to draw the node; that would get us further on issue #11
 * it's probably a necessary first step to being able to do animated transitions between graph 
states; see issue #26

When rendering the sample graphs with "make examples", if any graphs
reference images, those aren't found. The headers of the rendered files
contain warnings like:

# Warning: No such file or directory while opening foo.png
# Warning: No or improper image="foo.png" for node "a"

(None of the existing sample graphs use images, but if you add a graph that
does, then you run into this problem.)