icse99-2.ps

clustering tools and may use for research

01F0000F14F8391FC000FC003F14FEA24848137E157FA212FFA290B6FCA20180C7FCA412
7FA36C6C1307121F150E6C7E6C6C131C6C6C13783900FE03E090383FFFC0903807FE0020
207E9F25>101 D<EB01FE90380FFF8090381FC3C090387F07E09038FE0FF0120113FC12
03EC07E0EC018091C7FCA8B512FCA3D803FCC7FCB3A8387FFFF0A31C327EB119>I<9039
1FF007C09039FFFE3FE03A01F83F79F03907E00FC3000F14E19039C007E0E0001FECF000
A2003F80A5001F5CA2000F5CEBE00F00075C2603F83FC7FC3806FFFE380E1FF090C9FC12
1EA2121F7F90B57E6C14F015FC6C806C801680000F15C0003FC7127F007EEC1FE0007C14
0F00FC1407A4007EEC0FC0003E1580003F141FD80FC0EB7E003907F803FC0001B512F0D8
001F90C7FC242F7E9F28>I<EA01F812FFA3120F1207ADEC07F8EC3FFEEC783F02C01380
9039F9801FC0EBFB0001FE14E05BA35BB3B500C3B5FCA328327DB12D>I<EA03C0487E48
7E487EA46C5A6C5A6C5AC8FCA9EA01F8127FA31207B3A7B51280A311337DB217>I<EA01
F812FFA3120F1207B3B3A6B512C0A312327DB117>108 D<2703F007F8EB1FE000FFD93F
FEEBFFF8913A783F01E0FC02C090388300FE280FF1801FC6137F2607F30013CC01F602F8
148001FC5CA3495CB3B500C3B5380FFFFCA33E207D9F43>I<3903F007F800FFEB3FFEEC
783F02C013803A0FF1801FC03807F30001F614E013FCA35BB3B500C3B5FCA328207D9F2D
>I<EB07FC90387FFFC03901FC07F03903F001F848486C7E4848137E001F147F003F1580
49133F007F15C0A300FF15E0A8007F15C0A36C6CEB7F80A2001F15006C6C13FE00075C39
03F803F83901FE0FF039007FFFC0D907FCC7FC23207E9F28>I<3803F03F00FFEB7FC090
38F1C3E01487390FF30FF0EA07F6A29038FC07E0EC03C091C7FCA25BB2B512E0A31C207E
9F21>114 D<3801FF86000713FEEA1F00003C133E48131E140E12F8A36C90C7FCB47E13
FC387FFFC06C13F0806C7F00077F00017FEA003F01001380143F0060131F00E0130FA27E
15007E6C131E6C131C38FF807838F3FFF038C07F8019207D9F20>I<131CA5133CA3137C
A213FC120112031207381FFFFEB5FCA2D803FCC7FCB0EC0380A71201EC0700EA00FEEB7F
0EEB3FFCEB07F0192E7FAD1F>I<D801F8EB07E000FFEB03FFA3000FEB003F0007141FB3
153FA20003147FA26C6CEBDFF03A00FE039FFF90387FFF1FEB0FFC28207D9F2D>I<B53A
1FFFE03FF8A33C0FF000FE0007806D150300076EEB0700816D5D00039138FF800EA26C6C
486D5A15DF01FF153C6C9039038FE038A2D97F876D5A150702C714F0D93FCF6D5AECCE03
D91FFEEBF9C09138FC01FD16FF010F5D4A7EA26D486DC7FCA20103147E4A133EA26D4813
1C35207E9F3A>119 D<B5EB1FFCA3D80FF8EB03C0000715806D1307000315007F000114
0E7F6C5CA2EC803C017F1338ECC078013F1370ECE0F0011F5B14F1010F5B14F9903807FB
80A214FF6D90C7FCA26D5AA26D5AA21478A21470A214F05C1301007C5BEAFE035C49C8FC
5BEAFC1EEA787CEA3FF0EA0FC0262E7E9F2B>121 D E end
TeXDict begin

