Bug #104687 for Graph: diameter and centre of a one vertex graph

Mon May 25 08:43:47 2015 user42_kevin [...] yahoo.com.au - Ticket created

Subject:	diameter and centre of a one vertex graph
Date:	Mon, 25 May 2015 22:42:28 +1000
To:	bug-Graph [...] rt.cpan.org
From:	Kevin Ryde <user42_kevin [...] yahoo.com.au>

If a graph has just one vertex, diameter() returns undef and centre returns an empty list. I expected diameter 0 and that vertex the centre. Sample foo.pl below printing variously undef and empty. Am I right 0 and one centre would be the usual definition for these things? It would mean a line graph of n vertices would have diameter n-1, and for n odd one centre. (I struck this on a spot of code doing a layout which was to start work at the centre of a tree.)

Message body is not shown because sender requested not to inline it.

Mon Sep 21 22:26:49 2015 JHI [...] cpan.org - Correspondence added

I think the diameter for a single-vertex graph (or for that matter, a graph of arbitrary many unconnected vertices, in other words, no edges) cannot be zero, because it's defined as the longest path over all the paths between vertex pairs. Since there are no edges, no paths, no diameter. A non-existing path (or a multiplicity of them) doesn't have zero length/weight. Similarly for the center vertices: it's the set of vertices where the vertex eccentricity is equal to the graph radius. Vertex eccentricity is the longest path to the vertex: if unconnected, Inf. The radius is the shortest path over all the vertex pairs: unconnected, it's not that well-defined... but since it's the shortest, Inf is unlikely. On the whole, I think there are no good agreed-upon definitions here: better for the application to impose its own interpretation, and the undef (or empty list) is a good sign of weird things going on.

Mon Sep 21 22:26:49 2015 The RT System itself - Status changed from 'new' to 'open'

Mon Sep 21 22:26:50 2015 JHI [...] cpan.org - Status changed from 'open' to 'resolved'

Wed Sep 23 07:08:48 2015 user42_kevin [...] yahoo.com.au - Correspondence added

Subject:	Re: [rt.cpan.org #104687] diameter and centre of a one vertex graph
Date:	Wed, 23 Sep 2015 21:01:30 +1000
To:	"Jarkko_Hietaniemi via RT" <bug-Graph [...] rt.cpan.org>
From:	Kevin Ryde <user42_kevin [...] yahoo.com.au>

"Jarkko_Hietaniemi via RT" <bug-Graph@rt.cpan.org> writes: Show quoted text

> > longest path over all the paths between vertex pairs.

$graph->path_length($v,$v) is 0, so I would say diameter as maximum over all path_length() would then be zero. The attraction is that for example a path graph of n vertices has diameter n-1. (A graph of no vertices at all or a disconnected graph I have no opinion, I think.)

Wed Sep 23 08:07:44 2015 JHI [...] cpan.org - Correspondence added

On Wed Sep 23 07:08:48 2015, user42_kevin@yahoo.com.au wrote: Show quoted text

> "Jarkko_Hietaniemi via RT" <bug-Graph@rt.cpan.org> writes:

> > > > longest path over all the paths between vertex pairs.

> > $graph->path_length($v,$v) is 0, so I would say diameter as maximum over > all path_length() would then be zero. The attraction is that for > example a path graph of n vertices has diameter n-1. > > (A graph of no vertices at all or a disconnected graph I have no > opinion, I think.)

I am still not convinced... if we take for example http://mathworld.wolfram.com/GraphDiameter.html: "In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration." There are no paths. And a path from v to v would be a loop. I guess what it boils down to is that I don't like making a single-vertex graph a special case (of diameter being zero, or the center vertices being that vertex). (As opposed to multi-vertex no-edges graph.) Just wrap them for your app, where you have well-defined semantics: sub diameter0 { $_[0]->vertices == 1 ? 0 : $_[0]->diameter; } (or derive from Graph, if feeling more ambitious)

Fri Sep 25 04:03:28 2015 user42_kevin [...] yahoo.com.au - Correspondence added

Subject:	Re: [rt.cpan.org #104687] diameter and centre of a one vertex graph
Date:	Fri, 25 Sep 2015 17:54:11 +1000
To:	"Jarkko_Hietaniemi via RT" <bug-Graph [...] rt.cpan.org>
From:	Kevin Ryde <user42_kevin [...] yahoo.com.au>

"Jarkko_Hietaniemi via RT" <bug-Graph@rt.cpan.org> writes: Show quoted text

> > I am still not convinced... if we take for example http://mathworld.wolfram.com/GraphDiameter.html: > > "In other words, a graph's diameter is the largest number of vertices > which must be traversed in order to travel from one vertex to another > when paths which backtrack, detour, or loop are excluded from > consideration." > > There are no paths. And a path from v to v would be a loop.

I would interpret v to v as meaning you're at the destination with 0 edges traversed. But I suppose some graph stuff is over paths without v to v, like Graph.pm average_path_length() - a usual definition for that one as far as I know. It could be enough if the docs of diameter() and friends made it clearer what happens on empty, 1-vertex, disconnected. ... Might be as little as one sentence if it's undef on all of those. Show quoted text

> $_[0]->vertices == 1 ? 0 : $_[0]->diameter;

Oh, well, in application code $graph->diameter // 0 could be the suggestion for new enough perl. -- I played a country and western song backwards to listen for evil messages. It sounded the same but about a fella whose wife stood by him while he brought in a successful harvest and his dog recovered from illness.