[m-dev.] For review: changes to graph.m

[Fergus Henderson]

Thomas Charles CONWAY, you wrote:
> 
> Warwick has given me the following changes to the support for graphs
> in the library: graph.m becomes digraph.m, and graph.m is for undirected
> graphs.

Thanks.

Uh, how backwards-compatible are these changes?

If they are not backwards compatible, then it might be a good
idea to send some mail to mercury-users asking if anyone has lots
of code using graph.m before we make this change.

OK, now some detailed comments...

The new graph.m needs to be some reformatting to fit in 80 columns.

> /*
> 	% graph__path(Graph, Start, End, Path) is true iff there is a path
> 	% from the node Start to the node End in Graph that goes through
> 	% the sequence of edges Edges.
> 	% The algorithm will return paths containing at most one cycle.

The description of the algorithm is actually adding an extra constraint
to the semantics.  This comment should be:

 	% graph__path(Graph, Start, End, Path) is true iff there is a path
	% from the node Start to the node End in Graph that goes through
 	% the sequence of edges Path and that contains at most one cycle.
				^^^^

But, this is still not correct, I think.  I think it should  be

 	% graph__path(Graph, Start, End, Path) is true iff there is a path
	% from the node Start to the node End in Graph that goes through
 	% the sequence of edges Path and that contains no cycles
	% unless Start = End, in which case it must contain exactly one
	% cycle.

Oh, hang on, looking at the implementation I think it should be

 	% graph__path(Graph, Start, End, Path) is true iff there is a path
	% from the node Start to the node End in Graph that goes through
 	% the sequence of edges Path (finishing in End, but not starting
	% with Start) and that contains no cycles.

Hmm.  Perhaps someone can improve on this.

> :- pred graph__path(graph(N, E), node(N), node(N), list(edge(E))).
> :- mode graph__path(in, in, in, out) is nondet.
> :- mode graph__path(in, in, out, out) is nondet.
> */

How come graph__path is commented out?

> 	% graph__dummy_node(Graph, Node) is true iff Node is the dummy node
> 	% for graph Graph.
> :- pred graph__dummy_node(graph(N, A), node(N)).
> :- mode graph__dummy_node(in, out) is det.
> :- mode graph__dummy_node(in, in) is semidet.
> 
> 	% graph__dummy_edge(Graph, Edge) is true iff Edge is the dummy edge
> 	% for graph Graph.
> :- pred graph__dummy_edge(graph(N, A), edge(A)).
> :- mode graph__dummy_edge(in, out) is det.

What's a dummy node or a dummy edge?

> :- implementation.
...
> :- type graph(N, E)	== digraph(N, E).

A comment here would be helpful.

> graph__path_2(G, S, E, Nodes0, Path) :-

Please use more meaningful variable names than `G', `S', and `E'.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.