generate level numbers


 
Thread Tools Search this Thread
Top Forums Shell Programming and Scripting generate level numbers
# 1  
Old 09-19-2007
generate level numbers

Hi...

I have a sequence of jobs and its predecessors..

Input

Job_Name Predecessor
A NULL
B1 A
B2 A
B3 B1
C B3
C B2

So based on these i have to generate the level Number
What i mean is

Let A be level 1
for B1 to happen it should have done A
so B1 level is A+1 = 1+1 = 2
and same for B2 it should have done A
so B2 level is A+1 = 1+1 = 2
for B3 to happen it should have done B1
so B3 level is B2+1 = 2+1 = 3

but for C to complete it should have done B2 and B3
so C is max(B2,B3)+1
C=max(2,3)+1=4

so the final out put should be

A NULL 1
B1 A 2
B2 A 2
B3 B1 3
C B3 4
C B2 4



I am not able to code the logic..

Please Help..
# 2  
Old 09-19-2007
Try...
Code:
$ cat file1
A NULL
B1 A
B2 A
B3 B1
C B3
C B2

$ awk '{print $0, a[$1]=1+a[$2]}' file1
A NULL 1
B1 A 2
B2 A 3
B3 B1 3
C B3 4
C B2 3

# 3  
Old 09-20-2007
As i told for C the problem comes

It should be max for the both..

That is
For C to complete it should have done B2 and B3

so C is max(B2,B3)+1

C=max(2,3)+1=4

but
Quote:
$ awk '{print $0, a[$1]=1+a[$2]}' file1
A NULL 1
B1 A 2
B2 A 3
B3 B1 3
C B3 4
C B2 3
this give both 3 and 4 but it should be max of it..


I can give u one more input file

A 0
B1 A
B2 A
B3 B1
C B3
C B2
D C
E C
F D
F E
I E

This is extention of previous

when i run the awk i get

A 0 1
B1 A 2
B2 A 2
B3 B1 3
C B3 4
C B2 3---- as it 3 here next one takes as 4 but it shoul be at level 5 ..
D C 4
E C 4
F D 5
F E 5
I E 5
# 4  
Old 09-20-2007
How about:
Code:
$ cat data1
A NULL
B1 A
B2 A
B3 B1
C B3
C B2
$ awk '{r[NR]=$0 ; k[NR]=$1 ; if(v[$1]<1+v[$2]) v[$1]=1+v[$2] } END { for (n=1; n<=NR; n++) print r[n] , v[k[n]]}' data1
A NULL 1
B1 A 2
B2 A 2
B3 B1 3
C B3 4
C B2 4
$

# 5  
Old 09-21-2007
Hi...

Thanks a lot for all the idea's

Its almost done... but ..... Smilie

I am doing this to generate the level Numbers for Jobs to run in the unix server.. The input we have is the job name and it Predecessor Job Name

Small change required..

Have a look at the picture i have inserted..

If the Input is like this

A 0
B 0
C 0
D 0
E A
E B
E C
F E
G E
H E
I G
Z H
Z D


its perfect and works great..

But the same input and change in order..

A 0
B 0
C 0
D 0
E A
E B
E C
Z H
Z D

F E
G E
H E
I G

currupts the output.. gets me

A 0 1
B 0 1
C 0 1
D 0 1
E A 2
E B 2
E C 2
Z H 2
Z D 2
F E 3
G E 3
H E 3
I G 4

Just for the Pictorial view see the file i uploaded...
we have almost 1200 Jobs and it very tedious todo it..

Please Help...

Expected Out put
A 0 1
B 0 1
C 0 1
D 0 1
E A 2
E B 2
E C 2
Z H 4
Z D 4
F E 3
G E 3
H E 3
I G 4

We also have a file where it shows the Job and its Successor..

IF it could be of any use...

It like this

A E
B E
C E
D Z
E F
E G
E H
G I
H Z
I NULL
Z NULL
generate level numbers-dependency_chartjpg

Last edited by pbsrinivas; 09-21-2007 at 10:54 AM.. Reason: got some more infor to add
# 6  
Old 09-21-2007
This will never work unless you sort the input so that each job comes after all of its predecessors. The data pairs you have represent a directed graph. Provided that that the directed graph is acyclic, such a sort should be possible and this is called a topological sort. Lucky for you, Unix has a program called tsort to do this. Try:
Code:
#! /usr/bin/ksh
sort $1 > temp1
tsort temp1 | sed '$d' | nl | sort -nr | cut -f2 | nl | awk '{print $2, $1}' | sort | join temp1 - | sort -k 3n | awk '{print $1,$2}' |\
awk '{r[NR]=$0 ; k[NR]=$1 ; if(v[$1]<1+v[$2]) v[$1]=1+v[$2] } END { for (n=1; n<=NR; n++) print r[n] , v[k[n]]}'
exit 0

But bear in mind that with a complex directed graph there will probably be several different ways to assign your level numbers. This will find one of them.
# 7  
Old 09-22-2007
Thanks a lot for the inputs..

Its working great.. but a small problem..

if we change the name of NODE "E" by P is does some thing unexpected..

like

just the same in put but change E as P

