Diameter of a Graph

[The Hobo]

I need to write a function to compute the diameter of a graph given an array of edges, ie:

1, 2
1, 4
2, 3
3, 4

Any ideas on how to go about doing this?

[choey2k5]

the diameter? the coordinates plot a 45, 45, 90 triangle.

[The Hobo]

the diameter? the coordinates plot a 45, 45, 90 triangle.

There are four vertices, so it makes a square. I was spitting those off the top of my head, but regardless, the diameter would be 2.

The diameter of a graph is the greatest distance between two vertices.

Here's a better example. The diameter is 3:

1, 3
1, 6
1, 8
2, 5
2, 6
2, 7
3, 4
3, 8
4, 5
4, 9
6, 7
6, 8
8, 9

Any ideas on how to write a function to compute this?

[choey2k5]

just having the information that there are 4 coordinates does not mean that it'll plot a rectangle... there can be 50 thousand points that are colinear.

i guess you made a mistake when you pulled them out of your head because (1,2), (2,3), and (3,4) makes a straight line. just being picky

right off the head, i would have to guess that you should put the x's and y's in 2 arrays, and combinations of any 2 coordinates to find the distances, store them, and at the end find whatever value is the greatest, and go back to find out which 2 coordinates will give that value.

i'll think about it some more...

EDIT:

hmm... how is the diameter for those plots is 3? the slope is 3 and the distance between the farthest 2 points [ (1,3) and (8,9) ] is Sqrt(85), or about 9.2195. i don't think i understood this diameter thing right...

EDIT:

seems more complicated than i imagined
this might help: http://www.math.carleton.ca/~daniel/...y/allpairs.txt

[The Hobo]

I don't think I've explained this very well.

In my last example, 1-9 are all vertices within a graph. 1, 3 means that there is an edge between vertex 1 and 3. I think you're thinking more of traditional graph.

Sorry if I'm not explaining this very well.

So, for example, the distance between 1 and 3 is 1, because there's an edge between 1 and 3. The distance between 1 and 4 is 2, because the shortest way to get from 1 to 4 is 1 to 3, then 3 to 4.

[wossname]

I don't think I've explained this very well.

In my last example, 1-9 are all vertices within a graph. 1, 3 means that there is an edge between vertex 1 and 3. I think you're thinking more of traditional graph.

Sorry if I'm not explaining this very well.

So, for example, the distance between 1 and 3 is 1, because there's an edge between 1 and 3. The distance between 1 and 4 is 2, because the shortest way to get from 1 to 4 is 1 to 3, then 3 to 4.

Draw a rough picture in MSPaint, save it as a gif and post it up here.

[yrwyddfa]

Very difficult to do.

This is because although you express the edges and vertices as a visible picture it doesn't necessarily have to be the picture you've drawn.

Any graph can normally be drawn in many numbers of ways. Which means you can only find the diameter for a given graph drawing instance and not the graph itself.

What you will need to do is store the vertex coordinates alongside the graph. Once you've done this you can then find the outermost vertices and hence the outermost edges. Once you have a circular walk of the outermost vertices/edges you have the diameter (by summing the length of each edge on the walk)

The best way, I reckon of achieveing this is for a [i,j] matrix store k layers. The incidence matrix should be k=0, and k=1 could be x coordinates, k=2 could be y coordinates, and so on until k=n

Once you have this you figure out the circle that includes all of the vertices. You can then use the centre of that circle to figure out which vertices are the furthest away from the centre.

Then you go for a walk as they say . . .

(It may be easier to figure out the centre and use vector algebra to calculate distances)

[wossname]

Oh yeah, I forgot.