|"metric in Graph" email@example.com (Albretch) (2003-04-27)|
|Re: "metric in Graph" Robert@Knighten.org (2003-05-06)|
|Re: "metric in Graph" firstname.lastname@example.org (Antti-Juhani Kaijanaho) (2003-05-06)|
|From:||Robert@Knighten.org (Robert L. Knighten)|
|Date:||6 May 2003 01:06:47 -0400|
|Organization:||Posted via Supernews, http://www.supernews.com|
|Posted-Date:||06 May 2003 01:06:47 EDT|
Albretch <email@example.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
Note that the topology generated by this metric is necessarily discrete.
Robert L. Knighten
Return to the
Search the comp.compilers archives again.