-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
90 lines (67 loc) · 2.86 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
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9303
IAI-TR-93-10.ps.pdf:
chapter 8 describes algorithm for creating random maximal planar graphs
GRAPH algorithms
================
make
Should build the program randomgraph.
The graph file format is that of the LEDA package from the MPI Saarbruecken,
Germany, of Prof. K. Mehlhorn.
The whole ugraph.h package is motivated by that packages datatype
UGRAPH; the difference are plain ANSI-C instead C++, fewer bug ( :-) ) and
more features!
randomgraph
===========
randomgraph --> gives short intro
randomgraph 10 -s 12345 -o t.u --> generates random maximal planar graph in
file t.u with random generator seed 12345
Real random graph (seed is epoch time):
$ time ./randomgraph 1000000 -o t.u -s `date +%s`
-------------------------------------
malloc: 18 malloc-free: 0
real 0m3.220s
user 0m3.042s
sys 0m0.176s
s
Only new feature (in case file name ends with ".a"):
write embedding as 0-based adjacency list (for planar_graph_playground)
$ time ./randomgraph 7 -s 1234 -o t.a
-------------------------------------
malloc: 20 malloc-free: 0
real 0m0.002s
user 0m0.002s
sys 0m0.000s
$ cat t.a
[[1,3,5,6,4,2],[0,2,5,3],[0,4,6,5,1],[0,1,5],[0,6,2],[2,6,0,3,1],[5,2,4,0]]
$
"… -o - …" allows to write to stdout; in this case LEDA graph format is written (as if filename would have ".u" suffix).
Have a lot of fun,
Hermann Stamm-Wilbrandt.
P.S.: Any comments, bug reports, ... welcome!
Really 1994 code:
$ ls -lst
total 160
4 -rw-rw-r-- 1 stammw stammw 1080 Jun 21 20:14 LICENSE
4 -rw-r--r-- 1 stammw stammw 880 Jun 21 20:05 README
4 -rw-r--r-- 1 stammw stammw 1347 Jun 21 20:00 Makefile
4 -rw-r--r-- 1 stammw stammw 994 Nov 13 1997 array.h
4 -rw-r--r-- 1 stammw stammw 1735 Feb 14 1996 basic.h
12 -rw-r--r-- 1 stammw stammw 10593 Feb 10 1996 randomgraph.c
4 -rw-r--r-- 1 stammw stammw 2724 Dec 17 1994 is_embedding.c
4 -rw-r--r-- 1 stammw stammw 264 Dec 17 1994 is_embedding.h
16 -rw-r--r-- 1 stammw stammw 12939 Dec 13 1994 list.c
8 -rw-r--r-- 1 stammw stammw 7330 Dec 13 1994 list.h
4 -rw-r--r-- 1 stammw stammw 2008 Dec 13 1994 set.c
12 -rw-r--r-- 1 stammw stammw 9297 Dec 13 1994 ugraph.def
40 -rw-r--r-- 1 stammw stammw 36950 Dec 13 1994 ugraph.h
4 -rw-r--r-- 1 stammw stammw 2147 Nov 28 1994 array.c
4 -rw-r--r-- 1 stammw stammw 2119 Nov 11 1994 randomgrapho.c
4 -rw-r--r-- 1 stammw stammw 3807 Sep 13 1994 triangulate.c
4 -rw-r--r-- 1 stammw stammw 171 Jun 13 1994 randomgrapho.h
4 -rw-r--r-- 1 stammw stammw 35 Apr 15 1994 triangulate.h
4 -rw-r--r-- 1 stammw stammw 1517 Apr 15 1994 set.h
4 -rw-r--r-- 1 stammw stammw 1401 Mar 17 1994 basic.c
4 -rw-r--r-- 1 stammw stammw 2669 Mar 2 1994 b_urn.h
4 -rw-r--r-- 1 stammw stammw 1186 Mar 2 1994 b_stack.c
4 -rw-r--r-- 1 stammw stammw 902 Mar 2 1994 b_stack.h
$