6 May 2003 19:31:06 -0400

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) |

From: | Antti-Juhani Kaijanaho <antkaij@mit.jyu.fi> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.