1

OBJECTIVE

I have a file called graph that contains the textual description of a graph by listing all existing links between nodes. Each line contains one link, expressed like this :

number1->number2

Where number2 is the number of the node that receives a link from the node whose number is number1 (there is a link from number1 to number2).

I need to find the most "popular" node which is actually the node that receives the most links.

CONSTRAINTS

  1. I need to use only one command (with several pipes) not the sed or awk commands.

  2. The command line should display only two numbers: the number of the most popular node, and the number of links received by this node (not necessarily in that order).

WHAT'S INSIDE THE GRAPH FILE

110->41
74->125
117->29
135->85
24->68
34->25
58->81
18->77
108->20
36->89
45->43
75->28
57->18
135->5
74->126
18->7
40->63
18->123
9->17
133->2
86->10
91->12
125->74
133->25
121->53
135->41
55->81
60->25
16->78
47->40
112->30
12->99
71->107
135->42
31->53
108->99
54->55
49->69
37->24
26->31
64->93
47->65
98->14
108->34
15->60
80->119
40->65
41->110
42->13
95->56
134->62
18->29
40->47
43->125
103->102
18->93
79->68
21->35
87->116
108->124
40->29
94->75
48->33
59->20
18->119
18->63
51->17
45->133
18->22
6->72
43->15
108->127
73->115
12->98
77->88
43->102
29->67
12->106
65->30
46->94
126->13
77->135
126->129
52->10
43->129
89->67
118->91
109->57
80->134
18->38
7->123
25->121
114->21
13->125
62->50
46->28
43->70
99->108
24->130
14->9
126->85
8->116
89->36
128->34
28->109
126->5
95->86
20->83
95->76
86->111
89->112
103->78
132->39
53->121
41->54
101->122
18->33
18->116
133->120
129->85
12->71
19->46
12->118
59->25
79->6
81->58
119->127
31->26
15->59
92->7
33->44
123->124
40->112
86->74
30->47
79->111
27->23
18->71
75->94
38->29
77->75
120->104
99->127
23->22
75->32
11->115
52->111
79->130
40->89
4->114
89->4
123->7
17->97
85->53
18->11
55->54
93->96
43->126
126->42
113->8
40->8
35->21
130->127
9->98
83->131
3->64
105->103
18->68
23->122
0->77
124->25
52->67
77->25
48->1
17->103
48->10
111->79
56->52
104->105
69->129
18->27
29->115
8->114
108->25
61->106
48->6
68->118
118->68
130->124
135->125
18->14
67->92
4->80
17->100
10->132
106->61
39->19
8->113
40->38
88->66
15->39
46->32
9->43
37->111
1->35
128->109
91->128
40->117
18->64
20->77
82->25
86->87
18->6
37->79
66->31
86->33
43->125
16->2
107->88
47->117
47->88
20->135
73->84
32->49
72->54
89->84
52->56
29->132
117->52
50->78
43->108
61->19
18->0
9->0
86->7
39->64
44->86
12->43
11->116
1->21
90->51
40->3
18->95
78->131
100->16
127->130
133->100
126->41
76->95
114->25
63->27
118->51
34->128
76->50
27->25
131->82
116->66
43->45
35->15
17->4
36->40
122->3
78->82
102->105
18->107
17->120
5->129
114->15
2->48
133->16
84->73
18->115
18->37
81->24
18->130
123->113
97->5
37->72
91->90
20->24
115->38
96->25
1->15
70->101
89->97
79->37
22->101
40->100
3->25
40->36
14
  • 3
    Generally it's better to speak to a tutor / teacher if you are stuck on a homework question. – Philip Couling Feb 15 at 0:02
  • 2
    @PhilipCouling I'm sorry am I not allowed to ask questions like that on this website? (serious question) – William Feb 15 at 0:03
  • 6
    You are but... 1) it's often polite on any site to state that you are stuck with your homework 2) it's much better to state why you are stuck (what part of it can you do, what can't you do). 3) Assignments are often based on work taught in class. A lot of teachers will easily spot when someone (not in your class) gave you the answer. – Philip Couling Feb 15 at 0:16
  • 1
    What's the expected output for your sample input? – Mark Plotnick Feb 15 at 0:31
  • 1
    @William the most popular node being the one that is repeated? I can't see a repetition of a "node" in your sample. – schrodigerscatcuriosity Feb 15 at 0:36
3

This should work:

cut -d '>' -f 2 graph | sort | uniq -c | sort -n | tail -n 1

This will print the number of links to the node and the node on the same line (the number of links comes first, and the node is second). If you want them to appear on separate lines, use the following:

cut -d '>' -f 2 graph | sort | uniq -c | sort -n | tail -n 1 | tr ' ' '\n'

Or you could have nice human-readable output like this:

cut -d '>' -f 2 graph | sort | uniq -c | sort -n | tail -n 1 | xargs printf 'Number of links: %s\nNode: %s\n'

First, we cut the output with > as the delimiter and get the second field (-f 2), which is the node the edge leads to.

Next we use sort. We sort because otherwise uniq will not work as desired (uniq does not detect repeated lines unless they are adjacent).

Next we use uniq -c to get the counts for each node.

We sort again with the numerical order with the -n option. After this second sort, the output is in order from the node with the least number of incoming links to the node with the most incoming links.

tail -n 1 returns the last line, i.e., the line for the node with the most incoming links.

The tr part in the second version replaces the space character between the count and the node with a newline.

0
1

Read man cut sort uniq tail and do something like

cut '-d>' -f 2 graph | \
  sort -n | \
  uniq -c | \
  sort -n | \
  tail -n 1
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.