Hi Jeff > But you're right, that's a better word for discussing the problem. > Steven's problem data structures are cyclic graphs. I don't agree that such > structures are a sign one is doing something wrong (outside the naive > approach to printing them out). >
Thank you for agreeing with me, and nicely disagreeing with me. However, the problem of 'walking a graph' to find a spanning tree is first of all a matter of choosing an algorithm. The algorithm to be used and the representation of the graph are two different matters. Suppose the vertices are well ordered, for example (0, 1, 2, 3, .., n). Write each edge as an ORDERED pair, with the first vertex being less than the second vertex. Now list the edges in lexicographic order. That solves the problem, and gives a unique representation, provided we are given a well ordering of the vertices. Under certain circumstances, we can use the Python id to provide the well ordering of vertices. However, that doesn't always work. Two strings (or large ints, or tuples) can be equal even though they have different ids. However, I think it reasonable to assume that we have a sensible equality relation on the vertices. Now things get interesting. For a very large graph, it would be very helpful if every vertex has a hash. This would make determining equality easier. But if the data structure representing the graph has Python cycles in it (as in Steven's use case) then there won't be a hash available. Do you agree with me, Jeff, that the problem of printing out a vertices-and-edges graph is much easier (or at least quicker) if each vertex has a hash. More exactly, we want a quick and easy way to determine if two vertices are equal. It would be nice to have some further input from Steven, whose original post stated the problem he wished to solve. -- Jonathan
_______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/3AHIT7CQ6PW4SRIXNFP3UWPFKYO3KDGN/ Code of Conduct: http://python.org/psf/codeofconduct/
