summaryrefslogtreecommitdiff
path: root/doc/shortest.1
blob: a227efa08e9411407d4cd7450006cc23f5f8ec78 (plain)
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
.\" generated with Ronn/v0.7.3
.\" http://github.com/rtomayko/ronn/tree/0.7.3
.
.TH "SHORTEST" "1" "September 2017" "www.complex-networks.net" "www.complex-networks.net"
.
.SH "NAME"
\fBshortest\fR \- Compute the distance between one node and all the other nodes of a graph
.
.SH "SYNOPSIS"
\fBshortest\fR \fIgraph_in\fR \fInode\fR [SHOW]
.
.SH "DESCRIPTION"
\fBshortest\fR computes the distance (and the shortest paths) between a given node and all the other nodes of an undirected graph provided as input\. The program implements the Breadth\-First Search algorithm\.
.
.SH "PARAMETERS"
.
.TP
\fIgraph_in\fR
input graph (edge list) if equal to \fB\-\fR (dash), read the edge list from STDIN\.
.
.TP
\fInode\fR
The label of the node from which distances are to be computed
.
.TP
SHOW
If the third (optional) parameter is equal to \fBSHOW\fR, the program will dump on the standard error also all the shortest paths between \fInode\fR and all the other nodes of the graph
.
.SH "OUTPUT"
\fBshortest\fR prints on the standard output the distances betwen \fInode\fR and all the other nodes of the graph, in the format:
.
.IP "" 4
.
.nf

d0 d1 d2 d3\.\.\.\.\.
.
.fi
.
.IP "" 0
.
.P
where \fBd0\fR is the distance to node \fB0\fR, \fBd1\fR is the distance to node \fB1\fR, and so forth\. If \fBSHOW\fR is given, the list of all the shortest paths between \fInode\fR and the other nodes is printed on the standard error, one path per line, in the format:
.
.IP "" 4
.
.nf

label0 label1 label2 \.\.\. node
.
.fi
.
.IP "" 0
.
.P
where \fBlabel1\fR, \fBlabel2\fR, etc\. are the labels of a shortest path between \fBlabel0\fR and \fInode\fR
.
.SH "EXAMPLES"
The following command:
.
.IP "" 4
.
.nf

      $ shortest er_1000_5000\.net 25
      3 4 4 4 2\.\.\.\.\.\.\.
      $
.
.fi
.
.IP "" 0
.
.P
will show on output the distances between node 25 and all the other nodes in the graph \fBer_1000_5000\.net\fR\. If we invoke the program with:
.
.IP "" 4
.
.nf

      $ shortest er_1000_5000\.net 25 SHOW 2>er_1000_5000\.net_25_paths
      3 4 4 4 2\.\.\.\.\.\.\.
      $
.
.fi
.
.IP "" 0
.
.P
the program will dump on STDERR the list of all the shortest paths between \'node\' and all the other nodes of the graph\. Since we used the redirection \fB2>er_1000_5000\.net_25_paths\fR (which can be read "redirect STDERR to \'er_1000_5000\.net_25_paths\' "), the list of shortest paths will be written to the file \fBer_1000_5000\.net_25_paths\fR\.
.
.SH "SEE ALSO"
dijkstra(1), bet_dependency(1), betweenness(1), shortest_avg_max_hist(1)
.
.SH "REFERENCES"
.
.IP "\(bu" 4
V\. Latora, V\. Nicosia, G\. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 3, Cambridge University Press (2017)
.
.IP "\(bu" 4
V\. Latora, V\. Nicosia, G\. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 6, Cambridge University Press (2017)
.
.IP "" 0
.
.SH "AUTHORS"
(c) Vincenzo \'KatolaZ\' Nicosia 2009\-2017 \fB<v\.nicosia@qmul\.ac\.uk>\fR\.