README
1GRAPH.TXT : text description of a graph
2
3$ cr_from_a --file=GRAPH.TXT --graph=graph.dgl
4
5 read GRAPH.TXT and create graph.dgl
6
7
8
9
10$ view --graph=graph.dgl
11
12 View the graph.dgl content (node attributes are not printed)
13
14
15
16
17$ shortest_path --graph=graph.dgl --from=1 --to=80
18
19 Figure out shortest path from node 1 to node 5
20
21
22
23How to store X/Y/Z node coordinates:
24
25Node coordinates can be assigned as node attributes. In the GRAPH.TXT file
26lines beginning with 'A' are arcs, lines beginning with 'N' are node attributes.
27Each coordinate is stored as 32 bit integer. Thus when creating the graph
28(cr_from_a.c) I reserved 12 bytes for xyz values.
29See the GngSetNodeAttr() usage in cr_from_a.c
30The node attributes are passed back to the clip_node() callback during Dijkstra
31so that the user can check if the node is still into an arbitrary bounding box
32(see shortest_path.c).
33
34
35
36Clipping demo:
37
38Try to go from node 1 to node 80:
39
40$ ./shortest_path --graph=graph.dgl --from=1 --to=80
41
42See the result and then try to clip out node 3:
43
44$ ./shortest_path --graph=graph.dgl --from=1 --to=80 --discard=3
45
46The path will now use intermediate 2 instead of 3, resulting in a
47longer path.
48
49
50
51
52
53
54The test program cr_large_graph aims at figuring out performances, creating a graph of
55357202/60000 arc/node.
56Given that lot of insertion slowness depends on the node ids sorting, cr_large_graph can
57run in two ways: sorted ot interlaced.
58
59These are my time results (700Mhz intel):
60
61time ./cr_large_graph --graph=graphfile
62real 0m42.537s
63user 0m40.250s
64sys 0m1.060s
65
66time ./cr_large_graph --graph=graphfile --interlaced
67real 0m11.012s
68user 0m9.200s
69sys 0m1.020s
70
71
72When compiled with the -DGNGRP_STATS, cr_large_graph prints a line like this at (almost)
73each arc insertion:
74add arc 0238592 - from 0000203 - to 0000103 - cost 0010000 . Clock: tot 000000029 nt 000000015 nh 000000000 o 000000003
75
76The meaning of clocks are:
77tot = average number of clocks consumed by calls to gnGrpAddLink()
78nt = component of 'tot' spent in the node binary tree
79nh = component of 'tot' spent in the node heap
80o = component of 'tot' spent for all other operations
81
82Warn: the libdgl must also have been compiled with -DGNGRP_STATS.
83
84
85The next is the time spent to load 'graphfile' into memory and performing
86a shortest-path search from the node 0 to 59999 (that is from
87the upper-left to the lower-right of the network):
88
89time ./shortest_path --graph=graphfile --from=0 --to=59999
90real 0m4.579s
91user 0m3.940s
92sys 0m0.130s
93
94