[Dot] Spinning (also forum does not seem to be accepting questions.)

ianamason commented 7 years ago

So I tried posting this on the graphviz.org forum but to no avail. The connection always timed out. So I will repost it here.

We have a graph (yes I know it is large) that is not too much bigger than other graphs we render relatively painlessly. I have tried limiting all the things I can find to limit but alas dot appears to spin.

DotIssues iam$  dot -v -Ln3 dotIn.xdot -Txdot -o dotOut.xdot
dot - graphviz version 2.39.20141015.0446 (20141015.0446)
libdir = "/usr/local/lib/graphviz"
Activated plugin library: libgvplugin_core.6.dylib
Using render: xdot:core
Using device: xdot:xdot:core
Activated plugin library: libgvplugin_dot_layout.6.dylib
Using layout: dot:dot_layout
The plugin configuration file:
    /usr/local/lib/graphviz/config6
        was successfully loaded.
    render  :  dot fig map pic pov ps quartz svg tk vml xdot
    layout  :  circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopi
    textlayout  :  textlayout
    device  :  bmp canon cgimage cmap cmapx cmapx_np dot eps exr fig gif gv icns ico imap imap_np ismap jp2 jpe jpeg jpg pct pdf pic pict plain plain-ext png pov ps ps2 psd sgi svg svgz tga tif tiff tk vml vmlz xdot xdot1.2 xdot1.4
    loadimage   :  (lib) bmp eps gif jpe jpeg jpg pdf png ps svg
pack info:
  mode   undefined
  size   0
  flags  0
  margin 8
pack info:
  mode   node
  size   0
  flags  0
fontname: unable to resolve "Times-Roman"
network simplex:  1289 nodes 8029 edges maxiter=2147483647 balance=1
network simplex: 100 200 300 400
network simplex: 1289 nodes 8029 edges 419 iter 0.03 sec
Maxrank = 73, minrank = 0
mincross: pass 0 iter 0 trying 0 cur_cross 7322238 best_cross 7322238
mincross: pass 0 iter 1 trying 0 cur_cross 6052740 best_cross 6052740
mincross: pass 1 iter 0 trying 0 cur_cross 5245322 best_cross 4648732
mincross: pass 1 iter 1 trying 1 cur_cross 5721246 best_cross 4648732
mincross: pass 2 iter 0 trying 0 cur_cross 4648732 best_cross 4648732
mincross: pass 2 iter 1 trying 1 cur_cross 5818126 best_cross 4648732
mincross temp: 4648732 crossings, 98.92 secs.
network simplex:  213718 nodes 323873 edges maxiter=3867 balance=2

It sits at this last line for as long as I have the patience to wait (currently a couple of hours). We are not that fussy about the layout, but we are addicted to xdot output, because we use it to draw our graphs in an interactive java environment, in particular the nodes and edges.

Any suggestions? (other than me checking out the GitHub repo and seeing what has got its knickers in a knot). I put the graph in question here:

http://www.csl.sri.com/users/iam/dotIn.xdot

magneticnorth commented 7 years ago

network simplex: 213718 nodes 323873 edges maxiter=3867 balance=2 It sits at this last line for as long as I have the patience to wait (currently a couple of hours). We are not that fussy about the layout, but we are addicted to xdot output, because we use it to draw our graphs in an interactive java environment, in particular the nodes and edges.

Any suggestions? (other than me checking out the GitHub repo and seeing what has got its knickers in a knot). I put the graph in question here:

http://www.csl.sri.com/users/iam/dotIn.xdot http://www.csl.sri.com/users/iam/dotIn.xdot spline routing problem?

wonder if this is related to recent work on eliminating compile time warnings about floating point conversions? try an older version?

ianamason commented 7 years ago

OK so I spoke to soon. It eventually finished.

...
network simplex:  213718 nodes 323873 edges maxiter=3867 balance=2
network simplex: 100 200 300 400 500 600 700 800 900 1000
network simplex: 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000
network simplex: 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000
network simplex: 3100 3200 3300 3400 3500 3600 3700 3800
network simplex: 213718 nodes 323873 edges 3867 iter 11918.03 sec
routesplines: 10729 edges, 218765 boxes 23.70 sec
Using render: xdot:core
Using device: xdot:xdot:core
gvRenderJobs temp: 0.82 secs.

But I would really like to be able to speed it up a bit.... 3.3 hours is a tad slow UI wise.

