Re: "metric in Graph"

Robert@Knighten.org (Robert L. Knighten)
6 May 2003 01:06:47 -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: Robert@Knighten.org (Robert L. Knighten)
Newsgroups: comp.compilers
Date: 6 May 2003 01:06:47 -0400
Organization: Posted via Supernews, http://www.supernews.com
References: 03-04-105
Keywords: analysis
Posted-Date: 06 May 2003 01:06:47 EDT

Albretch <lbrtchx@hotmail.com> writes:


> Is there a way to define a metric in a DAG (direct acyclic graph)?
> Actually, the elements might be acyclic or cyclic to a certain extent,
> which I think, complicate things.
>
> Or anything metric-looking to kind of describe a distance among
> certain elements relating to each other?


Sure. In any connected graph, define the distance between two nodes to be the
minimum of the length (= number of links) of all paths between the nodes. If
the graph is not connected, this is easily generalized by allowing an infinite
distance and making the distance between nodes that cannot be connected
infinite.


Note that the topology generated by this metric is necessarily discrete.


-- Bob


--
Robert L. Knighten
Robert@Knighten.org

Post a followup to this message

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