Menu
▾
▴
tcllib-devel
|
From: Andreas K. <aku...@sh...> - 2009-08-03 00:44:09
|
> Hello. > All local searching is done - just got one problem how to arrange > one step of algorithm. If it takes too much time, I will describe it > to you, maybe you will come up with some better solution. I'll have a look. > I have started with documentation work. So, some questions about it: > - as it was described in developer file, I'm going to edit 'man' > file, from which is created html file during installation. Is > there anything else to do? No, not really. > - should there be any documentation file summarizing whole project? What do you envision as its content ? > - the documentation for graphops contains short descriptions on what > procedure does and how to use it. How about info concerning > complexities and generally some graph theory info about particular > algorithm? Or we assume that user knows, what he is looking for > when he wants to use e.g. Christofides Algorithm? The basic descriptions are a must. Having complexities would be good as well. For theory we should have at least references to wikipedia or other websites. If we have enough time left we can certainly add more. -- So long, Andreas Kupries <aku...@sh...> <http://www.purl.org/NET/akupries/> Developer @ <http://www.activestate.com/> ------------------------------------------------------------------------------- |
|
From: Michał A. <ant...@gm...> - 2009-08-03 21:27:55
|
I've got one more question about documentation. As during implementation, there were created some subprocedures (for main algorithms) that can be found useful as individual graph operations, I would like to verify which of them should be put in documentation : a) Algorithms: - Greedy Max Matching - subprocedure for Christofides but still individual algorithm, so I think can be included. - Greedy Max Independent Set (Weighted also) - the same as above. - BFS and BFS pathfinding - I think both BFS procedures will be useful addition. b) some other graph operations: - create squared graph - possibly useful graph operation. - create Complete Graph - for input graph G, adds missing edges and returns complete graph. - copy Graph - subprocedure for copying graphs as there are a lot of such uses in implementation. Possibly useful operation for users too. Generally subprocedures under "b)" are less likely to add in graphops than "a)" and "c)", but I'm asking to make sure. c) Subprocedures considering flow problems. Also useful as individual procedures: - create Residual Graph - create Augmenting Network - create Level Graph Best Regards, Michał Antoniewski |
|
From: Andreas K. <and...@ac...> - 2009-08-04 15:53:16
|
Michał Antoniewski wrote: > I've got one more question about documentation. > > As during implementation, there were created some subprocedures (for > main algorithms) that can be found useful as individual graph > operations, I would like to verify which of them should be put in > documentation : > > a) Algorithms: > - Greedy Max Matching - subprocedure for Christofides but > still individual algorithm, so I think can be included. > - Greedy Max Independent Set (Weighted also) - the same as above. > - BFS and BFS pathfinding - I think both BFS procedures will be useful > addition. Yes to all. > > b) some other graph operations: > - create squared graph - possibly useful graph operation. > - create Complete Graph - for input graph G, adds missing edges and > returns complete graph. > - copy Graph - subprocedure for copying graphs as there are a lot of > such uses in implementation. Possibly useful operation for users too. > Generally subprocedures under "b)" are less likely to add in graphops > than "a)" and "c)", but I'm asking to make sure. Yes to all. Copying graph definitely occurs often, and all not quite able to use the (de)serialize methods because of changes to attributes, and/or arc names, and the like. > c) Subprocedures considering flow problems. Also useful as individual > procedures: > - create Residual Graph > - create Augmenting Network > - create Level Graph Yes. Andreas. |
|
From: Michał A. <ant...@gm...> - 2009-08-05 14:14:41
|
Hello. Next version of documentation is availiable. I couldn't find a wiki link to K-Center problem (there was only http://en.wikipedia.org/wiki/1-center_problem), so I used another reference http://www.csc.kth.se/~viggo/wwwcompendium/node128.html, is that ok or rather only wiki references? The same is with min diameter spanning tree problem. Best Regards, Michał Antoniewski |
|
From: Andreas K. <and...@ac...> - 2009-08-05 17:42:30
|
Michał Antoniewski wrote: > Hello. > > Next version of documentation is availiable. Looks ok, modulo the structuring I talked about in the review for rev 42. (This is the review for rev 43). > I couldn't find a wiki link to K-Center problem (there was only > http://en.wikipedia.org/wiki/1-center_problem), so I used another > reference http://www.csc.kth.se/~viggo/wwwcompendium/node128.html, is > that ok or rather only wiki references? That is ok. > The same is with min diameter spanning tree problem. Andreas. |
|
From: Michał A. <ant...@gm...> - 2009-08-08 15:35:14
|
I reworked structuring like you said, please see if it now looks okey. In some places I left old style as I thought it looks better for those cases (mainly case of not a lot of text and single arguments). If you like I can change structure for them as well. For some procedures with e.g. single graph argument maybe it would look better when it's written in a single line? I've added some keywords and a graph theory section. Now, it has only k-approximation algorithm definition but I will scan whole problem set, so maybe some more interesting things could be added (also there is a reference to wiki concering approximation algorithms). Maybe each problem could have it's definition in that section, but on the other hand there are references which do the same. >>Any particular reason not modifying >> modules/struct/graphops.man >>directly ? Oh, I did so, but I created new documentation folder to separate documentation work from the rest for better access (division) at SVN. I was also doing some rechecking with test cases, so next upcoming update will include tests. Best Regards, Michał Antoniewski |
|
From: Andreas K. <and...@ac...> - 2009-08-10 16:56:15
|
Michal Antoniewski wrote:
> I reworked structuring like you said, please see if it now looks okay.
Doing now ...
> In some places I left old style as I thought it looks better for those
> cases (mainly case of not a lot of text and single arguments). If you
> like I can change structure for them as well.
... Checking ... Greedy(Weighted)MaxIndependentSet, VerticesCover.
The shorter description does work for them. I would have preferred consistency.
On the other hand I cannot complain too much here, given that I am often not
fully consistent either in my work.
> For some procedures with e.g. single graph argument maybe it would look
> better when it's written in a single line?
Actually for the non-structured description using 2 lines seems to be better
than one.
> I've added some keywords and a graph theory section. Now, it has only
> k-approximation algorithm definition but I will scan whole problem set,
> so maybe some more interesting things could be added (also there is a
> reference to wiki concerning approximation algorithms). Maybe each
> problem could have it's definition in that section, but on the other
> hand there are references which do the same.
I was thinking similarly when looking at the description, i.e. moving the
definitions to the graph theory section. As for definitions which are the same,
that would be no problem. You can have multiple references to the same thing.
Note here that we can not only have [section]s, but [subsection]s as well,
which can be [sectref]'d. I.e. each specific definition could be put into a
referencable sub-section, and then referenced directly.
>
> >>Any particular reason not modifying
> >> modules/struct/graphops.man
> >>directly ?
>
> Oh, I did so, but I created new documentation folder to separate
> documentation work from the rest for better access (division) at SVN.
Hm. I am more comfortable with work within the existing structure. It also
makes comparison easier, as I run a simple diff not only between last and
current, but also the original baseline and current. The latter gives me a list
of the files which have been added or changed within the tcllib structure. That
tells us what we have to save from the project for integration. Well, assuming
we wish to save only the changed parts. If we don't wish optimize (= save
space) just saving the whole 'struct' directory would work as well. That also
assumes that the work was done inside the existing directory and file structure.
> I was also doing some rechecking with test cases, so next upcoming
> update will include tests.
Rev 44 ...
> 419: [emph Note:] Algorithm finds solutions dynamically. It compares all
possible paths through the graph
When you say 'dynamically', do you mean 'Dynamic Programming' ?
> 531: [arg_def {Graph Object} G input]
> 533: Graph [arg G].
'The graph to cut.'
> 535: [arg_def {List} U input]
> 536:
> 537: Variable storing first set of nodes (cut) given by solution.
> 538:
> 539: [arg_def {List} V input]
> 540:
> 541: Variable storing second set of nodes (cut) given by solution.
U/V are also output, in a sense.
> 704: [arg_def {Integer} desiredGlow input]
Typo: Glow --> Flow
> 727: for sparse graphs, but also there exist some patological cases (those
cases generally don't appear in practise) that
Typo: patological -> pathological
> 728: make time complexity increase exponentially with the growth of the
number of nodes.
> 729:
> 730: [para]
> 731: [list_begin definitions]
> 732:
> 733: [def Arguments:]
> 734: [list_begin arguments]
> 735: [arg_def {Graph Object} G input]
> 736: Input graph.
> 737: [arg_def {Node} s input]
> 738: Source node for which all distances to each other node in graph [arg
G] are computed.
> 739: [list_end][comment {-- arguments --}]
> 740:
> 741: [def "Options and result:"]
> 742: [list_begin options]
> 743: [opt_def -distances]
distances, not -distances, per the code (graphops.tcl, line 1706-1716).
Either fix documentation, or the code.
> 744:
> 745: When selected [arg outputFormat] is [const distances] - procedure
returns dictionary containing
> 746: distances between source node [arg s] and each other node in graph
[arg G].
> 747:
> 748: [opt_def -paths]
Ditto. paths, not -paths
> 781: [opt_def -graph]
> 786: [opt_def -tree]
Ditto. Compare graphops.tcl, lines 1811-1820.
> 787:
> 788: When selected [option outputFormar] is [option tree] - procedure
returns a tree structure ([cmd struct::tree]),
outputFormat
> 959: [call [cmd struct::graph::op::createResidualGraph] [arg G] [arg f]]
> 971: [arg_def {Graph Object} G input]
> 972: Flow network (directed graph where each edge has set attribute: [term
throughput] ).
Argument f is not documented.
> 1010: [call [cmd struct::graph::op::createLevelGraph] [arg Gf] [arg s]]
> 1021: [arg_def {Graph Object} G input]
G -> Gf
Andreas.
|
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X