The three hour run is the uncommented version. I have yet to succeed with the one commented out (but didn't let it run that long).

/* graph [xdotversion=1.2, rankdir=TB, nslimit=3, nslimit1=3, maxiter=3, mclimit=0.1, searchsize=5]; */
graph [xdotversion=1.2, rankdir=TB, nslimit=3, mclimit=0.1];

magneticnorth commented 7 years ago

Yes, it seems to be hung in the network simplex solver for the X coordinate phase.

This is a bit unusual. It has nothing to do with floating point arithmetic.

We sometimes wondered if it was possible for the network simplex solver to get stuck in a phase where it would swap a lot of tight tree edges without making any progress, but never found an example. (Until now?)

On Nov 18, 2016, at 8:18 PM, Ian A Mason notifications@github.com wrote:

OK so I spoke to soon. It eventually finished.

... network simplex: 213718 nodes 323873 edges maxiter=3867 balance=2 network simplex: 100 200 300 400 500 600 700 800 900 1000 network simplex: 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 network simplex: 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 network simplex: 3100 3200 3300 3400 3500 3600 3700 3800 network simplex: 213718 nodes 323873 edges 3867 iter 11918.03 sec routesplines: 10729 edges, 218765 boxes 23.70 sec Using render: xdot:core Using device: xdot:xdot:core gvRenderJobs temp: 0.82 secs. But I would really like to be able to speed it up a bit.... 3.3 hours in a tad slow UI wise.

The three hour run is the uncommented version. I have yet to succeed with the one commented out (but didn't let it run that long).

/* graph [xdotversion=1.2, rankdir=TB, nslimit=3, nslimit1=3, maxiter=3, mclimit=0.1, searchsize=5]; */ graph [xdotversion=1.2, rankdir=TB, nslimit=3, mclimit=0.1]; — You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-261689813, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz3zFNM5CSiU6_a22oCPUvB1bggPyks5q_mqigaJpZM4K3IQg.

ianamason commented 7 years ago

The graphs are generated by inductively closing a set of biological reaction rules. So the rule nodes have an obvious rank, and by adding those ranks I have managed to reduce the time it spends in the stage between where it prints:

network simplex:  97406 nodes 149452 edges maxiter=1289 balance=2

and when it starts to print

network simplex: 100 200 300 400 500 600 700 800 900 1000
network simplex: 1100 1200
network simplex: 97406 nodes 149452 edges 1289 iter 2390.80 sec

to just over half an hour. This is still too long from the point of view of our tool being usable. I have tried dialing back all the knobs I can find:

dot -v rdotIn.xdot -Txdot -o rdotOut.xdot

with the graph annotations being:

graph [xdotversion=1.2, rankdir=TB, nslimit=1, nslimit1=1, maxiter=1, mclimit=0.1];

So unless you have something to suggest we are at wits end here.

Any suggestions, such as what additional structure we could add that would speed up the bottleneck, or knobs to dial, would be much appreciated.

graphviz commented 7 years ago

Maybe I can look at it next week.

It seems like an algorithm bug :-(

Sent from my iPad

On Nov 20, 2016, at 5:49 PM, Ian A Mason notifications@github.com wrote:

The graphs are generated by inductively closing a set of biological reaction rules. So the rule nodes have an obvious rank, and by adding those ranks I have managed to reduce the time it spends in the stage between where it prints:

network simplex: 97406 nodes 149452 edges maxiter=1289 balance=2 and when it starts to print

network simplex: 100 200 300 400 500 600 700 800 900 1000 network simplex: 1100 1200 network simplex: 97406 nodes 149452 edges 1289 iter 2390.80 sec to just over half an hour. This is still too long from the point of view of our tool being usable. I have tried dialing back all the knobs I can find:

dot -v rdotIn.xdot -Txdot -o rdotOut.xdot with the graph annotations being:

graph [xdotversion=1.2, rankdir=TB, nslimit=1, nslimit1=1, maxiter=1, mclimit=0.1]; So unless you have something to suggest we are at wits end here.

Any suggestions would be much appreciated.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

ianamason commented 7 years ago

That would be great! Let me know if you need any thing. I put the ranked graph here:

http://www.csl.sri.com/users/iam/rdotIn.xdot

ianamason commented 7 years ago

I'm hoping this hasn't fallen through the cracks....

magneticnorth commented 7 years ago

Maybe Graphviz needs a kickstarter project :-)

On Dec 1, 2016, at 10:26 AM, Ian A Mason notifications@github.com wrote:

I'm hoping this hasn't fallen through the cracks....

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264202432, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz5p6hELxcAP21Aq-z2glERo6Hv75ks5rDucggaJpZM4K3IQg.

ianamason commented 7 years ago

Yes. Soon all science in the states will be funded by the NKF.

magneticnorth commented 7 years ago

You lost me - National Kidney Foundation? At least Emden finds some Graphviz love at Google.

On Dec 1, 2016, at 10:57 AM, Ian A Mason notifications@github.com wrote:

Yes. Soon all science in the states will be funded by the NKF.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264211691, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWzzzoIxj15NcEGbiTwZB09wgLmNK7ks5rDu5hgaJpZM4K3IQg.

ianamason commented 7 years ago

National Kickstarter Foundation.

magneticnorth commented 7 years ago

See, I know so little about it. That’s what I get from thinking about healthcare data so much.

On Dec 1, 2016, at 11:01 AM, Ian A Mason notifications@github.com wrote:

National Kickstarter Foundation.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264212861, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz9GqYyuICxJTzQxkyUWpJJw6kgWsks5rDu9KgaJpZM4K3IQg.

emdenrg commented 7 years ago

There are only a limited number of 2-4 letter but even then, certain combinations are heavily overused.

On 12/01/2016 11:05 AM, Stephen North wrote:

See, I know so little about it. That’s what I get from thinking about healthcare data so much.

magneticnorth commented 7 years ago

Can someone use a profiler and determine where it (network simplex) is spending so much time in the X positions phase? Before or after finding initial feasible solution?

On Thu, Dec 1, 2016 at 11:50 AM Emden R. Gansner notifications@github.com wrote:

There are only a limited number of 2-4 letter but even then, certain combinations are heavily overused.

On 12/01/2016 11:05 AM, Stephen North wrote:

See, I know so little about it. That’s what I get from thinking about healthcare data so much.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264226908, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz34oh5C-LqqU2ImBOHbFoZBoxuhEks5rDvrVgaJpZM4K3IQg .

ianamason commented 7 years ago

I could learn how to do this, if there are no other takers. gprof?

magneticnorth commented 7 years ago

Or the clang equivalent? I can learn it but it will take time.

On Sat, Dec 3, 2016 at 11:13 AM Ian A Mason notifications@github.com wrote:

I could learn how to do this, if there are no other takers. gprof?

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264648484, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz4vmh5A3gFPuaZWRTfev6FReSbQsks5rEZU5gaJpZM4K3IQg .

magneticnorth commented 7 years ago

I’m stumped just trying to get graphviz to build and run with -pg

I’m using CC=gcc CFLAGS=-pg AR=/usr/bin/ar LIBTOOL=glibtool ./configure … on Mac OSX. gcc is really llvm, as far as I can tell. The executable works OK but I don’t see any profiling recorded in the current directory. Maybe llvm is too advanced for me!

On Dec 3, 2016, at 11:13 AM, Ian A Mason notifications@github.com wrote:

I could learn how to do this, if there are no other takers. gprof?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264648484, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz4vmh5A3gFPuaZWRTfev6FReSbQsks5rEZU5gaJpZM4K3IQg.

ianamason commented 7 years ago

Yes that does not look like a happy route. I'll do it on Monday on linux if you have no further luck being brave on a mac.

ellson commented 7 years ago

Stephen,

I get profiling results using.

./autogen.sh --prefix=$PREFIX --enable-static --disable-php

make -j CFLAGS="-Wall -pg" install

echo "graph{A}" | $PREFIX/bin/dot_static

gprof $PREFIX/bin/dot_static gmon.out >analysis.txt

less analysis.txt

($PREFIX is just set to a dirpath I use under my $HOME to install software without root).

Do you want me to run it on a particular test graph? Or are the results for this trivial graph useful to you?

John

On December 3, 2016 at 10:53 AM Stephen North notifications@github.com wrote:

Can someone use a profiler and determine where it (network simplex) is
spending so much time in the X positions phase? Before or after finding
initial feasible solution?

On Thu, Dec 1, 2016 at 11:50 AM Emden R. Gansner <notifications@github.com>
wrote:

> There are only a limited number of 2-4 letter but even then, certain
> combinations are heavily overused.
>
> On 12/01/2016 11:05 AM, Stephen North wrote:
> > See, I know so little about it. That’s what I get from thinking about
> > healthcare data so much.
>
> —
> You are receiving this because you commented.
>
>
> Reply to this email directly, view it on GitHub
> <https://github.com/ellson/graphviz/issues/1172#issuecomment-264226908>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ACtWz34oh5C-LqqU2ImBOHbFoZBoxuhEks5rDvrVgaJpZM4K3IQg>
> .
>

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264647024 , or mute the thread https://github.com/notifications/unsubscribe-auth/ABcTPTp_Cgwb528oA7Iw9L7CjYoHYK4jks5rEZBigaJpZM4K3IQg .

ellson commented 7 years ago

I found the problem graph earlier in the ticket...

I did this:

$PREFIX/bin/dot_static -v rdotIn.xdot -Txdot -o rdotOut.xdot << interrrupted after a couple of min gprof $PREFIX/bin/dot_static gmon.out >analysis.txt

analysis.txt attached

John

On December 4, 2016 at 2:53 AM John Ellson john.ellson@comcast.net wrote:

Stephen,

I get profiling results using.

./autogen.sh --prefix=$PREFIX --enable-static --disable-php

make -j CFLAGS="-Wall -pg" install

echo "graph{A}" | $PREFIX/bin/dot_static

gprof $PREFIX/bin/dot_static gmon.out >analysis.txt

less analysis.txt

($PREFIX is just set to a dirpath I use under my $HOME to install software without root).

Do you want me to run it on a particular test graph?  Or are the results for this trivial graph useful to you?

John

    > > On December 3, 2016 at 10:53 AM Stephen North <notifications@github.com> wrote:

    Can someone use a profiler and determine where it (network simplex) is
    spending so much time in the X positions phase? Before or after finding
    initial feasible solution?

    On Thu, Dec 1, 2016 at 11:50 AM Emden R. Gansner <notifications@github.com>
    wrote:

    > There are only a limited number of 2-4 letter but even then, certain
    > combinations are heavily overused.
    >
    > On 12/01/2016 11:05 AM, Stephen North wrote:
    > > See, I know so little about it. That’s what I get from thinking about
    > > healthcare data so much.
    >
    > —
    > You are receiving this because you commented.
    >
    >
    > Reply to this email directly, view it on GitHub
    > <https://github.com/ellson/graphviz/issues/1172#issuecomment-264226908>,
    > or mute the thread
    > <https://github.com/notifications/unsubscribe-auth/ACtWz34oh5C-LqqU2ImBOHbFoZBoxuhEks5rDvrVgaJpZM4K3IQg>
    > .
    >

    —
    You are receiving this because you are subscribed to this thread.
    Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264647024 , or mute the thread https://github.com/notifications/unsubscribe-auth/ABcTPTp_Cgwb528oA7Iw9L7CjYoHYK4jks5rEZBigaJpZM4K3IQg .

>

Flat profile:

Each sample counts as 0.01 seconds. % cumulative self self total
time seconds seconds calls s/call s/call name
38.10 20.21 20.21 295628726 0.00 0.00 left2right 21.99 31.88 11.67 48031108 0.00 0.00 out_cross 14.67 39.66 7.78 48030866 0.00 0.00 in_cross 10.59 45.28 5.62 61 0.09 0.42 reorder 6.37 48.66 3.38 11668 0.00 0.00 transpose_step 2.30 49.88 1.22 152 0.01 0.01 rcross 2.14 51.01 1.14 68208963 0.00 0.00 exchange 1.66 51.89 0.88 10757223 0.00 0.00 dttree 0.41 52.11 0.22 mincross_clust 0.28 52.26 0.15 1 0.15 1.29 cleanup1 0.19 52.36 0.10 8431854 0.00 0.00 dtextract 0.17 52.45 0.09 9597041 0.00 0.00 agsubrep 0.15 52.53 0.08 8431854 0.00 0.00 dtrestore 0.13 52.60 0.07 7219869 0.00 0.00 agnxtout 0.08 52.64 0.04 204776 0.00 0.00 irrelevant_subgraph 0.08 52.68 0.04 90666 0.00 0.00 enqueue_neighbors 0.08 52.72 0.04 2 0.02 6.36 build_ranks 0.06 52.75 0.03 1122837 0.00 0.00 agsubnodeidcmpf 0.06 52.78 0.03 61 0.00 0.00 medians 0.06 52.81 0.03 3 0.01 0.01 save_best 0.06 52.84 0.03 2 0.02 0.02 search_component 0.05 52.87 0.03 827188 0.00 0.00 aggetrec 0.04 52.89 0.02 179414 0.00 0.00 aaglex 0.04 52.91 0.02 91816 0.00 0.00 _agstrcanon 0.02 52.92 0.01 490059 0.00 0.00 agsubnodeseqcmpf 0.02 52.93 0.01 354485 0.00 0.00 refsymbind 0.02 52.94 0.01 119369 0.00 0.00 memalloc 0.02 52.95 0.01 106093 0.00 0.00 grealloc 0.02 52.96 0.01 91816 0.00 0.00 _write_canonstr 0.02 52.97 0.01 16062 0.00 0.00 getedgeitems 0.02 52.98 0.01 10224 0.00 0.00 applyattrs 0.02 52.99 0.01 9320 0.00 0.00 write_nondefault_attrs 0.02 53.00 0.01 165 0.00 0.00 dtdisc 0.02 53.01 0.01 1 0.01 0.13 aagparse 0.02 53.02 0.01 1 0.01 0.01 class1 0.02 53.03 0.01 1 0.01 0.01 flat_breakcycles 0.02 53.04 0.01 agfindedge_by_id 0.02 53.05 0.01 dtstrhash 0.01 53.05 0.01 28108 0.00 0.00 set_data 0.00 53.05 0.00 1181249 0.00 0.00 agnxtnode 0.00 53.05 0.00 1164624 0.00 0.00 agfstout 0.00 53.05 0.00 725810 0.00 0.00 agattrrec 0.00 53.05 0.00 652471 0.00 0.00 agroot 0.00 53.05 0.00 430349 0.00 0.00 agraphof 0.00 53.05 0.00 411912 0.00 0.00 agparent 0.00 53.05 0.00 378313 0.00 0.00 agfindnode_by_id 0.00 53.05 0.00 358252 0.00 0.00 agsubnode 0.00 53.05 0.00 354485 0.00 0.00 refdict 0.00 53.05 0.00 298378 0.00 0.00 gmalloc 0.00 53.05 0.00 295384 0.00 0.00 zmalloc 0.00 53.05 0.00 277560 0.00 0.00 gvputs 0.00 53.05 0.00 277560 0.00 0.00 gvwrite 0.00 53.05 0.00 277560 0.00 0.00 ioput 0.00 53.05 0.00 277527 0.00 0.00 gvwrite_no_z 0.00 53.05 0.00 233224 0.00 0.00 aginternalmapprint 0.00 53.05 0.00 233224 0.00 0.00 agnameof 0.00 53.05 0.00 233224 0.00 0.00 find_isym 0.00 53.05 0.00 233224 0.00 0.00 idprint 0.00 53.05 0.00 217626 0.00 0.00 dtsize 0.00 53.05 0.00 206683 0.00 0.00 agstrdup 0.00 53.05 0.00 196843 0.00 0.00 agnxtsubg 0.00 53.05 0.00 129563 0.00 0.00 agstrfree 0.00 53.05 0.00 128496 0.00 0.00 agsubedge 0.00 53.05 0.00 119365 0.00 0.00 agalloc 0.00 53.05 0.00 104146 0.00 0.00 endpoint_class 0.00 53.05 0.00 93105 0.00 0.00 aghtmlstr 0.00 53.05 0.00 91816 0.00 0.00 agcanonStr 0.00 53.05 0.00 91816 0.00 0.00 agstrcanon 0.00 53.05 0.00 91816 0.00 0.00 getoutputbuffer 0.00 53.05 0.00 91816 0.00 0.00 write_canonstr 0.00 53.05 0.00 91392 0.00 0.00 dequeue 0.00 53.05 0.00 91107 0.00 0.00 UF_find 0.00 53.05 0.00 91068 0.00 0.00 enqueue 0.00 53.05 0.00 90666 0.00 0.00 install_in_rank 0.00 53.05 0.00 84622 0.00 0.00 agedgeseqcmpf 0.00 53.05 0.00 75931 0.00 0.00 agedgeidcmpf 0.00 53.05 0.00 70052 0.00 0.00 agfree 0.00 53.05 0.00 70052 0.00 0.00 memfree 0.00 53.05 0.00 70033 0.00 0.00 listapp 0.00 53.05 0.00 70033 0.00 0.00 newitem 0.00 53.05 0.00 64026 0.00 0.00 agdatadict 0.00 53.05 0.00 63892 0.00 0.00 agdictof 0.00 53.05 0.00 60525 0.00 0.00 agdictsym 0.00 53.05 0.00 53041 0.00 0.00 fast_edge 0.00 53.05 0.00 53041 0.00 0.00 new_virtual_edge 0.00 53.05 0.00 53041 0.00 0.00 virtual_edge 0.00 53.05 0.00 52964 0.00 0.00 pop 0.00 53.05 0.00 52962 0.00 0.00 push 0.00 53.05 0.00 52073 0.00 0.00 virtual_weight 0.00 53.05 0.00 46587 0.00 0.00 indent 0.00 53.05 0.00 45735 0.00 0.00 add_to_component 0.00 53.05 0.00 45333 0.00 0.00 fast_node 0.00 53.05 0.00 44044 0.00 0.00 incr_width 0.00 53.05 0.00 44044 0.00 0.00 plain_vnode 0.00 53.05 0.00 44044 0.00 0.00 virtual_node 0.00 53.05 0.00 39868 0.00 0.00 agmethod_upd 0.00 53.05 0.00 39868 0.00 0.00 agupdcb 0.00 53.05 0.00 39819 0.00 0.00 agxset 0.00 53.05 0.00 37811 0.00 0.00 agmapnametoid 0.00 53.05 0.00 35851 0.00 0.00 agattr 0.00 53.05 0.00 35802 0.00 0.00 getattr 0.00 53.05 0.00 35716 0.00 0.00 appendattr 0.00 53.05 0.00 35716 0.00 0.00 cons_attr 0.00 53.05 0.00 32124 0.00 0.00 ins 0.00 53.05 0.00 30740 0.00 0.00 delete_items 0.00 53.05 0.00 30740 0.00 0.00 deletelist 0.00 53.05 0.00 30158 0.00 0.00 chkNum 0.00 53.05 0.00 28014 0.00 0.00 agbindrec 0.00 53.05 0.00 27593 0.00 0.00 idmap 0.00 53.05 0.00 26643 0.00 0.00 late_int 0.00 53.05 0.00 24598 0.00 0.00 agattrsym 0.00 53.05 0.00 23309 0.00 0.00 agget 0.00 53.05 0.00 23106 0.00 0.00 late_string 0.00 53.05 0.00 21268 0.00 0.00 addattr 0.00 53.05 0.00 18693 0.00 0.00 objputrec 0.00 53.05 0.00 18348 0.00 0.00 agfstsubg 0.00 53.05 0.00 18255 0.00 0.00 agnode 0.00 53.05 0.00 18255 0.00 0.00 agstrbind 0.00 53.05 0.00 18255 0.00 0.00 appendnode 0.00 53.05 0.00 18255 0.00 0.00 cons_node 0.00 53.05 0.00 18255 0.00 0.00 refstrbind 0.00 53.05 0.00 17351 0.00 0.00 write_nodename 0.00 53.05 0.00 16063 0.00 0.00 agisstrict 0.00 53.05 0.00 16062 0.00 0.00 chkPort 0.00 53.05 0.00 16062 0.00 0.00 cons_list 0.00 53.05 0.00 16062 0.00 0.00 mkport 0.00 53.05 0.00 16062 0.00 0.00 noClip 0.00 53.05 0.00 16062 0.00 0.00 nonconstraint_edge 0.00 53.05 0.00 16062 0.00 0.00 write_port 0.00 53.05 0.00 15272 0.00 0.00 poly_port 0.00 53.05 0.00 13230 0.00 0.00 memresize 0.00 53.05 0.00 13187 0.00 0.00 addstr 0.00 53.05 0.00 13187 0.00 0.00 beginstr 0.00 53.05 0.00 13187 0.00 0.00 endstr 0.00 53.05 0.00 10257 0.00 0.00 bindattrs 0.00 53.05 0.00 10223 0.00 0.00 node_in_subg 0.00 53.05 0.00 10223 0.00 0.00 write_node_test 0.00 53.05 0.00 10218 0.00 0.00 agedge 0.00 53.05 0.00 10218 0.00 0.00 agfindedge_by_key 0.00 53.05 0.00 10218 0.00 0.00 agisdirected 0.00 53.05 0.00 9342 0.00 0.00 aag_get_next_buffer 0.00 53.05 0.00 9342 0.00 0.00 aag_get_previous_state 0.00 53.05 0.00 9342 0.00 0.00 iofread 0.00 53.05 0.00 9338 0.00 0.00 aginitcb 0.00 53.05 0.00 9338 0.00 0.00 agmakeattrs 0.00 53.05 0.00 9338 0.00 0.00 agmethod_init 0.00 53.05 0.00 9338 0.00 0.00 agregister 0.00 53.05 0.00 9338 0.00 0.00 idregister 0.00 53.05 0.00 9338 0.00 0.00 topdictsize 0.00 53.05 0.00 9336 0.00 0.00 agnextseq 0.00 53.05 0.00 9320 0.00 0.00 attrs_written 0.00 53.05 0.00 9320 0.00 0.00 boxf_overlap 0.00 53.05 0.00 9320 0.00 0.00 emit_node 0.00 53.05 0.00 9320 0.00 0.00 node_in_box 0.00 53.05 0.00 9320 0.00 0.00 node_in_layer 0.00 53.05 0.00 8152 0.00 0.00 ffe 0.00 53.05 0.00 8152 0.00 0.00 find_fast_edge 0.00 53.05 0.00 8031 0.00 0.00 agedgeattr_init 0.00 53.05 0.00 8031 0.00 0.00 common_init_edge 0.00 53.05 0.00 8031 0.00 0.00 dot_init_edge 0.00 53.05 0.00 8031 0.00 0.00 edge_in_box 0.00 53.05 0.00 8031 0.00 0.00 edgerhs 0.00 53.05 0.00 8031 0.00 0.00 emit_edge 0.00 53.05 0.00 8031 0.00 0.00 endedge 0.00 53.05 0.00 8031 0.00 0.00 init_bb_edge 0.00 53.05 0.00 8031 0.00 0.00 installedge 0.00 53.05 0.00 8031 0.00 0.00 is_cluster_edge 0.00 53.05 0.00 8031 0.00 0.00 newedge 0.00 53.05 0.00 8031 0.00 0.00 newedge 0.00 53.05 0.00 8031 0.00 0.00 ok_to_make_edge 0.00 53.05 0.00 8031 0.00 0.00 write_edge 0.00 53.05 0.00 8031 0.00 0.00 write_edge_name 0.00 53.05 0.00 8031 0.00 0.00 write_edge_test 0.00 53.05 0.00 8029 0.00 0.00 make_chain 0.00 53.05 0.00 7184 0.00 0.00 basic_merge 0.00 53.05 0.00 7184 0.00 0.00 merge_oneway 0.00 53.05 0.00 6751 0.00 0.00 agxget 0.00 53.05 0.00 5129 0.00 0.00 late_double 0.00 53.05 0.00 4310 0.00 0.00 agxbput 0.00 53.05 0.00 4310 0.00 0.00 agxbput_n 0.00 53.05 0.00 4239 0.00 0.00 late_nnstring 0.00 53.05 0.00 3903 0.00 0.00 incident 0.00 53.05 0.00 3839 0.00 0.00 mapBool 0.00 53.05 0.00 3839 0.00 0.00 mapbool 0.00 53.05 0.00 3282 0.00 0.00 add_tree_edge 0.00 53.05 0.00 2950 0.00 0.00 agobjkind 0.00 53.05 0.00 2810 0.00 0.00 agfstin 0.00 53.05 0.00 2209 0.00 0.00 endnode 0.00 53.05 0.00 2209 0.00 0.00 has_no_predecessor_below 0.00 53.05 0.00 2192 0.00 0.00 installnode 0.00 53.05 0.00 2187 0.00 0.00 agisundirected 0.00 53.05 0.00 1835 0.00 0.00 agxbinit 0.00 53.05 0.00 1832 0.00 0.00 agxbfree 0.00 53.05 0.00 1704 0.00 0.00 xdot_fmt_num 0.00 53.05 0.00 1704 0.00 0.00 xdot_trim_zeros 0.00 53.05 0.00 1574 0.00 0.00 x_val 0.00 53.05 0.00 1568 0.00 0.00 is_style_delim 0.00 53.05 0.00 1460 0.00 0.00 strdup_and_subst_obj0 0.00 53.05 0.00 1377 0.00 0.00 make_label 0.00 53.05 0.00 1347 0.00 0.00 emit_once 0.00 53.05 0.00 1347 0.00 0.00 gvtextlayout 0.00 53.05 0.00 1347 0.00 0.00 htmlEntityUTF8 0.00 53.05 0.00 1347 0.00 0.00 make_simple_label 0.00 53.05 0.00 1347 0.00 0.00 pango_textlayout 0.00 53.05 0.00 1347 0.00 0.00 storeline 0.00 53.05 0.00 1347 0.00 0.00 textspan_size 0.00 53.05 0.00 1346 0.00 0.00 textfont_comparf 0.00 53.05 0.00 1289 0.00 0.00 agdegree 0.00 53.05 0.00 1289 0.00 0.00 agnodeattr_init 0.00 53.05 0.00 1289 0.00 0.00 agset 0.00 53.05 0.00 1289 0.00 0.00 bind_shape 0.00 53.05 0.00 1289 0.00 0.00 cnt 0.00 53.05 0.00 1289 0.00 0.00 common_init_node 0.00 53.05 0.00 1289 0.00 0.00 dot_init_node 0.00 53.05 0.00 1289 0.00 0.00 gv_nodesize 0.00 53.05 0.00 1289 0.00 0.00 has_no_edges 0.00 53.05 0.00 1289 0.00 0.00 init_bb_node 0.00 53.05 0.00 1289 0.00 0.00 initnode 0.00 53.05 0.00 1289 0.00 0.00 installnodetoroot 0.00 53.05 0.00 1289 0.00 0.00 newnode 0.00 53.05 0.00 1289 0.00 0.00 safefile 0.00 53.05 0.00 1289 0.00 0.00 shapeOf 0.00 53.05 0.00 1289 0.00 0.00 write_node 0.00 53.05 0.00 1259 0.00 0.00 poly_init 0.00 53.05 0.00 1197 0.00 0.00 treecount 0.00 53.05 0.00 956 0.00 0.00 agfstnode 0.00 53.05 0.00 920 0.00 0.00 agnxtin 0.00 53.05 0.00 903 0.00 0.00 UF_singleton 0.00 53.05 0.00 887 0.00 0.00 UF_union 0.00 53.05 0.00 804 0.00 0.00 renewlist 0.00 53.05 0.00 790 0.00 0.00 record_port 0.00 53.05 0.00 658 0.00 0.00 xdot_str 0.00 53.05 0.00 658 0.00 0.00 xdot_str_xbuf 0.00 53.05 0.00 651 0.00 0.00 xdot_point 0.00 53.05 0.00 651 0.00 0.00 yDir 0.00 53.05 0.00 448 0.00 0.00 style_token 0.00 53.05 0.00 444 0.00 0.00 pointfof 0.00 53.05 0.00 402 0.00 0.00 dfs 0.00 53.05 0.00 401 0.00 0.00 x_cutval 0.00 53.05 0.00 399 0.00 0.00 canontoken 0.00 53.05 0.00 398 0.00 0.00 colorxlate 0.00 53.05 0.00 398 0.00 0.00 gvrender_resolve_color 0.00 53.05 0.00 386 0.00 0.00 color2str 0.00 53.05 0.00 386 0.00 0.00 not_default_attrs 0.00 53.05 0.00 310 0.00 0.00 dtview 0.00 53.05 0.00 286 0.00 0.00 resolveColor 0.00 53.05 0.00 284 0.00 0.00 gvrender_set_pencolor 0.00 53.05 0.00 273 0.00 0.00 xdot_pencolor 0.00 53.05 0.00 242 0.00 0.00 zapinlist 0.00 53.05 0.00 224 0.00 0.00 parse_style 0.00 53.05 0.00 166 0.00 0.00 gvplugin_install 0.00 53.05 0.00 160 0.00 0.00 interpolate_pointf 0.00 53.05 0.00 149 0.00 0.00 dtopen 0.00 53.05 0.00 147 0.00 0.00 agdictobjmem 0.00 53.05 0.00 147 0.00 0.00 agdtopen 0.00 53.05 0.00 146 0.00 0.00 penColor 0.00 53.05 0.00 137 0.00 0.00 xdot_style 0.00 53.05 0.00 136 0.00 0.00 emit_label 0.00 53.05 0.00 136 0.00 0.00 gvrender_begin_label 0.00 53.05 0.00 136 0.00 0.00 gvrender_end_label 0.00 53.05 0.00 136 0.00 0.00 gvrender_textspan 0.00 53.05 0.00 136 0.00 0.00 xdot_textspan 0.00 53.05 0.00 121 0.00 0.00 delete_fast_edge 0.00 53.05 0.00 121 0.00 0.00 reverse_edge 0.00 53.05 0.00 114 0.00 0.00 gvrender_set_fillcolor 0.00 53.05 0.00 113 0.00 0.00 findStopColor 0.00 53.05 0.00 113 0.00 0.00 freeSegs 0.00 53.05 0.00 113 0.00 0.00 getObjId 0.00 53.05 0.00 113 0.00 0.00 getSegLen 0.00 53.05 0.00 113 0.00 0.00 gvrender_comment 0.00 53.05 0.00 113 0.00 0.00 initMapData 0.00 53.05 0.00 113 0.00 0.00 initObjMapData 0.00 53.05 0.00 113 0.00 0.00 layerPagePrefix 0.00 53.05 0.00 113 0.00 0.00 parseSegs 0.00 53.05 0.00 113 0.00 0.00 pop_obj_state 0.00 53.05 0.00 113 0.00 0.00 push_obj_state 0.00 53.05 0.00 113 0.00 0.00 setColorScheme 0.00 53.05 0.00 113 0.00 0.00 strdup_and_subst_obj 0.00 53.05 0.00 113 0.00 0.00 xdot_fillcolor 0.00 53.05 0.00 112 0.00 0.00 checkStyle 0.00 53.05 0.00 112 0.00 0.00 emit_begin_node 0.00 53.05 0.00 112 0.00 0.00 emit_end_node 0.00 53.05 0.00 112 0.00 0.00 findFill 0.00 53.05 0.00 112 0.00 0.00 findFillDflt 0.00 53.05 0.00 112 0.00 0.00 gvrender_begin_node 0.00 53.05 0.00 112 0.00 0.00 gvrender_end_node 0.00 53.05 0.00 112 0.00 0.00 gvrender_set_style 0.00 53.05 0.00 112 0.00 0.00 hsv2rgb 0.00 53.05 0.00 112 0.00 0.00 stylenode 0.00 53.05 0.00 112 0.00 0.00 xdot_end_node 0.00 53.05 0.00 102 0.00 0.00 poly_gencode 0.00 53.05 0.00 96 0.00 0.00 treeupdate 0.00 53.05 0.00 83 0.00 0.00 aglocaldictsym 0.00 53.05 0.00 82 0.00 0.00 add_pointf 0.00 53.05 0.00 72 0.00 0.00 xdot_points 0.00 53.05 0.00 65 0.00 0.00 gvrender_ellipse 0.00 53.05 0.00 65 0.00 0.00 xdot_ellipse 0.00 53.05 0.00 51 0.00 0.00 write_dict 0.00 53.05 0.00 49 0.00 0.00 dfs_range 0.00 53.05 0.00 49 0.00 0.00 leave_edge 0.00 53.05 0.00 49 0.00 0.00 setattr 0.00 53.05 0.00 48 0.00 0.00 dtvsearch 0.00 53.05 0.00 48 0.00 0.00 enter_edge 0.00 53.05 0.00 48 0.00 0.00 exchange_tree_edges 0.00 53.05 0.00 48 0.00 0.00 update 0.00 53.05 0.00 44 0.00 0.00 agnewsym 0.00 53.05 0.00 42 0.00 0.00 subgraph_search 0.00 53.05 0.00 38 0.00 0.00 dfs_enter_outedge 0.00 53.05 0.00 38 0.00 0.00 gvrender_polygon 0.00 53.05 0.00 38 0.00 0.00 xdot_polygon 0.00 53.05 0.00 35 0.00 0.00 gv_get_font 0.00 53.05 0.00 34 0.00 0.00 get_avail_faces 0.00 53.05 0.00 34 0.00 0.00 mid_pointf 0.00 53.05 0.00 33 0.00 0.00 copyUpper 0.00 53.05 0.00 30 0.00 0.00 agraphidcmpf 0.00 53.05 0.00 30 0.00 0.00 parse_reclbl 0.00 53.05 0.00 30 0.00 0.00 pos_reclbl 0.00 53.05 0.00 30 0.00 0.00 record_init 0.00 53.05 0.00 30 0.00 0.00 resize_reclbl 0.00 53.05 0.00 30 0.00 0.00 size_reclbl 0.00 53.05 0.00 24 0.00 0.00 gvrender_polyline 0.00 53.05 0.00 24 0.00 0.00 xdot_polyline 0.00 53.05 0.00 22 0.00 0.00 rerank 0.00 53.05 0.00 18 0.00 0.00 agmakedatadict 0.00 53.05 0.00 18 0.00 0.00 agopen1 0.00 53.05 0.00 18 0.00 0.00 agraphattr_init 0.00 53.05 0.00 18 0.00 0.00 maptoken 0.00 53.05 0.00 17 0.00 0.00 attrstmt 0.00 53.05 0.00 17 0.00 0.00 pop 0.00 53.05 0.00 17 0.00 0.00 push 0.00 53.05 0.00 17 0.00 0.01 write_body 0.00 53.05 0.00 17 0.00 0.00 write_dicts 0.00 53.05 0.00 17 0.00 0.00 write_hdr 0.00 53.05 0.00 17 0.00 0.00 write_subgs 0.00 53.05 0.00 17 0.00 0.00 write_trl 0.00 53.05 0.00 16 0.00 0.00 agdtdisc 0.00 53.05 0.00 16 0.00 0.00 agfindsubg_by_id 0.00 53.05 0.00 16 0.00 0.00 agsubg 0.00 53.05 0.00 16 0.00 0.00 closesubg 0.00 53.05 0.00 16 0.00 0.00 collapse_rankset 0.00 53.05 0.00 16 0.00 0.00 is_cluster 0.00 53.05 0.00 16 0.00 0.00 localsubg 0.00 53.05 0.00 16 0.00 0.00 opensubg 0.00 53.05 0.00 16 0.00 0.00 rank_set_class 0.00 53.05 0.00 10 0.00 0.00 dfs_enter_inedge 0.00 53.05 0.00 10 0.00 0.00 gen_fields 0.00 53.05 0.00 10 0.00 0.00 gvrender_beziercurve 0.00 53.05 0.00 10 0.00 0.00 record_gencode 0.00 53.05 0.00 10 0.00 0.00 round_corners 0.00 53.05 0.00 10 0.00 0.00 safe_dcl 0.00 53.05 0.00 10 0.00 0.00 xdot_bezier 0.00 53.05 0.00 9 0.00 0.00 agapply 0.00 53.05 0.00 9 0.00 0.00 get_faces 0.00 53.05 0.00 9 0.00 0.00 rec_apply 0.00 53.05 0.00 9 0.00 0.00 tight_tree 0.00 53.05 0.00 9 0.00 0.00 treesearch 0.00 53.05 0.00 8 0.00 0.00 dtmemory 0.00 53.05 0.00 7 0.00 0.00 dot_root 0.00 53.05 0.00 6 0.00 0.20 ncross 0.00 53.05 0.00 5 0.00 0.00 gv_fixLocale 0.00 53.05 0.00 5 0.00 0.00 gvconfig_plugin_install_from_library 0.00 53.05 0.00 5 0.00 0.00 gvplugin_list 0.00 53.05 0.00 5 0.00 0.00 gvplugin_package_record 0.00 53.05 0.00 4 0.00 0.00 gvplugin_load 0.00 53.05 0.00 4 0.00 6.12 transpose 0.00 53.05 0.00 3 0.00 0.00 aagalloc 0.00 53.05 0.00 3 0.00 0.00 agcopydict 0.00 53.05 0.00 3 0.00 0.00 agdictobjfree 0.00 53.05 0.00 3 0.00 0.00 agdtdelete 0.00 53.05 0.00 3 0.00 0.00 free_queue 0.00 53.05 0.00 3 0.00 12.53 mincross_step 0.00 53.05 0.00 3 0.00 0.00 new_queue 0.00 53.05 0.00 3 0.00 0.00 start_timer 0.00 53.05 0.00 3 0.00 0.00 validpage 0.00 53.05 0.00 2 0.00 0.00 aagdestruct 0.00 53.05 0.00 2 0.00 0.00 add_point 0.00 53.05 0.00 2 0.00 0.00 agclos 0.00 53.05 0.00 2 0.00 0.00 agnnodes 0.00 53.05 0.00 2 0.00 0.00 agopen 0.00 53.05 0.00 2 0.00 0.00 begin_component 0.00 53.05 0.00 2 0.00 0.02 decompose 0.00 53.05 0.00 2 0.00 0.00 dtclose 0.00 53.05 0.00 2 0.00 0.00 elapsed_sec 0.00 53.05 0.00 2 0.00 0.00 end_component 0.00 53.05 0.00 2 0.00 0.00 flat_reorder 0.00 53.05 0.00 2 0.00 0.00 freeStk 0.00 53.05 0.00 2 0.00 0.00 getFlagOpt 0.00 53.05 0.00 2 0.00 0.00 getPack 0.00 53.05 0.00 2 0.00 0.00 getPackModeInfo 0.00 53.05 0.00 2 0.00 0.00 getdoubles2ptf 0.00 53.05 0.00 2 0.00 0.00 gv_argvlist_reset 0.00 53.05 0.00 2 0.00 0.00 gvflush 0.00 53.05 0.00 2 0.00 0.00 gvg_init 0.00 53.05 0.00 2 0.00 0.00 idopen 0.00 53.05 0.00 2 0.00 0.00 initStk 0.00 53.05 0.00 2 0.00 0.00 mark_clusters 0.00 53.05 0.00 2 0.00 0.00 memopen 0.00 53.05 0.00 2 0.00 0.00 merge_chain 0.00 53.05 0.00 2 0.00 0.00 mode2Str 0.00 53.05 0.00 2 0.00 0.00 numPhysicalLayers 0.00 53.05 0.00 2 0.00 0.00 other_edge 0.00 53.05 0.00 2 0.00 0.00 pagecode 0.00 53.05 0.00 2 0.00 0.00 parsePackModeInfo 0.00 53.05 0.00 2 0.00 0.00 ports_eq 0.00 53.05 0.00 2 0.00 0.00 validlayer 0.00 53.05 0.00 1 0.00 0.00 TB_balance 0.00 53.05 0.00 1 0.00 0.00 aag_create_buffer 0.00 53.05 0.00 1 0.00 0.00 aag_flush_buffer 0.00 53.05 0.00 1 0.00 0.00 aag_init_buffer 0.00 53.05 0.00 1 0.00 0.00 aag_load_buffer_state 0.00 53.05 0.00 1 0.00 0.00 aagensure_buffer_stack 0.00 53.05 0.00 1 0.00 0.00 aagunput 0.00 53.05 0.00 1 0.00 0.00 acyclic 0.00 53.05 0.00 1 0.00 0.13 agconcat 0.00 53.05 0.00 1 0.00 0.00 agerrors 0.00 53.05 0.00 1 0.00 0.00 aginternalmapclearlocalnames 0.00 53.05 0.00 1 0.00 0.00 aglexeof 0.00 53.05 0.00 1 0.00 0.00 aglexinit 0.00 53.05 0.00 1 0.00 0.00 agnedges 0.00 53.05 0.00 1 0.00 0.13 agread 0.00 53.05 0.00 1 0.00 0.00 agsafeset 0.00 53.05 0.00 1 0.00 0.00 agsetfile 0.00 53.05 0.00 1 0.00 0.16 agwrite 0.00 53.05 0.00 1 0.00 0.00 allocate_ranks 0.00 53.05 0.00 1 0.00 0.00 attach_attrs_and_arrows 0.00 53.05 0.00 1 0.00 0.00 chkOrder 0.00 53.05 0.00 1 0.00 0.02 class2 0.00 53.05 0.00 1 0.00 0.00 collapse_sets 0.00 53.05 0.00 1 0.00 0.00 config_extra_args 0.00 53.05 0.00 1 0.00 0.00 dfs_cutval 0.00 53.05 0.00 1 0.00 52.52 doDot 0.00 53.05 0.00 1 0.00 0.00 do_graph_label 0.00 53.05 0.00 1 0.00 1.32 dot1_rank 0.00 53.05 0.00 1 0.00 52.52 dotLayout 0.00 53.05 0.00 1 0.00 0.00 dot_begin_graph 0.00 53.05 0.00 1 0.00 0.16 dot_end_graph 0.00 53.05 0.00 1 0.00 0.01 dot_init_node_edge 0.00 53.05 0.00 1 0.00 0.00 dot_init_subg 0.00 53.05 0.00 1 0.00 52.52 dot_layout 0.00 53.05 0.00 1 0.00 51.19 dot_mincross 0.00 53.05 0.00 1 0.00 1.32 dot_rank 0.00 53.05 0.00 1 0.00 0.00 dotneato_args_initialize 0.00 53.05 0.00 1 0.00 0.00 dotneato_basename 0.00 53.05 0.00 1 0.00 0.00 edgelabel_ranks 0.00 53.05 0.00 1 0.00 0.00 emit_background 0.00 53.05 0.00 1 0.00 0.00 emit_begin_graph 0.00 53.05 0.00 1 0.00 0.00 emit_clusters 0.00 53.05 0.00 1 0.00 0.16 emit_end_graph 0.00 53.05 0.00 1 0.00 0.16 emit_graph 0.00 53.05 0.00 1 0.00 0.00 emit_once_reset 0.00 53.05 0.00 1 0.00 0.00 emit_page 0.00 53.05 0.00 1 0.00 0.00 emit_view 0.00 53.05 0.00 1 0.00 0.00 endgraph 0.00 53.05 0.00 1 0.00 0.00 expand_ranksets 0.00 53.05 0.00 1 0.00 0.00 fdp_extra_args 0.00 53.05 0.00 1 0.00 0.00 feasible_tree 0.00 53.05 0.00 1 0.00 0.00 findCharset 0.00 53.05 0.00 1 0.00 0.00 firstlayer 0.00 53.05 0.00 1 0.00 0.00 firstpage 0.00 53.05 0.00 1 0.00 0.00 free_string_entry 0.00 53.05 0.00 1 0.00 0.00 freestack 0.00 53.05 0.00 1 0.00 0.00 getPackInfo 0.00 53.05 0.00 1 0.00 0.00 get_font_mapping 0.00 53.05 0.00 1 0.00 0.00 graphSize 0.00 53.05 0.00 1 0.00 0.00 graph_init 0.00 53.05 0.00 1 0.00 0.00 gvContextPlugins 0.00 53.05 0.00 1 0.00 0.00 gvFreeContext 0.00 53.05 0.00 1 0.00 52.52 gvLayoutJobs 0.00 53.05 0.00 1 0.00 0.00 gvNEWcontext 0.00 53.05 0.00 1 0.00 0.13 gvNextInputGraph 0.00 53.05 0.00 1 0.00 0.00 gvParseArgs 0.00 53.05 0.00 1 0.00 0.00 gvPluginsGraph 0.00 53.05 0.00 1 0.00 0.16 gvRenderJobs 0.00 53.05 0.00 1 0.00 0.00 gv_flist_free_af 0.00 53.05 0.00 1 0.00 0.00 gv_get_ps_fontlist 0.00 53.05 0.00 1 0.00 0.00 gv_initShapes 0.00 53.05 0.00 1 0.00 0.00 gvconfig 0.00 53.05 0.00 1 0.00 0.00 gvconfig_plugin_install_builtins 0.00 53.05 0.00 1 0.00 0.00 gvdevice_format 0.00 53.05 0.00 1 0.00 0.00 gvdevice_initialize 0.00 53.05 0.00 1 0.00 0.00 gvjobs_delete 0.00 53.05 0.00 1 0.00 0.00 gvjobs_first 0.00 53.05 0.00 1 0.00 0.00 gvjobs_next 0.00 53.05 0.00 1 0.00 0.00 gvjobs_output_filename 0.00 53.05 0.00 1 0.00 0.00 gvjobs_output_langname 0.00 53.05 0.00 1 0.00 0.00 gvlayout_select 0.00 53.05 0.00 1 0.00 0.00 gvplugin_write_status 0.00 53.05 0.00 1 0.00 0.00 gvrender_begin_graph 0.00 53.05 0.00 1 0.00 0.00 gvrender_begin_job 0.00 53.05 0.00 1 0.00 0.00 gvrender_begin_page 0.00 53.05 0.00 1 0.00 0.00 gvrender_box 0.00 53.05 0.00 1 0.00 0.16 gvrender_end_graph 0.00 53.05 0.00 1 0.00 0.00 gvrender_end_page 0.00 53.05 0.00 1 0.00 0.00 gvrender_select 0.00 53.05 0.00 1 0.00 0.00 gvtextlayout_select 0.00 53.05 0.00 1 0.00 0.00 init_bb 0.00 53.05 0.00 1 0.00 0.00 init_cutvalues 0.00 53.05 0.00 1 0.00 0.00 init_graph 0.00 53.05 0.00 1 0.00 0.00 init_gvc 0.00 53.05 0.00 1 0.00 0.00 init_job_dpi 0.00 53.05 0.00 1 0.00 0.00 init_job_margin 0.00 53.05 0.00 1 0.00 0.00 init_job_pad 0.00 53.05 0.00 1 0.00 0.00 init_job_pagination 0.00 53.05 0.00 1 0.00 0.00 init_job_viewport 0.00 53.05 0.00 1 0.00 0.00 init_layering 0.00 53.05 0.00 1 0.00 0.00 init_mccomp 0.00 53.05 0.00 1 0.00 0.03 init_mincross 0.00 53.05 0.00 1 0.00 0.00 init_rank 0.00 53.05 0.00 1 0.00 0.00 init_xdot 0.00 53.05 0.00 1 0.00 0.00 memtest_extra_args 0.00 53.05 0.00 1 0.00 51.16 mincross 0.00 53.05 0.00 1 0.00 0.00 mincross_options 0.00 53.05 0.00 1 0.00 0.00 minmax_edges 0.00 53.05 0.00 1 0.00 0.00 minmax_edges2 0.00 53.05 0.00 1 0.00 0.00 neato_extra_args 0.00 53.05 0.00 1 0.00 0.00 nextlayer 0.00 53.05 0.00 1 0.00 0.00 nextpage 0.00 53.05 0.00 1 0.00 0.00 ordered_edges 0.00 53.05 0.00 1 0.00 0.00 point_inside 0.00 53.05 0.00 1 0.00 0.00 poly_inside 0.00 53.05 0.00 1 0.00 0.00 rank 0.00 53.05 0.00 1 0.00 0.00 rank1 0.00 53.05 0.00 1 0.00 0.00 rank2 0.00 53.05 0.00 1 0.00 0.00 rec_attach_bb 0.00 53.05 0.00 1 0.00 0.00 scan_and_normalize 0.00 53.05 0.00 1 0.00 0.00 setAspect 0.00 53.05 0.00 1 0.00 0.00 setEdgeType 0.00 53.05 0.00 1 0.00 0.00 setRatio 0.00 53.05 0.00 1 0.00 0.00 setYInvert 0.00 53.05 0.00 1 0.00 0.00 set_attrwf 0.00 53.05 0.00 1 0.00 0.00 setup_page 0.00 53.05 0.00 1 0.00 0.00 star_inside 0.00 53.05 0.00 1 0.00 0.00 startgraph 0.00 53.05 0.00 1 0.00 0.00 textfont_dict_close 0.00 53.05 0.00 1 0.00 0.00 textfont_dict_open 0.00 53.05 0.00 1 0.00 0.00 textfont_freef 0.00 53.05 0.00 1 0.00 0.00 textfont_makef 0.00 53.05 0.00 1 0.00 0.00 translate_postscript_fontname 0.00 53.05 0.00 1 0.00 0.00 versionStr2Version 0.00 53.05 0.00 1 0.00 0.00 xdot_begin_graph 0.00 53.05 0.00 1 0.00 0.00 xdot_end_graph

% the percentage of the total running time of the time program used by this function.

cumulative a running sum of the number of seconds accounted seconds for by this function and those listed above it.

self the number of seconds accounted for by this seconds function alone. This is the major sort for this listing.

calls the number of times this function was invoked, if this function is profiled, else blank.

self the average number of milliseconds spent in this ms/call function per call, if this function is profiled, else blank.

total the average number of milliseconds spent in this ms/call function and its descendents per call, if this function is profiled, else blank.

name the name of the function. This is the minor sort for this listing. The index shows the location of the function in the gprof listing. If the index is in parenthesis it shows where it would appear in the gprof listing if it were to be printed. Copyright (C) 2012-2015 Free Software Foundation, Inc.

Copying and distribution of this file, with or without modification, are permitted in any medium without royalty provided the copyright notice and this notice are preserved. Call graph (explanation follows)

granularity: each sample hit covers 2 byte(s) for 0.02% of 53.05 seconds

index % time self children called name

[1] 99.2 0.00 52.65 main [1] 0.00 52.52 1/1 gvLayoutJobs [2] 0.00 0.13 1/1 gvNextInputGraph [38] 0.00 0.00 1/1 gvContextPlugins [186] 0.00 0.00 1/1 gvParseArgs [229] 0.00 0.00 1/1 gvPluginsGraph [499] ----------------------------------------------- 0.00 52.52 1/1 main [1] [2] 99.0 0.00 52.52 1 gvLayoutJobs [2] 0.00 52.52 1/1 dot_layout [4] 0.00 0.00 1/1 graph_init [200] 0.00 0.00 1/28014 agbindrec [104] 0.00 0.00 1/23309 agget [126] 0.00 0.00 2/652471 agroot [267] 0.00 0.00 1/5 gv_fixLocale [440] 0.00 0.00 1/1 gv_initShapes [502] ----------------------------------------------- 0.00 52.52 1/1 dot_layout [4] [3] 99.0 0.00 52.52 1 doDot [3] 0.00 52.52 1/1 dotLayout [5] 0.00 0.00 1/1 getPackInfo [240] 0.00 0.00 1/2 getPack [237] 0.00 0.00 1/2 getPackModeInfo [238] ----------------------------------------------- 0.00 52.52 1/1 gvLayoutJobs [2] [4] 99.0 0.00 52.52 1 dot_layout [4] 0.00 52.52 1/1 doDot [3] 0.00 0.00 1/2 agnnodes [453] ----------------------------------------------- 0.00 52.52 1/1 doDot [3] [5] 99.0 0.00 52.52 1 dotLayout [5] 0.00 51.19 1/1 dot_mincross [6] 0.00 1.32 1/1 dot_rank [16] 0.00 0.01 1/1 dot_init_node_edge [105] 0.00 0.00 1/1 dot_init_subg [214] 0.00 0.00 1/35851 agattr [80] 0.00 0.00 1/1 setEdgeType [259] 0.00 0.00 1/1 setAspect [258] 0.00 0.00 1/26643 late_int [306] ----------------------------------------------- 0.00 51.19 1/1 dotLayout [5] [6] 96.5 0.00 51.19 1 dot_mincross [6] 0.00 51.16 1/1 mincross [7] 0.00 0.03 1/1 init_mincross [52] 0.00 0.00 1/1 init_mccomp [525] ----------------------------------------------- 0.00 51.16 1/1 dot_mincross [6] [7] 96.4 0.00 51.16 1 mincross [7] 0.00 37.59 3/3 mincross_step [8] 0.04 12.68 2/2 build_ranks [13] 0.00 0.81 4/6 ncross [20] 0.03 0.00 3/3 save_best [62] 0.01 0.00 1/1 flat_breakcycles [88] 0.00 0.00 2/7 dot_root [439] 0.00 0.00 2/2 flat_reorder [457] ----------------------------------------------- 0.00 37.59 3/3 mincross [7] [8] 70.8 0.00 37.59 3 mincross_step [8] 5.62 19.70 61/61 reorder [9] 0.00 12.23 2/4 transpose [11] 0.03 0.00 61/61 medians [61] ----------------------------------------------- 5.62 19.70 61/61 mincross_step [8] [9] 47.7 5.62 19.70 61 reorder [9] 18.57 0.00 271613167/295628726 left2right [12] 1.13 0.00 68037959/68208963 exchange [21] ----------------------------------------------- 3.38 21.09 11668/11668 transpose [11] [10] 46.1 3.38 21.09 11668 transpose_step [10] 11.67 0.00 48031108/48031108 out_cross [14] 7.78 0.00 48030866/48030866 in_cross [15] 1.64 0.00 24015559/295628726 left2right [12] 0.00 0.00 171004/68208963 exchange [21] ----------------------------------------------- 0.00 12.23 2/4 build_ranks [13] 0.00 12.23 2/4 mincross_step [8] [11] 46.1 0.00 24.47 4 transpose [11] 3.38 21.09 11668/11668 transpose_step [10] ----------------------------------------------- 1.64 0.00 24015559/295628726 transpose_step [10] 18.57 0.00 271613167/295628726 reorder [9] [12] 38.1 20.21 0.00 295628726 left2right [12] ----------------------------------------------- 0.04 12.68 2/2 mincross [7] [13] 24.0 0.04 12.68 2 build_ranks [13] 0.00 12.23 2/4 transpose [11] 0.00 0.41 2/6 ncross [20] 0.04 0.00 90666/90666 enqueue_neighbors [48] 0.00 0.00 90989/91392 dequeue [284] 0.00 0.00 90666/90666 install_in_rank [287] 0.00 0.00 321/91068 enqueue [286] 0.00 0.00 2/3 new_queue [448] 0.00 0.00 2/7 dot_root [439] 0.00 0.00 2/3 free_queue [447] ----------------------------------------------- 11.67 0.00 48031108/48031108 transpose_step [10] [14] 22.0 11.67 0.00 48031108 out_cross [14] ----------------------------------------------- 7.78 0.00 48030866/48030866 transpose_step [10] [15] 14.7 7.78 0.00 48030866 in_cross [15] ----------------------------------------------- 0.00 1.32 1/1 dotLayout [5] [16] 2.5 0.00 1.32 1 dot_rank [16] 0.00 1.32 1/1 dot1_rank [17] 0.00 0.00 1/23309 agget [126] ----------------------------------------------- 0.00 1.32 1/1 dot_rank [16] [17] 2.5 0.00 1.32 1 dot1_rank [17] 0.15 1.14 1/1 cleanup1 [18] 0.00 0.02 1/2 decompose [58] 0.01 0.00 1/1 class1 [81] 0.00 0.00 1/1 expand_ranksets [178] 0.00 0.00 1/1 collapse_sets [181] 0.00 0.00 1/1 acyclic [205] 0.00 0.00 1/1 rank1 [242] 0.00 0.00 1/1 edgelabel_ranks [488] 0.00 0.00 1/1 minmax_edges [528] 0.00 0.00 1/1 minmax_edges2 [529] ----------------------------------------------- 0.15 1.14 1/1 dot1_rank [17] [18] 2.4 0.15 1.14 1 cleanup1 [18] 0.07 0.83 7131528/7219869 agnxtout [23] 0.00 0.13 1144632/1164624 agfstout [34] 0.00 0.11 1144632/1181249 agnxtnode [39] 0.00 0.00 888/956 agfstnode [183] 0.00 0.00 804/804 renewlist [365] ----------------------------------------------- 1.22 0.00 152/152 ncross [20] [19] 2.3 1.22 0.00 152 rcross [19] 0.00 0.00 6/106093 grealloc [91] 0.00 0.00 1/298378 gmalloc [270] ----------------------------------------------- 0.00 0.41 2/6 build_ranks [13] 0.00 0.81 4/6 mincross [7] [20] 2.3 0.00 1.22 6 ncross [20] 1.22 0.00 152/152 rcross [19] ----------------------------------------------- 0.00 0.00 171004/68208963 transpose_step [10] 1.13 0.00 68037959/68208963 reorder [9] [21] 2.1 1.14 0.00 68208963 exchange [21] ----------------------------------------------- 0.00 0.00 2/10757223 dtclose [247] 0.00 0.00 3/10757223 agdtdelete [232] 0.00 0.00 5/10757223 agcopydict [223] 0.00 0.00 16/10757223 agopen1 [100] 0.00 0.00 16/10757223 agfindsubg_by_id [154] 0.00 0.00 27/10757223 setattr [106] 0.00 0.00 80/10757223 dtvsearch [216] 0.00 0.00 94/10757223 write_dict [201] 0.00 0.00 920/10757223 agnxtin [179] 0.00 0.00 956/10757223 agfstnode [183] 0.00 0.00 1008/10757223 not_default_attrs [180] 0.00 0.00 1347/10757223 storeline [165] 0.00 0.00 1348/10757223 emit_once [172] 0.00 0.00 2810/10757223 agfstin [161] 0.00 0.00 4384/10757223 installnode [160] 0.00 0.00 5418/10757223 agsubrep [41] 0.00 0.00 10218/10757223 agfindedge_by_key [151] 0.00 0.00 10856/10757223 agstrdup [66] 0.00 0.00 18348/10757223 agfstsubg [138] 0.00 0.00 32124/10757223 ins [118] 0.00 0.00 45135/10757223 agmakeattrs [79] 0.00 0.00 60493/10757223 agdictsym [111] 0.01 0.00 66232/10757223 write_nondefault_attrs [47] 0.02 0.00 196843/10757223 agnxtsubg [76] 0.03 0.00 354485/10757223 refsymbind [46] 0.03 0.00 378313/10757223 agfindnode_by_id [55] 0.10 0.00 1164624/10757223 agfstout [34] 0.10 0.00 1181249/10757223 agnxtnode [39] 0.59 0.03 7219869/10757223 agnxtout [23] [22] 1.7 0.88 0.04 10757223 dttree [22] 0.03 0.00 1122837/1122837 agsubnodeidcmpf [59] 0.01 0.00 490059/490059 agsubnodeseqcmpf [86] 0.00 0.00 84622/84622 agedgeseqcmpf [288] 0.00 0.00 75931/75931 agedgeidcmpf [289] 0.00 0.00 1346/1346 textfont_comparf [358] 0.00 0.00 30/30 agraphidcmpf [420] 0.00 0.00 4/8 dtmemory [438] 0.00 0.00 3/3 agdictobjfree [446] 0.00 0.00 1/1 textfont_freef [541] 0.00 0.00 1/1 free_string_entry [495] 0.00 0.00 1/1 textfont_makef [542] ----------------------------------------------- 0.00 0.00 8031/7219869 dot_init_node_edge [105] 0.00 0.00 8031/7219869 allocate_ranks [148] 0.00 0.00 8031/7219869 class1 [81] 0.00 0.00 8031/7219869 emit_view [141] 0.00 0.00 8031/7219869 init_bb_node [152] 0.00 0.00 8031/7219869 write_body [33] 0.00 0.00 8031/7219869 set_attrwf [147] 0.00 0.00 16062/7219869 class2 [75] 0.00 0.00 16062/7219869 setattr [106] 0.07 0.83 7131528/7219869 cleanup1 [18] [23] 1.7 0.07 0.84 7219869 agnxtout [23] 0.59 0.03 7219869/10757223 dttree [22] 0.09 0.00 7219869/8431854 dtextract [40] 0.07 0.00 7219869/8431854 dtrestore [42] 0.07 0.00 7219869/9597041 agsubrep [41] ----------------------------------------------- [24] 0.4 0.22 0.00 mincross_clust [24] ----------------------------------------------- [25] 0.3 0.00 0.16 intr [25] 0.00 0.16 1/1 gvRenderJobs [26] 0.00 0.00 1/1 gvFreeContext [248] ----------------------------------------------- 0.00 0.16 1/1 intr [25] [26] 0.3 0.00 0.16 1 gvRenderJobs [26] 0.00 0.16 1/1 emit_graph [27] 0.00 0.00 1/1 init_bb [149] 0.00 0.00 1/1 init_gvc [222] 0.00 0.00 1/28014 agbindrec [104] 0.00 0.00 1/1 init_layering [255] 0.00 0.00 1/1 chkOrder [252] 0.00 0.00 1/1 init_job_viewport [254] 0.00 0.00 2/5 gv_fixLocale [440] 0.00 0.00 1/3 start_timer [449] 0.00 0.00 1/1 gvjobs_first [507] 0.00 0.00 1/1 gvrender_select [517] 0.00 0.00 1/1 gvrender_begin_job [513] 0.00 0.00 1/1 init_job_pad [523] 0.00 0.00 1/1 init_job_margin [522] 0.00 0.00 1/1 init_job_dpi [521] 0.00 0.00 1/1 init_job_pagination [524] 0.00 0.00 1/1 gvjobs_next [508] 0.00 0.00 1/2 elapsed_sec [455] 0.00 0.00 1/233224 agnameof [277] ----------------------------------------------- 0.00 0.16 1/1 gvRenderJobs [26] [27] 0.3 0.00 0.16 1 emit_graph [27] 0.00 0.16 1/1 emit_end_graph [29] 0.00 0.00 1/1 emit_page [140] 0.00 0.00 1/1 emit_begin_graph [143] 0.00 0.00 1289/1181249 agnxtnode [39] 0.00 0.00 1/35851 agattr [80] 0.00 0.00 1/956 agfstnode [183] 0.00 0.00 1/23106 late_string [192] 0.00 0.00 2/2 numPhysicalLayers [468] 0.00 0.00 2/3 validpage [450] 0.00 0.00 2/2 validlayer [472] 0.00 0.00 1/113 gvrender_comment [390] 0.00 0.00 1/1 firstlayer [493] 0.00 0.00 1/1 firstpage [494] 0.00 0.00 1/1 nextpage [532] 0.00 0.00 1/1 nextlayer [531] ----------------------------------------------- 0.00 0.16 1/1 gvrender_end_graph [30] [28] 0.3 0.00 0.16 1 dot_end_graph [28] 0.00 0.16 1/1 agwrite [31] 0.00 0.00 1/1 xdot_end_graph [220] ----------------------------------------------- 0.00 0.16 1/1 emit_graph [27] [29] 0.3 0.00 0.16 1 emit_end_graph [29] 0.00 0.16 1/1 gvrender_end_graph [30] 0.00 0.00 1/113 pop_obj_state [394] ----------------------------------------------- 0.00 0.16 1/1 emit_end_graph [29] [30] 0.3 0.00 0.16 1 gvrender_end_graph [30] 0.00 0.16 1/1 dot_end_graph [28] 0.00 0.00 1/1 gvdevice_format [504] ----------------------------------------------- 0.00 0.16 1/1 dot_end_graph [28] [31] 0.3 0.00 0.16 1 agwrite [31] 0.00 0.16 1/1 write_body [33] 0.00 0.00 1/1 set_attrwf [147] 0.00 0.00 1/17 write_hdr [198] 0.00 0.00 1/23309 agget [126] 0.00 0.00 1/17 write_trl [428] 0.00 0.00 1/2 gvflush [461] ----------------------------------------------- [32] 0.3 0.00 0.16 1+33 [32] 0.00 0.16 17 write_body [33] 0.00 0.00 17 write_subgs [195] ----------------------------------------------- 16 write_subgs [195] 0.00 0.16 1/1 agwrite [31] [33] 0.3 0.00 0.16 17 write_body [33] 0.00 0.07 8031/8031 write_edge_test [43] 0.00 0.04 8031/8031 write_edge [49] 0.00 0.04 10223/10223 write_node_test [50] 0.00 0.01 1289/1289 write_node [107] 0.00 0.00 8031/7219869 agnxtout [23] 0.00 0.00 2192/1164624 agfstout [34] 0.00 0.00 2192/1181249 agnxtnode [39] 0.00 0.00 17/956 agfstnode [183] 0.00 0.00 17/64026 agdatadict [131] 0.00 0.00 17/652471 agroot [267] 17 write_subgs [195] ----------------------------------------------- 0.00 0.00 1043/1164624 has_no_edges [167] 0.00 0.00 1289/1164624 dot_init_node_edge [105] 0.00 0.00 1289/1164624 allocate_ranks [148] 0.00 0.00 1289/1164624 class1 [81] 0.00 0.00 1289/1164624 emit_view [141] 0.00 0.00 1289/1164624 init_bb_node [152] 0.00 0.00 1289/1164624 set_attrwf [147] 0.00 0.00 2192/1164624 write_body [33] 0.00 0.00 2578/1164624 class2 [75] 0.00 0.00 6445/1164624 setattr [106] 0.00 0.13 1144632/1164624 cleanup1 [18] [34] 0.3 0.00 0.14 1164624 agfstout [34] 0.10 0.00 1164624/10757223 dttree [22] 0.01 0.00 1164624/8431854 dtextract [40] 0.01 0.00 1164624/8431854 dtrestore [42] 0.01 0.00 1164624/9597041 agsubrep [41] ----------------------------------------------- 0.01 0.12 1/1 agconcat [36] [35] 0.2 0.01 0.12 1 aagparse [35] 0.00 0.05 8031/8031 endedge [45] 0.02 0.01 179414/179414 aaglex [56] 0.01 0.00 16062/16062 getedgeitems [82] 0.00 0.01 18255/18255 appendnode [96] 0.00 0.01 16/16 opensubg [99] 0.00 0.01 2209/2209 endnode [103] 0.00 0.00 35716/35716 appendattr [123] 0.00 0.00 1/1 startgraph [159] 0.00 0.00 17/17 attrstmt [194] 0.00 0.00 1/1 freestack [226] 0.00 0.00 16/16 closesubg [429] 0.00 0.00 2/2 aagdestruct [451] 0.00 0.00 1/1 endgraph [490] ----------------------------------------------- 0.00 0.13 1/1 agread [37] [36] 0.2 0.00 0.13 1 agconcat [36] 0.01 0.12 1/1 aagparse [35] 0.00 0.00 1/1 aglexinit [483] ----------------------------------------------- 0.00 0.13 1/1 gvNextInputGraph [38] [37] 0.2 0.00 0.13 1 agread [37] 0.00 0.13 1/1 agconcat [36] ----------------------------------------------- 0.00 0.13 1/1 main [1] [38] 0.2 0.00 0.13 1 gvNextInputGraph [38] 0.00 0.13 1/1 agread [37] 0.00 0.00 1/1 agsetfile [484] 0.00 0.00 1/2 gvg_init [462] ----------------------------------------------- 0.00 0.00 903/1181249 collapse_rankset [182] 0.00 0.00 1289/1181249 allocate_ranks [148] 0.00 0.00 1289/1181249 expand_ranksets [178] 0.00 0.00 1289/1181249 class1 [81] 0.00 0.00 1289/1181249 emit_view [141] 0.00 0.00 1289/1181249 emit_graph [27] 0.00 0.00 1289/1181249 init_bb [149] 0.00 0.00 1289/1181249 attach_attrs_and_arrows [146] 0.00 0.00 1289/1181249 agnedges [174] 0.00 0.00 1289/1181249 set_attrwf [147] 0.00 0.00 2192/1181249 write_body [33] 0.00 0.00 2578/1181249 dot_init_node_edge [105] 0.00 0.00 2578/1181249 class2 [75] 0.00 0.00 2578/1181249 mark_clusters [169] 0.00 0.00 2578/1181249 decompose [58] 0.00 0.00 11609/1181249 setattr [106] 0.00 0.11 1144632/1181249 cleanup1 [18] [39] 0.2 0.00 0.11 1181249 agnxtnode [39] 0.10 0.00 1181249/10757223 dttree [22] 0.01 0.00 1181249/9597041 agsubrep [41] ----------------------------------------------- 0.00 0.00 920/8431854 agnxtin [179] 0.00 0.00 1289/8431854 cnt [197] 0.00 0.00 2810/8431854 agfstin [161] 0.00 0.00 10218/8431854 agfindedge_by_key [151] 0.00 0.00 32124/8431854 ins [118] 0.01 0.00 1164624/8431854 agfstout [34] 0.09 0.00 7219869/8431854 agnxtout [23] [40] 0.2 0.10 0.00 8431854 dtextract [40] ----------------------------------------------- 0.00 0.00 920/9597041 agnxtin [179] 0.00 0.00 1289/9597041 agdegree [193] 0.00 0.00 2810/9597041 agfstin [161] 0.00 0.00 10218/9597041 agfindedge_by_key [151] 0.00 0.00 16062/9597041 installedge [113] 0.01 0.00 1164624/9597041 agfstout [34] 0.01 0.00 1181249/9597041 agnxtnode [39] 0.07 0.00 7219869/9597041 agnxtout [23] [41] 0.2 0.09 0.00 9597041 agsubrep [41] 0.00 0.00 5418/10757223 dttree [22] ----------------------------------------------- 0.00 0.00 920/8431854 agnxtin [179] 0.00 0.00 1289/8431854 cnt [197] 0.00 0.00 2810/8431854 agfstin [161] 0.00 0.00 10218/8431854 agfindedge_by_key [151] 0.00 0.00 32124/8431854 ins [118] 0.01 0.00 1164624/8431854 agfstout [34] 0.07 0.00 7219869/8431854 agnxtout [23] [42] 0.2 0.08 0.00 8431854 dtrestore [42] ----------------------------------------------- 0.00 0.07 8031/8031 write_body [33] [43] 0.1 0.00 0.07 8031 write_edge_test [43] 0.03 0.01 128496/204776 irrelevant_subgraph [44] 0.00 0.02 128496/128496 agsubedge [68] 0.00 0.01 128496/196843 agnxtsubg [76] 0.00 0.00 8031/18348 agfstsubg [138] ----------------------------------------------- 0.00 0.00 16/204776 write_subgs [195] 0.01 0.01 76264/204776 node_in_subg [51] 0.03 0.01 128496/204776 write_edge_test [43] [44] 0.1 0.04 0.02 204776 irrelevant_subgraph [44] 0.00 0.02 614328/725810 agattrrec [67] 0.

ianamason commented 7 years ago

John,

Thanks for the effort, and the crystal clear instructions.

Stephen,

I followed John's instructions and let it run to completion. The top 100% are

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  Ks/call  Ks/call  name    
 30.26    641.25   641.25    26297     0.00     0.00  treesearch
 24.41   1158.59   517.34        2     0.26     1.03  feasible_tree
 21.97   1624.24   465.65    26297     0.00     0.00  tight_tree
 13.51   1910.66   286.41 2010816878     0.00     0.00  add_tree_edge
  6.85   2055.76   145.10 1917958723     0.00     0.00  incident
  0.72   2071.12    15.36 516005856     0.00     0.00  left2right
  0.44   2080.50     9.39 91821370     0.00     0.00  out_cross
  0.42   2089.48     8.98 91821080     0.00     0.00  in_cross
  0.26   2094.98     5.50 604904071     0.00     0.00  ccw
  0.23   2099.95     4.97     1339     0.00     0.00  dfs_range
  0.19   2103.89     3.94      104     0.00     0.00  reorder
  0.14   2106.84     2.95    22375     0.00     0.00  transpose_step
  0.06   2108.17     1.33     8815     0.00     0.00  limitBoxes
  0.06   2109.35     1.18 27077146     0.00     0.00  solve3
  0.05   2110.38     1.03 18354447     0.00     0.00  connecttris
  0.04   2111.20     0.82  3929721     0.00     0.00  isdiagonal
  0.04   2112.01     0.81     5577     0.00     0.00  enter_edge
  0.04   2112.82     0.81     1851     0.00     0.00  dfs_enter_outedge
  0.04   2113.62     0.81 117668088     0.00     0.00  exchange
  0.04   2114.39     0.77      230     0.00     0.00  rcross
  0.03   2114.97     0.58 27072261     0.00     0.00  splineintersectsline
  0.03   2115.51     0.54   405097     0.00     0.00  grealloc
  0.02   2116.01     0.50        2     0.00     0.00  init_rank
  0.02   2116.42     0.41 11126565     0.00     0.00  dttree
  0.02   2116.83     0.41 74285093     0.00     0.00  intersects
  0.02   2117.15     0.32     1280     0.00     0.00  rerank
  0.01   2117.36     0.21     3726     0.00     0.00  dfs_enter_inedge
  0.01   2117.52     0.16                             mincross_clust
  0.01   2117.67     0.15   212949     0.00     0.00  finddqsplit
  0.01   2117.78     0.11 31103786     0.00     0.00  points2coeff

the full output is here:

http://csl.sri.com/~iam/analysis.txt

Hope this helps.

Ian.

P.S. This is dot's output:

 $PREFIX/bin/dot_static -v rdotIn.xdot -Txdot -o rdotOut.xdot
dot_static - graphviz version 2.39.20161204.1538 (20161204.1538)
Using render: xdot:core
Using device: xdot:xdot:core
Using layout: dot:dot_layout
Demand loading of plugins is disabled.
    render  :  dot dot_json fig json json0 map mp pic pov ps svg tk vml xdot xdot_json
    layout  :  circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopi
    textlayout  :
    device  :  canon cmap cmapx cmapx_np dot dot_json eps fig gv imap imap_np ismap json json0 mp pic plain plain-ext pov ps ps2 svg svgz tk vml vmlz xdot xdot1.2 xdot1.4 xdot_json
    loadimage   :  (lib) eps gif jpe jpeg jpg png ps svg
pack info:
  mode   undefined
  size   0
  flags  0
  margin 8
pack info:
  mode   node
  size   0
  flags  0
fontname: "Times-Roman" resolved to: [internal times]
network simplex:  402 nodes 847 edges maxiter=1289 balance=1
network simplex: 402 nodes 847 edges 48 iter 0.00 sec
Maxrank = 26, minrank = 0
mincross: pass 0 iter 0 trying 0 cur_cross 5226015 best_cross 5226015
mincross: pass 0 iter 1 trying 0 cur_cross 5120414 best_cross 5120414
mincross: pass 1 iter 0 trying 0 cur_cross 4893817 best_cross 4893817
mincross: pass 1 iter 1 trying 1 cur_cross 5253852 best_cross 4893817
mincross: pass 2 iter 0 trying 0 cur_cross 4893817 best_cross 4893817
mincross: pass 2 iter 1 trying 1 cur_cross 5253852 best_cross 4893817
mincross temp: 4893817 crossings, 47.10 secs.
network simplex:  97406 nodes 149452 edges maxiter=1289 balance=2
network simplex: 100 200 300 400 500 600 700 800 900 1000
network simplex: 1100 1200
network simplex: 97406 nodes 149452 edges 1289 iter 2096.10 sec
routesplines: 8815 edges, 108845 boxes 21.00 sec
Using render: xdot:core
Using device: xdot:xdot:core
gvRenderJobs temp: 0.91 secs.

magneticnorth commented 7 years ago

Does valgrind say anything that seems important?

I tried gperftools pprof but can’t get function names, as in http://stackoverflow.com/questions/10562280/line-number-in-google-perftools-cpu-profiler-on-macosx http://stackoverflow.com/questions/10562280/line-number-in-google-perftools-cpu-profiler-on-macosx though I did try -Wl,-no_pie as suggested but it didn’t seem to help.

It does appear that tight_tree() is taking a lot of time, which means the solver is spending an unexpected large amount of time searching for an initial solution, for some reason.

ianamason commented 7 years ago

I have it valgrinding away (quietly so far). Probably, given the usual slow down, it will take all night. I'll add the results here in the morning.

magneticnorth commented 7 years ago

Thank you

Maybe I'll try building on an AWS node since mac OS X seems kind of troublesome.

On Sun, Dec 4, 2016 at 10:01 PM Ian A Mason notifications@github.com wrote:

I have it valgrinding away (quietly so far). Probably, given the usual slow down, it will take all night. I'll add the results here in the morning.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-264757805, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz-iMO1RnGKWOo7m7I5Yg6nBzdgnuks5rE36DgaJpZM4K3IQg .

ianamason commented 7 years ago

Nothing suspect...

valgrind $PREFIX/bin/dot_static -v rdotIn.xdot -Txdot -o rdotOut.xdot
==17208== Memcheck, a memory error detector
==17208== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==17208== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==17208== Command: /home/iam/bin/graphviz/bin/dot_static -v rdotIn.xdot -Txdot -o rdotOut.xdot
==17208==
dot_static - graphviz version 2.39.20161204.1538 (20161204.1538)
Using render: xdot:core
Using device: xdot:xdot:core
Using layout: dot:dot_layout
Demand loading of plugins is disabled.
    render  :  dot dot_json fig json json0 map mp pic pov ps svg tk vml xdot xdot_json
    layout  :  circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopi
    textlayout  :
    device  :  canon cmap cmapx cmapx_np dot dot_json eps fig gv imap imap_np ismap json json0 mp pic plain plain-ext pov ps ps2 svg svgz tk vml vmlz xdot xdot1.2 xdot1.4 xdot_json
    loadimage   :  (lib) eps gif jpe jpeg jpg png ps svg
pack info:
  mode   undefined
  size   0
  flags  0
  margin 8
pack info:
  mode   node
  size   0
  flags  0
fontname: "Times-Roman" resolved to: [internal times]
network simplex:  402 nodes 847 edges maxiter=1289 balance=1
network simplex: 402 nodes 847 edges 48 iter 0.07 sec
Maxrank = 26, minrank = 0
mincross: pass 0 iter 0 trying 0 cur_cross 5226015 best_cross 5226015
mincross: pass 0 iter 1 trying 0 cur_cross 5120414 best_cross 5120414
mincross: pass 1 iter 0 trying 0 cur_cross 4893817 best_cross 4893817
mincross: pass 1 iter 1 trying 1 cur_cross 5253852 best_cross 4893817
mincross: pass 2 iter 0 trying 0 cur_cross 4893817 best_cross 4893817
mincross: pass 2 iter 1 trying 1 cur_cross 5253852 best_cross 4893817
mincross temp: 4893817 crossings, 826.90 secs.
network simplex:  97406 nodes 149452 edges maxiter=1289 balance=2
network simplex: 100 200 300 400 500 600 700 800 900 1000
network simplex: 1100 1200
network simplex: 97406 nodes 149452 edges 1289 iter 10676.54 sec
routesplines: 8815 edges, 108845 boxes 757.52 sec
Using render: xdot:core
Using device: xdot:xdot:core
gvRenderJobs temp: 37.47 secs.
==17208==
==17208== Process terminating with default action of signal 27 (SIGPROF)
==17208==    at 0x58754BE: __open_nocancel (syscall-template.S:81)
==17208==    by 0x5885F50: write_gmon (gmon.c:360)
==17208==    by 0x5886659: _mcleanup (gmon.c:428)
==17208==    by 0x57C61A8: __run_exit_handlers (exit.c:82)
==17208==    by 0x57C61F4: exit (exit.c:104)
==17208==    by 0x57ABF4B: (below main) (libc-start.c:321)
==17208==
==17208== HEAP SUMMARY:
==17208==     in use at exit: 68,504,964 bytes in 393,384 blocks
==17208==   total heap usage: 1,721,761 allocs, 1,328,377 frees, 221,936,115 bytes allocated
==17208==
==17208== LEAK SUMMARY:
==17208==    definitely lost: 12,840 bytes in 274 blocks
==17208==    indirectly lost: 19,440 bytes in 81 blocks
==17208==      possibly lost: 90,616 bytes in 1,255 blocks
==17208==    still reachable: 68,382,068 bytes in 391,774 blocks
==17208==         suppressed: 0 bytes in 0 blocks
==17208== Rerun with --leak-check=full to see details of leaked memory
==17208==
==17208== For counts of detected and suppressed errors, rerun with: -v
==17208== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Profiling timer expired

magneticnorth commented 7 years ago

It’s easy to print the size of the tight tree when it is being incrementally computed in feasible_tree()….

... FT 105975 of 213718 FT 105976 of 213718 FT 105979 of 213718 FT 105981 of 213718 FT 105983 of 213718 FT 105984 of 213718 FT 105987 of 213718 FT 105992 of 213718 FT 106021 of 213718 FT 106022 of 213718 FT 106023 of 213718 FT 106025 of 213718 FT 106032 of 213718 …

Well, that's bad news. It appears there is some unusual degeneracy in this particular example that causes it to creep along constructing the tight tree (initial solution).

Also I still do not understand why each pass is so slow - a 2.4GHz i5 gets something like 30K MIPS, so |V|^2 of 40 billion doesn’t seem crazy.

We might be able to assign initial values to define a tight tree by explicitly left justifying all the objects in each level, then align the levels so there are tight edges between them. There can be other nodes around for things like cluster bounding boxes, flat edges etc. but that might get us most of the way there. (The example graph does not have clusters or flat edges as far as I can tell.)

Stephen

magneticnorth commented 7 years ago

OK, so we just need a nice, reliable linear time algorithm for initial level assignment of a dag with variable edge lengths. Humiliating. The present algorithm is based on, I guess, Kahn’s algorithm? for topological sort, which may have to move large parts of the tree around to make each candidate edge tight, which I guess can possibly go into outer space orbit (|V|^3? why?) I’m sure some undergraduate can fix this for us ha ha

ellson commented 7 years ago

So, I guess I shouldn't hold up the graphviz-2.40 release to wait for this?

J.

On December 6, 2016 at 5:08 PM Stephen North notifications@github.com wrote:

OK, so we just need a nice, reliable linear time algorithm for initial
level assignment of a dag with variable edge lengths. Humiliating.
The present algorithm is based on, I guess, Kahn’s algorithm? for
topological sort, which may have to move large parts of the tree
around to make each candidate edge tight, which I guess can
possibly go into outer space orbit (|V|^3? why?) I’m sure some
undergraduate can fix this for us ha ha

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-265288528 , or mute the thread https://github.com/notifications/unsubscribe-auth/ABcTPQBaUdYE1iE27QT905ZjglSTNAm0ks5rFdzHgaJpZM4K3IQg .

ianamason commented 7 years ago

So my next avenue will be to try and trim the number of edges in the graph. Since it appears that we are not going to have a quick fix. Is this a possible route?

magneticnorth commented 7 years ago

We should recode feasible_tree()

On Wed, Dec 7, 2016 at 1:30 PM Ian A Mason notifications@github.com wrote:

So my next avenue will be to try and trim the number of edges in the graph.

Is this a possible route?

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-265530730, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz_Ky_T-5qB8D568mnoXCwW78Gu8Pks5rFvtJgaJpZM4K3IQg .

graphviz commented 7 years ago

Would the following work to compute the initial solution (in pseudocode):

for v in nodelist(G) level(v) = -MAXINT // indicates level not yet assigned

for v in nodelist(G) if indegree(v) == 0 { assert level(v) == -MAXINT assign(v) }

function assign(v) assert level(v) == -MAXINT if indegree(v) == 0 { level(v) = 0 } else { for e in inlist(v) { u = tail(v) if level(u) == -MAXINT { assign(u) } level(v) = MAX(level(v), level(u) + length(e)) } }

It would be easy to code. The only problem I see is that potentially the entire graph is pushed on the stack, so on really large inputs we could run out of stack space. I realize it is a common undergraduate programming exercise to convert a recursive algorithm to a non-recursive one but the day is long…

magneticnorth commented 7 years ago

No, that doesn’t work, many counterexamples.

The problem is if indegree(v) == 0 { level(v) = 0 } does not ensure the outedges of v are tight.

On Dec 8, 2016, at 10:45 PM, graphviz notifications@github.com wrote:

Would the following work to compute the initial solution (in pseudocode):

for v in nodelist(G) level(v) = -MAXINT // indicates level not yet assigned

for v in nodelist(G) if indegree(v) == 0 { assert level(v) == -MAXINT assign(v) }

function assign(v) assert level(v) == -MAXINT if indegree(v) == 0 { level(v) = 0 } else { for e in inlist(v) { u = tail(v) if level(u) == -MAXINT { assign(u) } level(v) = MAX(level(v), level(u) + length(e)) } }

It would be easy to code. The only problem I see is that potentially the entire graph is pushed on the stack, so on really large inputs we could run out of stack space. I realize it is a common undergraduate programming exercise to convert a recursive algorithm to a non-recursive one but the day is long…

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-265926352, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz2QdwKIhzpNZM05B94ieotfLS00qks5rGM69gaJpZM4K3IQg.

magneticnorth commented 7 years ago

Maybe we can use a heap. As the graph is being scanned, when we encounter nodes that cannot be scheduled (assigned a level) we put them in a heap or update them in the heap until they are ready to be scheduled (assigned a level). We keep the heap in the order of the lowest nodes in the DAG. I think this works because nodes are always connected by a tight edge when they are taken out of the heap and we never change the level of a node that was already scheduled. It should run pretty fast. Can someone code this right away ha ha

On Dec 8, 2016, at 10:45 PM, graphviz notifications@github.com wrote:

Would the following work to compute the initial solution (in pseudocode):

for v in nodelist(G) level(v) = -MAXINT // indicates level not yet assigned

for v in nodelist(G) if indegree(v) == 0 { assert level(v) == -MAXINT assign(v) }

function assign(v) assert level(v) == -MAXINT if indegree(v) == 0 { level(v) = 0 } else { for e in inlist(v) { u = tail(v) if level(u) == -MAXINT { assign(u) } level(v) = MAX(level(v), level(u) + length(e)) } }

It would be easy to code. The only problem I see is that potentially the entire graph is pushed on the stack, so on really large inputs we could run out of stack space. I realize it is a common undergraduate programming exercise to convert a recursive algorithm to a non-recursive one but the day is long…

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/1172#issuecomment-265926352, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz2QdwKIhzpNZM05B94ieotfLS00qks5rGM69gaJpZM4K3IQg.

graphviz commented 7 years ago

Upon further reflection, I can see the current algorithm is mostly correct - it constructs a forest of tight trees and then chooses one as the current solution and merges in the subtrees not yet connected. Each merge pass scans the current solution to finds a candidate edge to bring in to merge in the subtree on the other side.

In the pathological example we have, the current solution is about |V|/2 but the subtree being merged is only 1 or 2 nodes, so it goes very slowly.

It could be possible to keep track of the sizes of all the trees and in each merge pass, do work proportional to the smaller tree being merged in. (Just mumbling here but might need union-find to keep track of the tree merges but at least that’s cheap.)

Shouldn’t we have undergraduates or interns to help with these sort of problems :-)

magneticnorth commented 7 years ago

OK, I’ve figured out a fix.

The difficulty arises because the initial tight tree is built by discovering subtrees and merging them. “Merge” means adjusting the levels of the nodes in a subtree so it is tight against another subtree. This is done incrementally until the entire graph is spanned by a tight subtree. The current implementation moves the entire subtree discovered so far. If only a few additional nodes are added by this process then it progresses very slowly, e.g. the current solution has |V|/2 nodes and if we only add a small constant number of nodes, the running time is O(|V|^2).

A potential solution is: find the first subtree root and get the first tight subtree. Scan the rest of the graph. For each of the other subtree roots, get its tight subtree and find the slack w.r.t. the previous solution. Move the subtree down by the amount of the slack so it is tight against the previous solution. Now there is just one tight subtree again. Iterate. This will pick up the entire graph in linear time. I will start coding this. It should be simpler than the existing code too.

ianamason commented 7 years ago

That is excellent news Stephen! We look forward to stress testing it for you...

graphviz commented 7 years ago

I’m bogus. There is no way to guarantee that the second tight subtree has a potential tight edge to the first subtree so they can be merged.

I’m just riffing here, but it may be possible to find all the subtrees, then just start merging them bottom up until they are all merged but not predetermine the order of the merge.

Don’t we have interns for this? I mean, doesn’t our lab in exile at Google have interns for this?

magneticnorth commented 7 years ago

OK this is how it should work.

We construct an initial level assignment using the current method which is just breadth first search from the nodes with indegree(0).

Then find all the tight subtrees of this assignment which takes linear time.

We need to merge all the subtrees into one tree where all the edges are tight. To do this, put the subtrees in a heap ordered ascending subtree size. For each tight subtree when it is visited, find the most constrained edge to another subtree, and adjust the smaller subtree so it is tight. Continue until all the subtrees are merged, which is guaranteed.

I believe this is N log N (due to subtree merge depth) not N^2 like our current alg.

Let me know when the interns would like to meet to discuss it!

magneticnorth commented 7 years ago

Snow day today, so I coded the new tight subtree merge, and it works well. $ time dot_static dotIn.xdot -o /dev/null

real 4m18.03s user 4m8.14s sys 0m2.25s $

I don't know if the layout is usable, but the solver seems OK. Here's a TODO list: It needs more testing. It leaks memory from ns.c lines 298, 406, 490 - I think the subtree descriptors can only be freed at the end of feasible_tree() because they can be referenced even after subtrees are merged. We should check the new alg. with valgrind. All the new(?) compilation warnings with clang LLVM 8.0 are annoying. A few debug printfs are commented out but maybe should be put back in and depend on the runtime debug level. I probably broke the formatting because I'm confused about what we're doing with tabs and spaces these days. That's what I have right now. I'm not checking this code in yet because of the above problems. When I have time I'll figure out how to use GitHub more reasonably. Hope this is useful.

ns.c.txt

ianamason commented 7 years ago

That is great news Stephen. I have to do penance and go home for a summery xmas tomorrow, but I will be back in the first few days of new year to try this out.

magneticnorth commented 7 years ago

Issue was fixed by rewrite of tight_tree() in lib/common.ns.c, took a few iterations to get it right,

ianamason commented 7 years ago

Stephen,

So I have been testing it, and it has been handling the stress. I'm about to hand it off to the biologists, so if they can't break it we can take the rest of the decade off.

Thanks again for all your effort.

Cheers, Ian.

ianamason commented 7 years ago

@magneticnorth asked:

Hi Ian. Can the biologists that use this software actually see anything meaningful in such large graphs?

but I do not see the question here, so here is the answer anyway. Just another GitHub oddity.

Stephen, That's the $64,000 question. I have tweaked the tool so they can do a lot of stuff without displaying the graph, but they have a button that will display it if they cannot help themselves. From looking at the graphs myself, I think we need to reduce the edges (perhaps by not showing "enzymes" to the rules), the number of nodes seems fine. In my hacking I goofed and was drawing the graphs without rendering the edges for a time, and that actually seemed like a good thing, so we shall see. I did have to optimize the java painting too.

emden commented 7 years ago

Did the test graph change? The initial run reported 73 ranks, but later on, I see reports of 26 ranks. And I am still getting 73.

Concerning how to get a better visualization, there are 3 tricks that immediately come to mind: transitive reduction, unflattening, and making edges semi-transparent. I have used the Graphviz tred tool to great effect frequently, but the current implementation limits its use for larger graphs. It would be worthwhile seeing if this code could be rewritten. In theory, it should be O(EV).

One can use the unflatten tool, but it would also be worth the effort to turn on the aspect ratio code again. It doesn't work with clusters or disconnected graphs, but a lot of input doesn't have clusters, and one can get around the disconnected problem by using the pack attribute with dot.

ianamason commented 7 years ago

Yes there are two graphs in the fray: dotIn.xdot and rdotIn.xdot. The latter was when we added the inductive rank of the rules nodes into the generated dot, in an attempt to speed things up. I think we will first try eliminating the edges that are less semantically important and see where that gets us. semi-transparent edges sound interesting too, but my guess is they will still slow down the java rendering anyway, which is also a bit of a drag currently.

magneticnorth commented 7 years ago

but I do not see the question here, so here is the answer anyway. Just another GitHub oddity.

My fault, I sent the reply to your personal email but didn’t point that out. However the answer is interesting to everyone (or should be!)

emden commented 7 years ago

Thanks. I was misled that the number of edges and nodes was the same.

Removing less important edges is a big win. As for semi-transparency, try it before tossing it out. This appears to be well supported in current graphics systems.

emden commented 7 years ago

(I wish comments were numbered so you could specify which comment you were responding to.)

Following up on Stephen's comment two above, I'd like to recommend we use the issues for all communication about issues (unless we plan to resurrect the mailing list) and avoid private emails unless the comment really has limited relevance.

magneticnorth commented 7 years ago

Some of these conversations should become FAQs in the new web site.

ellson / MOTHBALLED-graphviz

[Dot] Spinning (also forum does not seem to be accepting questions.) #1172