A 0
B 0
C 0
D 0
P A
P B
P C
Z H
Z D
F P
G P
H P
I G


the ouput i get.. (---- I have chaged ur script as $3 instead of $2....

sort $1 > temp1
tsort temp1 | sed '$d' | nl | sort -nr | cut -f2 | nl | awk '{print $2, $1}' | sort | join temp1 - | sort -k 3n | awk '{print $1,$3}' |\
awk '{r[NR]=$0 ; k[NR]=$1 ; if(v[$1]<1+v[$2]) v[$1]=1+v[$2] } END { for (n=1; n<=NR; n++) print r[n] , v[k[n]]}'
exit 0


A 0 1
B 0 1
C 0 1
D 0 1
F P 1
G P 1
H P 1
I G 2
P A 2
P B 2
P C 2
Z D 2
Z H 2


when E as E it great... no issues...

A 0 1
B 0 1
C 0 1
D 0 1
E A 2
E B 2
E C 2
F E 3
G E 3
H E 3
I G 4
Z D 4
Z H 4

by that i saw the tsort is fine..
but when the name of the jobs are in aphabetical order it has no problem

till this both produce same output

sort $1 > temp1
tsort temp1 | sed '$d' | nl | sort -nr | cut -f2 | nl | awk '{print $2, $1}'

but after that the sort |join temp1 - scatter the feilds..

Last edited by pbsrinivas; 09-22-2007 at 01:52 AM.. Reason: wrong anylisis... tsort is fine..... more analysis
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Script to generate sequence of numbers

I need awk script to generate part number sequencing based on data in multiple columns like below Input File --------- Col A|Col B|Col C| 1|a|x| 2|b|y| |c|z| | |m| | |n| And out put should be like 1ax 1ay 1az 1am 1an 1bx 1by (6 Replies)
Discussion started by: aramacha
6 Replies

2. Shell Programming and Scripting

Need advise to generate 10 character numbers example 0000000000 - 9999999999

Hi all, i need advise from all experts here. when i use command below to print number in 10 character printf "%010d\n" {0..999} it will give me output nicely starts from 0000000000 untillllllllllll 0000000994 0000000995 0000000996 0000000997 0000000998 0000000999 However. when i... (6 Replies)
Discussion started by: jason6247
6 Replies

3. Shell Programming and Scripting

Auto generate Line Numbers

How do I generate line numbers in Vi? I have this: ,'04-90020-039N','61423','2GDV00039-0002', SYSDATE); ,'04-90020-040D','61423','2GDV00046-0001', SYSDATE); ,'04-90020-041N','61423','2GDV00038-0002', SYSDATE); ,'04-90020-043D','61423','2GDV00047-0001', SYSDATE);... (3 Replies)
Discussion started by: djehresmann
3 Replies

4. Shell Programming and Scripting

Generate random numbers in script

i want to generate a random number through a script, and even if anyone reads the script, they wont be able to figure out what the random number is. only the person who setup the script would know it. something like this could work: random the full thread is here: ... (13 Replies)
Discussion started by: SkySmart
13 Replies

5. Shell Programming and Scripting

Generate 16 digit positive random Numbers

Hi Unix Gurus, I have a requirement to generate positive random 16 and 13 digit numbers. Here is the script I have so far..... number=$RANDOM$RANDOM$RANDOM$RANDOM; let "number %= 10000000000000"; echo $number But sometimes it is generating negative numbers and also 15 digit... (8 Replies)
Discussion started by: scorpioraghu
8 Replies

6. Shell Programming and Scripting

Generate Codes based on start and End values of numbers in a column

Hello All, Could you please help with this. This is what I have: 506234.222 2 506234.222 2 506234.222 2 506234.222 2 508212.200 2 508212.200 2 333456.111 2 333456.111 2 333456.111 2 333456.111 2 But this is what I want: 506234.222 1 506234.222 2 506234.222 2 506234.222 3 (5 Replies)
Discussion started by: canimba
5 Replies

7. Programming

generate array of random numbers

hi guys, I am writing a c program that generates a two dimensional array to make matrix and a vector of random numbers and perform multiplication. I can't figure out whats wrong with my code. It generates a matrix of random numbers but all the numbers in the vector array is same and so is the... (2 Replies)
Discussion started by: saboture88
2 Replies

8. Shell Programming and Scripting

Generate numbers 000 to 999

I have tried to make this script to generate: 000 001 002 ... 997 998 999 i=0 while do if then echo "00"$i else if && then echo "0"$i (5 Replies)
Discussion started by: locoroco
5 Replies

9. Shell Programming and Scripting

How to generate 10.000 unique numbers?

hello, does anybody can give me a hint on how to generate a lot of numbers which are not identically via scripting etc? (7 Replies)
Discussion started by: xrays
7 Replies

10. Shell Programming and Scripting

How to generate a series of numbers

Hi All, I have a requirement where in I have an input as follows:- input=1-4,6,8-10,12-15 I need to explode this range into an output file as follows:- 1 2 3 4 6 8 9 10 12 13 14 15 My input may vary like 1,5-9,11-13,15-17....... (3 Replies)
Discussion started by: rony_daniel
3 Replies
Login or Register to Ask a Question