From 7ec77fb0d453f5153fc64be647ad943ad6cdbe4c Mon Sep 17 00:00:00 2001 From: erg Date: Mon, 4 Sep 2006 20:19:05 +0000 Subject: [PATCH] Improve description of quadratic attribute behavior. --- doc/FAQ.html | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-) diff --git a/doc/FAQ.html b/doc/FAQ.html index e3c374bd8..88f9328eb 100644 --- a/doc/FAQ.html +++ b/doc/FAQ.html @@ -806,22 +806,27 @@ this as a ranked graph is quadratic in the number of nodes. You probably won't encounter the following, but it is also possible -to construct graphs whose parsing takes quadratic time, by appending -attributes to nodes and edges after the graph has been loaded. -For example: +to construct graphs whose parsing takes quadratic time in the number +of attributes, by appending attributes to nodes and edges after the +graph has been loaded. For example: 
 digraph G {
-    /* really big graph goes here... */
-    n0 -> n1 -> ... -> n999999999;
+    /* really big graph goes here...with N+1 nodes */
+    n0 -> n1 -> ... -> nN;
 
-    n0 [attr0="whatever"]
-    n0 [attr1="something else"]
+    n0 [attr0="whatever",
+        attr1="something else",
     /* and so on with many more attributes */
+        attrM="something again"]
 }
-The addition of attr0 touches every node of the graph. -Then the addition of attr1 touches every node again, and so on. +When an attribute first appears, each object is visited with possible cost +proportional to the number of previously declared attributes. Thus, +the running time for the above would be cN O(M) +for some constant c. If there is any concern about this, the +graph should specify the attributes first before declaring nodes or +edges. In practice, this problem is neglible.

Q. Twopi runs forever on a certain example. -- 2.40.0