Re: Graph reduction algorithm

Peter Collingbourne wrote:
Dear group,

I have a directed cyclic graph G1, such that each arc holds information
over which there exists an equivalence relation C. The nodes hold no
information. I would like to find the minimal subgraph G2 such that
f is the mapping function from nodes in G1 to nodes in G2, and any path

n[1] --a[1]--> n[2] --a[2]--> n[3] ... --a[n-1]--> n[n]

in G1 has a corresponding path

f(n[1]) --b[1]--> f(n[2]) --b[2]--> f(n[3]) ... --b[n-1]--> f(n[n])

in G2 such that C(a[1],b[1]), C(a[2],b[2]) ... C(a[n-1],b[n-1]) hold.
Furthermore, for each node n in G1, for each arc b from node f(n) in G2,
if property P(b) holds then there must be a corresponding arc a from n
such that C(a,b) holds.

I would be grateful for any ideas or pointers for solving this problem.

Thanks,

I think it would be helpful to the rest of us if you could provide a small example illustrating what you're trying to do. I for one have a hard time making sense of statements like, "each arc holds information over which there exists an equivalence relation." Likewise your paths, labels as a[], b[], n[], f(n[]), with n also apparently serving as an index name, are quite hard to comprehend.
.