1 0 bop 224 -105 a Fp(Automatic)27 b(Clustering)f(of)h(Soft)n(w)n(are)g
(Systems)506 -14 y(using)f(a)h(Genetic)f(Algorithm)480
122 y Fo(D.)19 b(Do)n(v)m(al,)e(S.)i(Mancoridis,)f(B.)g(S.)g(Mitc)n
(hell)499 180 y Fn(Dept.)j(of)16 b(Mathematics)f(&)h(Computer)f
(Science)775 238 y(Drexel)g(Univ)o(ersit)o(y)736 296
y(3141)j(Chestn)o(ut)e(Street)716 354 y(Philadelphia,)f(P)l(A,)g(USA)
784 412 y(+1)i(215)g(895)h(6824)380 470 y(e-mail:)h Fm(f)p
Fn(uddo)o(v)m(al,)d(smancori,)f(bmitc)o(hel)p Fm(g)p
Fn(@)o(m)o(cs.dre)o(xel)o(.edu)-75 567 y Fl(ABSTRA)o(CT)-75
616 y Fk(Large)d(soft)o(w)o(are)g(systems)f(tend)i(to)e(ha)o(v)o(e)h(a)
f(ric)o(h)h(and)g(complex)-75 666 y(structure.)36 b(Designers)20
b(t)o(ypically)e(depict)i(the)g(structure)h(of)-75 716
y(soft)o(w)o(are)c(systems)g(as)g(one)h(or)f(more)f(directed)i(graphs.)
28 b(F)m(or)-75 766 y(example,)15 b(a)g(directed)i(graph)f(can)g(b)q(e)
h(used)g(to)e(describ)q(e)j(the)-75 816 y(mo)q(dules)c(\(or)h
(classes\))i(of)d(a)h(system)g(and)g(their)h(static)f(in)o(ter-)-75
865 y(relationships)21 b(using)f(no)q(des)i(and)f(directed)h(edges,)h
(resp)q(ec-)-75 915 y(tiv)o(ely)m(.)c(W)m(e)14 b(call)g(suc)o(h)h
(graphs)g(mo)q(dule)e(dep)q(endency)j(graphs)-75 965
y(\(MDGs\).)-75 1042 y(MDGs)h(can)g(b)q(e)h(large)e(and)h(complex)f
(graphs.)28 b(One)18 b(w)o(a)o(y)e(of)-75 1091 y(making)c(them)h(more)g
(accessible)j(is)e(to)g(partition)f(them,)g(sep-)-75
1141 y(arating)19 b(their)h(no)q(des)g(\()p Fj(i.e.,)g
Fk(mo)q(dules\))f(in)o(to)g(clusters)i(\()p Fj(i.e.,)-75
1191 y Fk(subsystems\).)39 b(In)20 b(this)h(pap)q(er,)h(w)o(e)f
(describ)q(e)h(a)f(tec)o(hnique)-75 1241 y(for)e(\014nding)g(\\go)q(o)q
(d")g(MDG)g(partitions.)34 b(Go)q(o)q(d)19 b(partitions)-75
1291 y(feature)d(relativ)o(ely)e(indep)q(enden)o(t)i(subsystems)g(that)
f(con)o(tain)-75 1341 y(mo)q(dules)i(whic)o(h)h(are)h(highly)e(in)o
(ter-dep)q(enden)o(t.)33 b(Our)19 b(tec)o(h-)-75 1390
y(nique)12 b(treats)h(\014nding)f(a)g(go)q(o)q(d)g(partition)f(as)h(an)
g(optimization)-75 1440 y(problem,)g(and)i(uses)h(a)e(Genetic)h
(Algorithm)e(\(GA\))i(to)f(searc)o(h)-75 1490 y(the)19
b(extraordinarily)e(large)g(solution)g(space)i(of)f(all)e(p)q(ossible)
-75 1540 y(MDG)g(partitions.)25 b(The)17 b(e\013ectiv)o(eness)i(of)d
(our)g(tec)o(hnique)i(is)-75 1590 y(demonstrated)10 b(b)o(y)h(applying)
e(it)h(to)g(a)g(medium-sized)e(soft)o(w)o(are)-75 1639
y(system.)-75 1716 y Fl(Keyw)o(ords)-75 1766 y Fk(Automatic)g
(Clustering,)i(Rev)o(erse)g(Engineering,)g(Genetic)g(Al-)-75
1816 y(gorithms.)-75 1892 y Fl(1)48 b(INTR)o(ODUCTION)-75
1942 y Fk(The)20 b(main)o(tenance)e(and)i(ev)o(olution)e(of)h(medium)e
(and)i(large)-75 1992 y(soft)o(w)o(are)f(systems)f(can)h(b)q(e)g(a)g
(daun)o(ting)e(task,)j(esp)q(ecially)e(if)-75 2042 y(the)c(system)g(is)
g(p)q(o)q(orly)f(do)q(cumen)o(ted)h(or)g(not)g(do)q(cumen)o(ted)g(at)
-75 2092 y(all.)27 b(Con)o(tin)o(uous)17 b(main)o(tenance)g(o)o(v)o(er)
g(an)g(extended)i(p)q(erio)q(d)-75 2141 y(of)c(time)e(can)j(ha)o(v)o(e)
f(a)f(negativ)o(e)h(impact)f(on)h(the)g(qualit)o(y)f(of)h(a)-75
2191 y(system's)h(structure)j(\(also)d(referred)j(to)d(as)h(Soft)o(w)o
(are)f(Arc)o(hi-)-75 2241 y(tecture)g([12)o(,)d(14]\).)-75
2318 y(Soft)o(w)o(are)24 b(designers)h(use)g(directed)g(graphs)f(to)g
(mak)o(e)f(the)1025 567 y(structure)11 b(of)e(complex)g(soft)o(w)o(are)
g(systems)h(more)f(understand-)1025 616 y(able.)27 b(W)m(e)17
b(call)f(suc)o(h)i(graphs)f(mo)q(dule)f(dep)q(endency)j(graphs)1025
666 y(\(MDGs\).)29 b(In)18 b(MDGs,)g(the)g(system's)f(mo)q(dules)g(\()p
Fj(e.g.,)h Fk(\014les,)1025 716 y(classes\))13 b(are)f(represen)o(ted)j
(as)d(no)q(des)g(and)g(their)g(relationships)1025 766
y(\()p Fj(e.g.,)23 b Fk(function)f(calls,)i(inheritance)f
(relationships\))f(as)h(di-)1025 816 y(rected)13 b(edges)h(that)e
(connect)h(the)g(no)q(des.)18 b(Ho)o(w)o(ev)o(er,)13
b(ev)o(en)f(the)1025 865 y(MDGs)17 b(of)g(small)e(systems)j(can)g(b)q
(e)g(complex.)28 b(One)19 b(w)o(a)o(y)e(of)1025 915 y(making)c(MDGs)i
(more)g(accessible)i(is)f(to)f(partition)g(them)g(b)o(y)1025
965 y(grouping)f(closely)i(related)g(no)q(des)g(in)o(to)f(clusters,)i
(in)e(what)g(is)1025 1015 y(kno)o(wn)c(as)i(the)g Fj(softwar)n(e)f
(clustering)h(pr)n(oblem)p Fk(.)k(The)c(MDG)f(of)1025
1065 y(a)i(soft)o(w)o(are)g(system)g(can)h(b)q(e)g(extracted)h
(automatically)11 b(from)1025 1114 y(its)h(source)h(co)q(de)h(using)e
(to)q(ols)g(suc)o(h)h(as)f(CIA)h([6)o(])f(\(for)g(C\),)g(Aca-)1025
1164 y(cia)h([1)o(])h(\(for)f(C)h(and)g(C++\))g(or)g(Star)g([7])f
(\(for)h(T)m(uring)f([4)o(]\).)1025 1241 y(Creating)j(a)g
Fj(me)n(aningful)21 b Fk(partition)16 b(of)g(an)g(MDG,)f(ho)o(w)o(ev)o
(er,)1025 1291 y(is)e(di\016cult,)g(b)q(ecause)i(the)f(n)o(um)o(b)q(er)
f(of)g(p)q(ossible)h(partitions)f(is)1025 1341 y(v)o(ery)k(large)g(ev)o
(en)h(for)e(a)h(small)e(graph)i([8)o(].)28 b(Also,)17
b(small)e(dif-)1025 1390 y(ferences)g(b)q(et)o(w)o(een)g(t)o(w)o(o)f
(partitions)f(can)h(yield)f(v)o(ery)h(di\013eren)o(t)1025
1440 y(qualitativ)o(e)h(results.)29 b(As)18 b(an)e(example,)h(let's)g
(consider)h(Fig-)1025 1490 y(ure)d(1,)f(whic)o(h)g(presen)o(ts)j(an)d
(MDG)g(with)g(a)g(small)f(n)o(um)o(b)q(er)h(of)1025 1540
y(mo)q(dules)9 b(and)h(relations.)16 b(\(All)10 b(diagrams)e(on)i(this)
g(pap)q(er)h(w)o(ere)1025 1590 y(pro)q(duced)h(using)g
Fj(dot)k Fk([6)o(],)11 b(a)g(to)q(ol)g(for)h(dra)o(wing)e(and)i
(automat-)1025 1639 y(ically)g(la)o(ying)g(out)i(lab)q(eled)g(directed)
h(graphs.\))1025 1716 y(The)g(t)o(w)o(o)f(partitions)h(of)f(the)i(MDG)e
(presen)o(ted)j(in)e(Figures)g(2)1025 1766 y(and)h(3)h(are)h(v)o(ery)f
(similar,)e(with)i(only)f(t)o(w)o(o)h(no)q(des)h(sw)o(app)q(ed.)1025
1816 y(In)13 b(spite)g(of)g(this)g(seemingly)f(small)e(di\013erence,)15
b(the)f(partition)1025 1865 y(de\014ned)f(in)g(Figure)g(3)f(b)q(etter)i
(captures)h(the)e(high-lev)o(el)f(struc-)1025 1915 y(ture)k(of)g(the)g
(graph,)g(since)h(it)f(groups)g(no)q(des)h(that)f(are)g(more)1025
1965 y(in)o(ter-dep)q(enden)o(t.)1025 2042 y(In)i(this)h(pap)q(er,)h(w)
o(e)f(describ)q(e)i(a)d(tec)o(hnique)i(that)f(automat-)1025
2092 y(ically)d(\014nds)i(a)g(go)q(o)q(d)f(partition)g(of)h(a)f
(system's)h(MDG.)e(Our)1025 2141 y(approac)o(h)e(treats)i(clustering)f
(as)g(an)f(optimization)e(problem,)1025 2191 y(where)f(the)g(goal)e(is)
h(to)g(\014nd)h(a)f(go)q(o)q(d)g(\(p)q(ossibly)g(optimal\))d(parti-)
1025 2241 y(tion.)16 b(T)m(o)10 b(explore)i(the)g(extraordinarily)e
(large)h(solution)f(space)1025 2291 y(of)h(all)g(p)q(ossible)i
(partitions)f(for)g(a)g(giv)o(en)g(MDG,)f(w)o(e)i(use)g(a)f(Ge-)1025
2341 y(netic)17 b(Algorithm)d(\(GA\))j([2)o(,)f(9].)25
b(In)17 b(Section)g(3)f(w)o(e)h(describ)q(e)1025 2390
y(ho)o(w)e(w)o(e)h(quan)o(tify)f(a)g(partition's)g(qualit)o(y)g(using)h
(features)h(of)1025 2440 y(the)d(graph.)1025 2517 y(W)m(e)k
(demonstrate)g(the)i(e\013ectiv)o(eness)h(of)d(our)h(tec)o(hnique)g(on)
1025 2567 y(a)c(medium-sized)e(soft)o(w)o(are)j(system.)23
b(The)16 b(to)q(ol)f(that)h(imple-)1025 2616 y(men)o(ts)f(our)h(tec)o
(hnique)h(uses)h(the)e(system's)g(MDG)f(as)i(input,)1025
2666 y(and)c(pro)q(duces)j(a)d(partition)g(of)h(that)g(MDG)f(as)h
(output.)p eop
2 1 bop 105 -9 a
 gsave currentpoint currentpoint translate -90 neg rotate neg exch
neg exch translate
 105 -9 a @beginspecial 36 @llx 36 @lly
289 @urx 247 @ury 1842 @rwi @setspecial
save
/DotDict 200 dict def
DotDict begin

/coord-font-family /Times-Roman def
/default-font-family /Times-Roman def
/coordfont coord-font-family findfont 8 scalefont def

/InvScaleFactor 1.0 def
/set_scale {
	dup 1 exch div /InvScaleFactor exch def
	dup scale
} bind def

% styles
/solid { } bind def
/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def
/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def
/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def
/bold { 2 setlinewidth } bind def
/filled { } bind def
/unfilled { } bind def
/rounded { } bind def
/diagonals { } bind def

% hooks for setting color 
/nodecolor { sethsbcolor } bind def
/edgecolor { sethsbcolor } bind def
/graphcolor { sethsbcolor } bind def
/nopcolor {pop pop pop} bind def

/beginpage {	% i j npages
	/npages exch def
	/j exch def
	/i exch def
	/str 10 string def
	npages 1 gt {
		gsave
			coordfont setfont
			0 0 moveto
			(\() show i str cvs show (,) show j str cvs show (\)) show
		grestore
	} if
} bind def

/set_font {
	findfont exch
	scalefont setfont
} def

/arrowhead {
	/arrowwidth exch def
	/arrowlength exch def
	gsave
		3 1 roll
		translate
			rotate
			newpath
			arrowlength arrowwidth 2 div moveto
			0 0 lineto
			arrowlength arrowwidth -2 div lineto
		closepath fill
		stroke
	grestore
} def

% draw aligned label in bounding box aligned to current point
% alignfactor tells what fraction to place on the left.
% -.5 is centered.
/alignedtext {			% text labelwidth fontsz alignfactor
	/alignfactor exch def
	/fontsz exch def
	/width exch def
	/text exch def
	gsave
		% even if node or edge is dashed, don't paint text with dashes
		[] 0 setdash
		currentpoint newpath moveto
		text stringwidth pop
		alignfactor mul fontsz -.3 mul rmoveto
		text show
	grestore
} def

/boxprim {				% xcorner ycorner xsize ysize
		4 2 roll
		moveto
		2 copy
		exch 0 rlineto
		0 exch rlineto
		pop neg 0 rlineto
		closepath
} bind def

/ellipse_path {
	/ry exch def
	/rx exch def
	/y exch def
	/x exch def
	matrix currentmatrix
	newpath
	x y translate
	rx ry scale
	0 0 1 0 360 arc
	setmatrix
} bind def

/endpage { showpage } bind def

/layercolorseq
	[	% layer color sequence - darkest to lightest
		[0 0 0]
		[.2 .8 .8]
		[.4 .8 .8]
		[.6 .8 .8]
		[.8 .8 .8]
	]
def

/setlayer {/maxlayer exch def /curlayer exch def
	layercolorseq curlayer get
	aload pop sethsbcolor
	/nodecolor {nopcolor} def
	/edgecolor {nopcolor} def
	/graphcolor {nopcolor} def
} bind def

/onlayer { curlayer ne {invis} if } def

/onlayers {
	/myupper exch def
	/mylower exch def
	curlayer mylower lt
	curlayer myupper gt
	or
	{invis} if
} def

/curlayer 0 def

14 default-font-family set_font
% /arrowlength 10 def
% /arrowwidth 5 def
gsave
35 35 254 212 boxprim clip newpath
36 36 translate
gsave 252 0 translate 90 rotate
0 0 1 beginpage
grestore
252 0 translate 90 rotate
0.000 0.000 0.000 graphcolor
14.00 /Times-Roman set_font

%	N1
gsave 10 dict begin
filled
0.537 0.247 0.902 nodecolor
54 234 27 18 ellipse_path
gsave 0 setgray stroke grestore fill
gsave 10 dict begin
0.000 0.000 0.000 nodecolor
54 235 moveto (N1) 17 14.00 -0.50 alignedtext
end grestore
end grestore

%	N2
gsave 10 dict begin
filled
0.537 0.247 0.902 nodecolor