# Re: "metric in Graph"

## Antti-Juhani Kaijanaho <antkaij@mit.jyu.fi>6 May 2003 19:31:06 -0400

From comp.compilers

Related articles
"metric in Graph" lbrtchx@hotmail.com (Albretch) (2003-04-27)
Re: "metric in Graph" Robert@Knighten.org (2003-05-06)
Re: "metric in Graph" antkaij@mit.jyu.fi (Antti-Juhani Kaijanaho) (2003-05-06)
| List of all articles for this month |

 From: Antti-Juhani Kaijanaho Newsgroups: comp.compilers Date: 6 May 2003 19:31:06 -0400 Organization: University of Jyvaskyla, Finland References: 03-04-105 Keywords: tools Posted-Date: 06 May 2003 19:31:06 EDT

Albretch wrote:
> Is there a way to define a metric in a DAG (direct acyclic graph)?

The trivial metric is always available:
d(x,y) = 0 for all x and y

It is possible to construct other metrics, but you'd need to consider
what you need the metric for to decide whether you want them or not.
One possibility is this:

Let G = (V, E) be a finite, reflexive, weakly connected graph, where V
is the set of vertices and E \subset V^2 is the set of edges. Let
sp(x,y) be the length of the shortest path from x \in V to y \in V.
Now, d_G : V^2 -> [0,oo[, d_G : (x,y) -> min { sp(x,y), sp(y,x) } is a
metric in G.

(If your graph is not reflexive, there exists an x \in V such that
d_G(x,x) > 0. If your graph is not finite or weakly connected, there
are vertices x \in V for which d_G(x,x) is undefined. I'd like to call
this the Dijkstra metric as a homage to Dijkstra's algorithm, but it
seems it already has a name:
http://mathworld.wolfram.com/GraphDistance.html)

(BTW. I have a hard time figuring out how this relates to compilers.)
--
Antti-Juhani Kaijanaho, FM (MSc), http://www.mit.jyu.fi/antkaij/
ohjelmistotekniikan assistentti * assistant in software engineering
Jyväskylän yliopisto * University of Jyväskylä
Tietotekniikan laitos * Dept. of Mathematical Inf. Tech.
[A DAG is the standard data structure for representing sets of
expressions in a compiler. -John]

Post a followup to this message