| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394 |
- GRAPH.TXT : text description of a graph
- $ cr_from_a --file=GRAPH.TXT --graph=graph.dgl
- read GRAPH.TXT and create graph.dgl
- $ view --graph=graph.dgl
- View the graph.dgl content (node attributes are not printed)
- $ shortest_path --graph=graph.dgl --from=1 --to=80
- Figure out shortest path from node 1 to node 5
- How to store X/Y/Z node coordinates:
- Node coordinates can be assigned as node attributes. In the GRAPH.TXT file
- lines beginning with 'A' are arcs, lines beginning with 'N' are node attributes.
- Each coordinate is stored as 32 bit integer. Thus when creating the graph
- (cr_from_a.c) I reserved 12 bytes for xyz values.
- See the GngSetNodeAttr() usage in cr_from_a.c
- The node attributes are passed back to the clip_node() callback during Dijkstra
- so that the user can check if the node is still into an arbitrary bounding box
- (see shortest_path.c).
- Clipping demo:
- Try to go from node 1 to node 80:
- $ ./shortest_path --graph=graph.dgl --from=1 --to=80
- See the result and then try to clip out node 3:
- $ ./shortest_path --graph=graph.dgl --from=1 --to=80 --discard=3
- The path will now use intermediate 2 instead of 3, resulting in a
- longer path.
- The test program cr_large_graph aims at figuring out performances, creating a graph of
- 357202/60000 arc/node.
- Given that lot of insertion slowness depends on the node ids sorting, cr_large_graph can
- run in two ways: sorted ot interlaced.
- These are my time results (700Mhz intel):
- time ./cr_large_graph --graph=graphfile
- real 0m42.537s
- user 0m40.250s
- sys 0m1.060s
- time ./cr_large_graph --graph=graphfile --interlaced
- real 0m11.012s
- user 0m9.200s
- sys 0m1.020s
- When compiled with the -DGNGRP_STATS, cr_large_graph prints a line like this at (almost)
- each arc insertion:
- add arc 0238592 - from 0000203 - to 0000103 - cost 0010000 . Clock: tot 000000029 nt 000000015 nh 000000000 o 000000003
- The meaning of clocks are:
- tot = average number of clocks consumed by calls to gnGrpAddLink()
- nt = component of 'tot' spent in the node binary tree
- nh = component of 'tot' spent in the node heap
- o = component of 'tot' spent for all other operations
- Warn: the libdgl must also have been compiled with -DGNGRP_STATS.
- The next is the time spent to load 'graphfile' into memory and performing
- a shortest-path search from the node 0 to 59999 (that is from
- the upper-left to the lower-right of the network):
- time ./shortest_path --graph=graphfile --from=0 --to=59999
- real 0m4.579s
- user 0m3.940s
- sys 0m0.130s
|
