Re: "metric in Graph"

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]

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