-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
134 lines (85 loc) · 3.35 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
Algorithms Coursework: Small-World Network Average Path Lengths
===============================================================
Implementation
--------------
Our implementation is written in C. To compile:
$ make
This builds some binaries:
- run_test
This generates and analyses a small world network, and prints out the maximum
distance, total path length, and the average path length.
The options are as follows:
./run_test [-n nodes] [-k distance] [-b rand] [-p] [-g file]
-n: The number of nodes in the graph.
-k: The distance of the furthest neighbour.
-b: The small-world randomisation (should be a float in the interval [0, 1]).
-p: Whether to use parallelisation for graph processing.
-g: File to save the graph to in graphviz format.
To render a graph:
$ ./run_test -g /tmp/graph
$ circo /tmp/graph -Tpng > /tmp/graph.png
$ eog /tmp/graph.png
- run_tests
This runs a load of tests (21000 in total) with various parameters, printing
a csv file to stdout with the following fields:
num_nodes
The number of nodes in the graph.
out_degree
The number of neighbours each node is connected to in the generated ring
network.
randomisation
The probability of randomly re-wiring an edge.
L
The calculated average path length.
max_dist
The maximum found path length.
total_dist
The total path length.
time
The cpu time it took to run this test.
This takes about 1.5 hours to run on mcore48. This was ran three times; the
produced data files are in the `data` directory. The parameters can be adjusted fairly simply in the `main` function at the bottom of `run_tests.c`.
- packed_graph_test
A quick test of the packed_graph representation. This should produce no
errors, and not leak any memory.
Organisation
~~~~~~~~~~~~
The implementation is organised into several pairs of C and header files:
- digraph
A representation of a digraph where the out-degree of each node is fixed.
- graph
Contains a more flexible graph representation, where each node contains a
linked list of edges. Each edge is stored by two links in opposite directions
for fast traversal.
- packed_graph
Contains a more compact (and therefore slightly more efficient by about 10%)
representation of a graph, and a function for converting to this from the
digraph representation..
- small_world
Contains a function for small-worldifying a digraph (the most natural
representation for this), and a function for converting a digraph to a graph.
- dijkstra
Contains an implementation of Dijkstra's algorithm.
- pqueue
Contains an implementation of a binary-heap priority queue, used by
Dijkstra's algorithm.
- bfs
Contains an implementation of breadth-first search, and a parallelised
all-pairs shortest path function. This operates on a packed_graph.
- queue
Contains an implementation of a linked-list queue, used by BFS.
- stats.
Deals with various graph statistics.
Analysis
========
All analysis was performed in R. To run the plotting scripts, the following R
packages are required:
- reshape2
- plyr
- lattice
Scripts
~~~~~~~
- util.r
Contains functions for loading data from data files.
- plots.r
Plots the three graphs as seen on the poster into the `plots` directory.