Geografic-Information-System/lib/vector/dglib/examples

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