Re: "metric in Graph"

Antti-Juhani Kaijanaho <>
6 May 2003 19:31:06 -0400

          From comp.compilers

Related articles
"metric in Graph" (Albretch) (2003-04-27)
Re: "metric in Graph" (2003-05-06)
Re: "metric in Graph" (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:

(BTW. I have a hard time figuring out how this relates to compilers.)
Antti-Juhani Kaijanaho, FM (MSc),
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

Return to the comp.compilers page.
Search the comp.compilers archives again.