Re: [Tcllib-devel] Review rev 41 - Re: Graphops - Documentation

[Andreas K. <and...@ac...>]

Michał Antoniewski wrote:
> Hello.
>  
> First part of documentation availiable on SVN. Please review it and let 
> me know, what you think about it.
>  
> Is that Input/Output division allright visually? And generally does it 
> look ok?

The general idea of structuring the documentation of a command in this manner 
is good. The execution needs however some changes as it doesn't make use of the 
doctools markup commands we have available for this.

See my review (rev 41) below where I give examples.

Further, some links

http://docs.activestate.com/activetcl/8.5/tcllib/doctools/doctools_lang_intro.html
doctools introduction

http://docs.activestate.com/activetcl/8.5/tcllib/doctools/doctools_lang_cmdref.html
Markup command reference

http://docs.activestate.com/activetcl/8.5/tcllib/doctools/doctools_lang_syntax.html
Syntax reference


 >   53:	
 >   54:	[call [cmd struct::graph:op::toAdjacencyList] [arg G] [opt [arg 
options]...]]
 >   55:	
 >   56:	Procedure creates for input graph [arg G], it's representation as 
[term "Adjacency List"].
 >   57:	
 >   58:	[para]
 >   59:	
 >   60:	[const Input:]
 >   61:	[arg G] - input graph.
 >   62:	[arg options] - possible options are: directed (for directed graphs - 
undirected is default).
 >   63:	and weights ( including weights at edges in Adjacency List).

Ok, here is the above using the structuring facilities we havein doctools markup.

As the [const] command is for the markup of contant strings in the API its use 
to highlight and structure the documentation is ... ill-advised.

I am now using a definition-list to generate the overall structure (Arguments, 
Options), and then the list types for arguments and options to structure them 
further.

The comments at the end of the lists are just my personal way of keeping track 
of deeply nested list structures.


	[list_begin definitions]

	[item Arguments]
	[list_begin arguments]
	[arg_def {graph object} G input]

	The graph to convert into an [term "Adjacency List"].

	[list_end][comment {-- arguments --}]

	[item Options]
	[list_begin options]
	[opt_def -directed]

	By default [arg G] is operated as if it were an [term {Undirected graph}].
	Using this option tells the command to handle [arg G] as the directed graph it is.

	[opt_def -weights]

	By default any weight information the graph [arg G] may have is ignored.
	Using this option tells the command to put weight information into the result.
	In that case it is expected that all arcs have a proper weight, and an error
	is thrown if that is not the case.

	[list_end][comment {-- options --}]
	[list_end][comment {-- definitions --}]

Note how I use '-directed' and '-weights', i.e. the actual exact names of the 
options in question, including the '-' prefix. Using inaccurate names is bad 
when it comes to documentation. Its purpose is to inform actual and potential 
users, not to misdirect them.

Note also my addition of error conditions (... proper weight ...), i.e. what 
checks are performed on the input by the command.





 >  301:	
 >  302:	[call [cmd struct::graph::op::BellmanFord] [arg G] [arg startnode]]
 >  303:	
 >  304:	Searching for shortests paths between chosen node and all other nodes 
in graph [arg G]. Based
 >  305:	on relaxation method. In comparison to [cmd 
struct::graph::op::dijkstra] it doesn't need assumption that all weights
 >  306:	on edges in input graph [arg G] have to be positive.
 >  307:	
 >  308:	[para]
 >  309:	
 >  310:	That generality sets the complexity of algorithm to - [term O(V*E)], 
where [term V] is the amount of vertices
 >  311:	and [term E] is amount of edges in graph [arg G].

amount -> number

 >  312:	
 >  313:	[para]
 >  314:	
 >  315:	[const Input:]
 >  316:	
 >  317:	[para]
 >  318:	[const G] - Directed, connected and edge weighted graph [arg G], 
without any negative cycles ( presence of cycles with the negative sum
 >  319:	of weight means that there is no shortest path, since the total weight 
becomes lower each time the cycle is
 >  320:	traversed ). Negative weights on edges are allowed.
 >  321:	
 >  322:	[para]
 >  323:	
 >  324:	[const Output:]
 >  325:	
 >  326:	[para]
 >  327:	Dictionary containing for each node (key) distances to each other node 
in graph [arg G].

Using the basic template I demoed for line 63 and before ... In the Tcl style 
guide for C code output of a function is described as 'Result', and I believe 
that is a good name to use here as well.

	[list_begin definitions]

	[item Arguments]
	[list_begin arguments]
	...
	[list_end][comment {-- arguments --}]

