I have done Felix version of Skiena's representation of a graph, and a breadth first search.
As usual i'm less interested in the representation as such than the typing, abstraction, etc. However, Skiena's representation makes me feel uneasy. typedef digraph_t = (vertices: darray[vertex_t], nedges: int); // x index implicit, the edge source // y index is the edge destination typedef edge_t = (elabel:E, y:int, weight:int); typedef vertex_t = (vlabel:V, outedges: list[edge_t]); 1. Skiena uses a flag to tell the difference between an undirected and directed graph. I have only a digraph here. It's not clear to me the two things shouldn't be completely distinct, even though an undirected graph can be represented by a digraph with edge pairs (x,y) and (y,x). 2. The rep is compact, but the edge type doesn't tell the source of the edge, it's implicit from the position in the array. I don't like that, the *actual* edge required a pair int * edge_t. 3. Using integers to represent vertices leaves open the problem of how to properly build the graph. I solved that by adding default vertices to fill up the list up to the currently specified maximum integer. My graph has both edge and vertex labels, but these can't be assumed unique. But identifying by integer is a plain wrong. It may be OK for a static graph, but even after construction of a graph, one might like to perform mutations. IMHO pointers are just plain better. They provide unique if arbitrary identification. And they allow mutation in a fairly natural way. Deleting an edge in Skiena's rep is ok, but deleting a vertex isn't really possible (at best you can isolated it). 4. One of the core things about graphs is that a set of vertices and edges can often generate other graphs: search order trees, parents for them, spanning trees, etc etc. Generally doing this should not require a modification to the original graph, but often we would like to share the vertices. 5. Note that one of the most important "theoretical" uses of a graph is that every graph generates a category, namely the set of all paths in the graph (with identity paths for each vertex added). -- john skaller skal...@users.sourceforge.net http://felix-lang.org ------------------------------------------------------------------------------ Dive into the World of Parallel Programming The Go Parallel Website, sponsored by Intel and developed in partnership with Slashdot Media, is your hub for all things parallel software development, from weekly thought leadership blogs to news, videos, case studies, tutorials and more. Take a look and join the conversation now. http://goparallel.sourceforge.net/ _______________________________________________ Felix-language mailing list Felix-language@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/felix-language
