hn3000 / canviz Goto Github PK

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 " ];
}

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.

If an image cannot be loaded, there is no debug output or "broken image" 
indication. It looks the 
same as if the image were still in the process of loading.

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

The color scheme files express colors in integer RGB format:

aliceblue:[240,248,255]

But if we convert the colors to hex RGB format we can save up to 5 bytes per 
color:

aliceblue:'f0f8ff'

I originally used RGB format because that's how it's expressed in the Graphviz 
source and I was 
manually munging that file in a text editor to produce the file that is now 
x11colors.js. But since 
the color scheme files are now generated automatically (see issue #1 and issue 
#2) it's trivial to 
convert the data from integer to hex.

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/

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

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

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").

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.

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.

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.

Apparently some operating systems don't have the -t option to mktemp; Ron
Newman showed this error he encountered with the Canviz Makefile:

mktemp: invalid option -- t
Usage: mktemp [-d] [-q] [-u] template

Here's where Ron originally reported this:

http://groups.google.com/group/canviz/browse_thread/thread/9d2c3626bef5fb3f/93c0
00def553dcd0

Here's how one project eliminated the use of mktemp -t from their code, so
I could do something like that in Canviz:

http://www.gelato.unsw.edu.au/archives/git/0504/1616.html

Canviz is using the URL and href attributes to determine what should be
clickable, but there are many other attributes that can be used, which
Canviz needs to support:

edgehref
edgeURL
headhref
headURL
labelhref
labelURL
tailhref
tailURL

Ron Newman initially reported this on the discussion list:

http://groups.google.com/group/canviz/browse_thread/thread/a3d37ed8a0905326

This relates to issue #11.

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.

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

Files that are automatically generated by the Makefile (x11colors.js,
brewercolors.js, graphlist.js, layoutlist.js) should have a message at the
top indicating that.

The generated graphs already have such a message but maybe I want to reword
that as well.

Need a new simple example that shows how one might convert a system using
PNGs and image maps to using Canviz instead.

Each text file in the project should have not only a Subversion $Id$ header
at the top but also a note that the file is part of the Canviz project with
a link to http://www.canviz.org/

The graph form in the sample graphs example appears to be absolutely
positioned; it's supposed to be fixed positioned, and is in IE 7 and
standards-compliant browsers. IE 6 doesn't support fixed positioning. An IE
6-specific stylesheet was added in r235 using a trick I read about to fake
fixed positioning, but it doesn't seem to be working.

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.

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 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 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

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

Create a dot format with some image nodes, calling, say GOODIMAGE and one
for BADIMAGE, and make sure the bad image does not exist.

Running it through graphviz gives a warning:
Warning: BADIMAGE was not found as a file or as a shape library member
Warning: No or improper image=BADIMAGE for node "node2"

The output will be along the lines of (one good node and one bad):
node49 [label="", image=GOODIMAGE, width="1.31", height="0.61",
pos="128,983", _draw_="I 81 962 94 42 6 -Purina "];
node50 [label="", image=BADIMAGE, width="0.25", height="0.25", pos="450,750"];

Previously Canviz drew the graph and simply left a blank spot for the
missing image.  Now it bails on an "Undefined value" error at canviz.js
line 450:
draw_attr_hash = containers[0].drawAttrs;

Since there are no _draw_ commands for the latter, this is where canviz is
getting bogged down.  I'm not sure how deep the architecture changes have
been in the last week, but it has increased the sensitivity too much.

The text labels are now being shown in IE 6, 7, and 8 beta 2 (see issue #8)
when using graphs produced by Graphviz 2.21.20081029.0445 and earlier. But
when they're made by Graphviz 2.21.20081115.1321 or later, IE 6 and 7 show
all text elements mashed up against one another on a single line at the top
of the window, and IE 8 beta 2 shows nothing (doesn't even hide the
"Loading..." div). No similar problem in Safari or Firefox.

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.)

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.

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.

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.

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.

excanvas traditionally converted canvas commands into VML elements Internet 
Explorer for 
Windows understands. There's now a new alternate version of excanvas that 
translates canvas 
commands into Silverlight. It's not part of the latest excanvas 0002 release, 
but is in their repository 
and will presumably be part of excanvas 0003.

The Silverlight version has at least two benefits that I can see: 1. images are 
drawn well (see issue 
#41 for why they're not drawn well with the VML version); 2. lines are drawn 
the correct thickness.

I don't want to use the Silverlight version of excanvas exclusively because 
that would require that 
the Microsoft Silverlight plugin be installed, and one of the properties of 
Canviz I rather like is that 
it doesn't require any browser plugins.

It would be nice if Canviz would determine at runtime whether Silverlight is 
installed, and then 
dynamically load either the VML excanvas.js or the Silverlight excanvas.js, 
using the same dynamic 
loading technique in issue #20. Microsoft shows here how you can determine if 
Silverlight is 
installed:

http://code.msdn.microsoft.com/silverlightjs


Note that all of this is applicable to Internet Explorer on Windows only. All 
other browsers would 
continue to use the native browser canvas as they do now.

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.)

Canviz and Path both need LICENSE.txt files.

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.

In IE 6 and 7 the graph and labels draw properly now (see issue #8) but in
IE 8 beta 2, only the labels draw; the node shapes, edges, etc. aren't
showing up, even using excanvas revision 43 which supposedly includes IE 8
fixes.

If you draw a graph with default colors, like this:

digraph one { node [style=filled]; a }

and render it to xdot, you get _*draw_ commands that use the color names 
"white" (for the graph 
background), "black" (for the node outline and label) and "lightgrey" (for the 
node fill). A mini X11 
color scheme with just these three colors was added to Canviz in issue #14 so 
that you can use 
Canviz without loading x11colors.js.

A problem arises if you specify a different color scheme but still want those 
default colors, like this:

digraph two { graph [colorscheme=reds4]; node [colorscheme=reds4, 
style=filled]; a }

Graphviz still expresses the colors as "white", "black" and "lightgrey", though 
there are no colors by 
those names in the reds4 color scheme.

I proposed that the default colors used by Graphviz should really be "/white", 
"/black" and 
"/lightgrey" (the preceding slash means the color should be looked up in the 
X11 color scheme, 
irrespective of what color scheme has otherwise been selected):

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

In a response that didn't go to the list, Emden revealed that Graphviz actually 
has a special case 
internally for ensuring that the color "black" always resolves regardless of 
color scheme, but that 
special cases for the other two default colors were forgotten. This explains 
why "digraph two" above 
produces the errors "Warning: lightgrey is not a known color" and "Warning: 
white is not a known 
color" but no complaint about the color black.


In Canviz, we should have a similar fallback. If looking up a named color in 
the selected color 
scheme fails, look it up in the internal fallback color scheme. I'm inclined to 
provide the fallback for 
all three colors, not just black. We can change the mini X11 color scheme added 
in issue #14 into 
the fallback color scheme.

When bitmapped images are included in a graph, they don't look great in IE
using the VML-based excanvas script. The image gets scaled down to 75%
(72/96) size, then that gets scaled back up again, resulting in blurring
and pixelation.

A workaround for now is to install Microsoft Silverlight and use the
Silverlight version of excanvas which doesn't have this problem.

I reported this problem to the developers of excanvas:

http://groups.google.com/group/google-excanvas/browse_thread/thread/e72e328ff14d
c90d

I had used BSD xargs on my Mac OS X system and all was well, but if you
have GNU xargs, this problem occurs:


mkdir ./graphs/images
find /mp/share/graphviz/graphs -type f -name '*.gif' -or -name '*.jpg' -or
-name '*.png' -print0 | gxargs -0 -t -n 1 -J % cp % ./graphs/images
gxargs: invalid option -- J
Usage: gxargs [-0prtx] [--interactive] [--null] [-d|--delimiter=delim]
       [-E eof-str] [-e[eof-str]]  [--eof[=eof-str]]
       [-L max-lines] [-l[max-lines]] [--max-lines[=max-lines]]
       [-I replace-str] [-i[replace-str]] [--replace[=replace-str]]
       [-n max-args] [--max-args=max-args]
       [-s max-chars] [--max-chars=max-chars]
       [-P max-procs]  [--max-procs=max-procs] [--show-limits]
       [--verbose] [--exit] [--no-run-if-empty] [--arg-file=file]
       [--version] [--help] [command [initial-arguments]]

Report bugs to <[email protected]>.
make: *** [examples-images] Error 1


Apparently the -J option is not portable.

This problem was initially reported on the discussion group by Ron Newman:

http://groups.google.com/group/canviz/browse_thread/thread/2d67f1049b84172

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.

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.

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.

canviz.js defines these global variables (classes):

Tokenizer
Entity
Node
Edge
Graph
Canviz
CanvizImage

Those names that don't begin with "Canviz" should. Canviz shouldn't claim 
global variable names 
that are so generic.

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.

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.

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

If you check out to Windows, then copy the files to Linux, executable bits
get lost, and the Makefile currently requires that render_example_graph.sh
be executable.

Ron Newman initially reported this on the discussion group:

http://groups.google.com/group/canviz/browse_thread/thread/2d67f1049b84172

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).

Files that are part of an example, and are not files you would need when
using Canviz in your own project, should go into an examples directory, and
possibly then a subdirectory for the specific example, since there will be
more than one example eventually.

Files relating to the existing sample graphs example:

canviz-ie6.css
canviz.css
index.html

Files that used to be part of that example and are now not used, but which
should be used in a more comprehensive future example:

graph.php
image.php