## SOCNET@LISTS.UFL.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Monospaced Font

Subject:

Re: Searching for diameter calculation algoritm

From:

Date:

Wed, 12 Nov 2003 11:45:48 -0800

Content-Type:

text/plain

Parts/Attachments:

 text/plain (41 lines)
 ***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** Carl Nordlund wrote: > ***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** > > SocNetters, > > I am working on a small java program for drawing valued undirectional > graphs/networks while it calculates some network indices. However, I > cannot find a suitable algorithm for calculating geodesics and > diameters. I could, I guess, calculate the geodesic by dichotomizing the > matrix and calculating the power matrices until all the blanks are > filled in (Shimbel-style) - but is that the best algorithm for > calculating the geodesic? And what algorithms are available for > calculating diameters? All I can think of is a recursive n2-iterative > djikstra solution! > > I currently store the network as a graph (nodes as objects and edges as > objects referring to two node-objects) but I would prefer to calculate > geodesics and diameters from sociomatrices (which poses problems with > using the djikstra, right?) > > Thanks for any advice! > Try Ahuja et al.'s (1993) _Network Flows: Theory, Algorithms, and Applications_ for a variety of algorithms. As for the diameter, you can find it as a byproduct of the all-pairs shortest path problem (just look for the maximum geodesic). The manner in which your data is stored (sociomatrices, linked lists, etc.) should not pose problems here, although some storage schemes are more efficient than others. Hope that helps, -Carter _____________________________________________________________________ SOCNET is a service of INSNA, the professional association for social network researchers (http://www.sfu.ca/~insna/). To unsubscribe, send an email message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of the message.