wss@cs.nott.ac.uk (William Shu) (11/10/86)
I am not sure which group this has to be. Appologies if in the wrong group. Suppose directed [possibly cyclic] graph, G (could be a path expression, regular expression, or ... whatever) with a unique entry node, S. We want to restore the original graph should the links between nodes be scrambled, some nodes removed or extra nodes linked in. What scheme (metric) is most suitable to weight (or label) the nodes so that their original position a) relative to each other and b) their distance relative to S could be deduced (calculated) solely from the label. For example, Let G be a simple list and let D0(N) be the distance of node N from S, taken as (to a 1st approximation), the number of arcs in the path from S to N. then the label is, say, D0(N) = n-1 where n is the n-th node of the list. Solutions to subsets of the problem or transformations to an equivalent problem are welcome. A practical implementation detail is time and/or space efficiency to acquire/use the labels. A summary of replies will be compiled and made available over the net. ________________________________________ Please Mail to: real life | e-mail --------------------------------------------------------------------------- William Shu | | Department of Computer Science, | JANET : wss@uk.ac.nott.cs | University of Nottingham, | | University Park, | ARPA : wss@nott.cs@cs.ucl.ac.uk | Nottingham NG9 2RD. | | England, UK. | UUCP : ukc!nott.cs!wss | Tel (0602) 506101 Ext 3702 (day)| | ---------------------------------------------------------------------------