othar@ernie.Berkeley.EDU (Othar Hansson) (10/12/89)
Aside from Matrix routines, I'd be eager to see a nice elegant class for implementing Graphs. A Graph of Xs, connected by Ys, appears in almost as many programs as a Queue of Xs or a Set of Ys. For example, a Graph of Cities (Nodes) and Highways (Edges), might support operations of the following sort: Graph G; . . . Node node1 = G.nodes[1]; int i = node1.indegree(); Edge edge1 = node1.outedges[i-1]; // take last outgoing edge... (edge1.to).inedges -= edge1; // unlink it... node2.inedges += edge1; // and link to node2 float c = (edge1.contents)->cost; long pop = (node1.contents)->population; Highway *hwy49 = edge1.contents; NodeQueue visitme = node1.traveling_salesman_tour(); Ok, so the last one isn't that essential. And we rarely see one-way highways, but... The idea is that the connectivity is reflected in the Graph class, while the semantics of the edges and nodes is captured in two separate classes, and accessed through a single ptr stored in the Nodes/Edges. The Graph class would have to be supplemented by Node and Edge classes, where most of the work would take place. It's easy to write an ugly class definition (as I've just done this weekend), but an elegant one would greatly simplify an ENORMOUS number of programs. Anyone have one? Anyone interested in writing one? Anyone want to give this to their class as a homework? Wishfully, Othar Hansson othar@ernie.berkeley.edu