6 May 2003 01:06:47 -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: | 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.