**	[item Result]
**
**	A dictionary containing the distances from the [arg startnode] to all other 
nodes in the graph [arg G]. The node names are used as dictionary keys.
**
	[list_end][comment {-- definitions --}]


 >  329:	[para]
 >  330:	[emph Note:] If algorithm finds a negative cycle, it will return error 
message.

Good.

I won't copy the template to all the other commands now, I believe showing it 
twice (with different parts) is good enough for that.



 >  334:	[call [cmd struct::graph::op::Johnsons] [arg G] [opt [arg options]...]]
 >  335:	
 >  336:	Searching paths between all pairs of vertices in graph. For sparse graphs
 >  337:	asymptotically quicker than [cmd struct::graph::op::FloydWarshall] 
algorithm. Johnson's algorithm
 >  338:	uses [cmd struct::graph::op::BellmanFord] and [cmd 
struct::graph::op::dijkstra] as subprocedures.
 >  339:	[nl]

[nl] is depcrecated, we should always use [para].


 >  417:	
 >  418:	[emph Note:] It's 2-approximation algorithm.


We should maybe make a note in general what it means to be an N-approximation 
algorithm.


 >  453:	[call [cmd struct::graph::op::MaxCut] [arg G] [arg U] [arg V]]
 >  454:	
 >  455:	[term "Maximum cut problem"] is a problem finding a cut not smaller 
than any other cut. In
 >  456:	other words, we divide set of nodes for graph [arg G] into such 2 sets 
of nodes [term U] and [term V],
 >  457:	that the amount of edges connecting [term U] and [term V] is as high 
as possible.
 >  458:	
 >  459:	Algorithm is a 2-approximation, so for [term ALG] (solution returned 
by algorithm) and
 >  460:	[term OPT] (optimal solution), such inequality is true: [emph "OPT <= 
2 * ALG"].

Ah, and here we have such a remark ... We should possibly move this into a 
separate graph theory / term section at the end and make a reference to it here ...

	Algorithm is a [sectref {Background theory and terms} 2-approximation].
	                        ~ name of the section we ref  ~~ label used in the 
sentence.

 >  461:	
 >  462:	[para]
 >  463:	[const Input:]

 >  464:	[list_begin enum]
 >  465:	[enum] Graph [arg G].
 >  466:	[enum] [arg U] - variable storing first set of nodes (cut) given by 
solution.
 >  467:	[enum] [arg V] - variable storing second set of nodes (cut) given by 
solution.

See my template, 'argument' list.

 >  475:	[call [cmd struct::graph::op::UnweightedKCenter] [arg G] [arg k]]



 >  477:	[emph Definition:]
 >  478:	For any set [term S] ( which is subset of [term V] ) and node [term 
v], let the [term connect(v,S)] be the
 >  479:	cost of cheapest edge connecting [term v] with any node in [term S]. 
The goal is to find
 >  480:	such [term S], that [term "|S| = k"] and [term "max_v{connect(v,S)}"] 
is possibly small.

Structure with definition-list.




 >  544:	[call [cmd struct::graph::op::VerticesCover] [arg G]]
 >  545:	
 >  546:	[term "Vertices cover"] is a set o vertices such that each edge of the 
graph is incident to

typo ... of vertices ...




 >  556:	[call [cmd struct::graph::op::EdmondsKarp] [arg G] [arg s] [arg t]]
 >  557:	
 >  558:	The general idea of algorithm is finding the shortest augumenting 
paths in graph [arg G], as long
 >  559:	as they exist, and for each path updating the edge's weights along 
that path,
 >  560:	with maximum possible throughput. The final (maximum) flow is found
 >  561:	when there is no other augumenting path from source to sink.

This information about the implementation should be moved to the end of the 
block describing the command, as it is likely of less interest to users. At 
this point the important thing they wish to know is that it computes a max-flow.


 >  614:	
 >  615:	[call [cmd struct::graph::op::ShorestsPathsByBFS] [arg G] [arg s] [arg 
outputFormat]]

Typo ... Shorests -> Shortests?

 >  654:	[option outputFormat] - possible options are [option graph] and 
[option tree].

option -> arg. The [option graph] should is [const graph].


 >  883:	
 >  884:	[keywords graph dijkstra distance radius diameter eccentricity]
 >  885:	[keywords edge arc node vertex subgraph neighbour]
 >  886:	[keywords adjacent loop degree]
 >  887:	[keywords {cut vertex} {articulation point} {connected component}]
 >  888:	[keywords {strongly connected component} {adjacency matrix}]
 >  889:	[keywords {minimal spanning tree} bipartite bridge {cut edge} isthmus]

The above list of keywords and terms should be extended as well.


Andreas.