[Dot] Spinning (also forum does not seem to be accepting questions.) #1172
Comments
wonder if this is related to recent work on eliminating compile time |
|
OK so I spoke to soon. It eventually finished. But I would really like to be able to speed it up a bit.... 3.3 hours is The three hour run is the uncommented version. I have yet to succeed |
|
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
|
|
The graphs are generated by inductively closing a set of biological reaction rules. and when it starts to print to just over half an hour. This is still too long from the point of view of with the graph annotations being: 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 |
|
Maybe I can look at it next week. It seems like an algorithm bug :-( Sent from my iPad
|
|
That would be great! Let me know if you need any thing. I put the ranked graph here: |
|
I'm hoping this hasn't fallen through the cracks.... |
|
Maybe Graphviz needs a kickstarter project :-)
… On Dec 1, 2016, at 10:26 AM, Ian A Mason ***@***.***> 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 <#1172 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACtWz5p6hELxcAP21Aq-z2glERo6Hv75ks5rDucggaJpZM4K3IQg>.
|
|
Yes. Soon all science in the states will be funded by the NKF. |
|
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 ***@***.***> 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 <#1172 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACtWzzzoIxj15NcEGbiTwZB09wgLmNK7ks5rDu5hgaJpZM4K3IQg>.
|
|
National Kickstarter Foundation. |
|
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 ***@***.***> wrote:
National Kickstarter Foundation.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub <#1172 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACtWz9GqYyuICxJTzQxkyUWpJJw6kgWsks5rDu9KgaJpZM4K3IQg>.
|
|
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.
|
|
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
<#1172 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/ACtWz34oh5C-LqqU2ImBOHbFoZBoxuhEks5rDvrVgaJpZM4K3IQg>
.
|
|
I could learn how to do this, if there are no other takers. gprof? |
|
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 ***@***.***> 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
<#1172 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/ACtWz4vmh5A3gFPuaZWRTfev6FReSbQsks5rEZU5gaJpZM4K3IQg>
.
|
|
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 ***@***.***> 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 <#1172 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACtWz4vmh5A3gFPuaZWRTfev6FReSbQsks5rEZU5gaJpZM4K3IQg>.
|
|
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. |
|
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 ***@***.***> 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 ***@***.***>
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
> <#1172 (comment)>,
> 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 #1172 (comment) , or mute the thread https://github.com/notifications/unsubscribe-auth/ABcTPTp_Cgwb528oA7Iw9L7CjYoHYK4jks5rEZBigaJpZM4K3IQg .
|
|
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 ***@***.***> 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 ***@***.***> 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 ***@***.***>
> 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
> > <#1172 (comment)>,
> > 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 #1172 (comment) , 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
<spontaneous>
[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 <cycle 1> [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]
-----------------------------------------------
<spontaneous>
[24] 0.4 0.22 0.00 mincross_clust [24]
-----------------------------------------------
<spontaneous>
[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 <cycle 1> [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 <cycle 1 as a whole> [32]
0.00 0.16 17 write_body <cycle 1> [33]
0.00 0.00 17 write_subgs <cycle 1> [195]
-----------------------------------------------
16 write_subgs <cycle 1> [195]
0.00 0.16 1/1 agwrite [31]
[33] 0.3 0.00 0.16 17 write_body <cycle 1> [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 <cycle 1> [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 <cycle 1> [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 <cycle 1> [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 <cycle 1> [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 <cycle 1> [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.
|
|
John, Thanks for the effort, and the crystal clear instructions. Stephen, I followed John's instructions and let it run to completion. the full output is here: http://csl.sri.com/~iam/analysis.txt Hope this helps. Ian. P.S. This is dot's output: |
|
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.
|
|
I have it valgrinding away (quietly so far). Probably, given the usual slow down, it will take all night. |
|
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 ***@***.***> 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
<#1172 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/ACtWz-iMO1RnGKWOo7m7I5Yg6nBzdgnuks5rE36DgaJpZM4K3IQg>
.
|
|
Nothing suspect... |
|
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
|
|
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
|
|
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 ***@***.***> 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 #1172 (comment) , or mute the thread https://github.com/notifications/unsubscribe-auth/ABcTPQBaUdYE1iE27QT905ZjglSTNAm0ks5rFdzHgaJpZM4K3IQg .
|
|
So my next avenue will be to try and trim the number of edges in the graph. |
|
We should recode feasible_tree()
…On Wed, Dec 7, 2016 at 1:30 PM Ian A Mason ***@***.***> 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
<#1172 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/ACtWz_Ky_T-5qB8D568mnoXCwW78Gu8Pks5rFvtJgaJpZM4K3IQg>
.
|
|
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…
|
|
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 ***@***.***> 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 <#1172 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACtWz2QdwKIhzpNZM05B94ieotfLS00qks5rGM69gaJpZM4K3IQg>.
|
|
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 ***@***.***> 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 <#1172 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACtWz2QdwKIhzpNZM05B94ieotfLS00qks5rGM69gaJpZM4K3IQg>.
|
|
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 :-)
|
|
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.
|
|
That is excellent news Stephen! We look forward to stress testing it for you... |
|
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?
|
|
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!
|
|
Snow day today, so I coded the new tight subtree merge, and it works well. real 4m18.03s 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. |
|
That is great news Stephen. I have to do penance and go home for a summery xmas tomorrow, but I |
|
Issue was fixed by rewrite of tight_tree() in lib/common.ns.c, took a few iterations to get it right, |
|
Stephen, So I have been testing it, and it has been handling the stress. I'm about to Thanks again for all your effort. Cheers, Ian. |
|
@magneticnorth asked: 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 |
|
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. |
|
Yes there are two graphs in the fray: dotIn.xdot and rdotIn.xdot. |
|
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!)
|
|
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. |
|
(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. |
|
Some of these conversations should become FAQs in the new web site.
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
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.
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
The text was updated successfully, but these errors were encountered: