Re: [Tcllib-devel] Flow problems - attributes question

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

Michał Antoniewski wrote:
> Oh, I think I missed somehow note to use attributes for arcs/nodes.

Let me check my mail archives ... Ok, found it, review rev 32, mail of July 7 
... I am inlining

Michał Antoniewski wrote:
 > >
 > >
 > >
 > >     Should document structure of nodeWeights as list of (list (node,
 > >     weight)). This I inferred from the commands using the data, otherwise
 > >     it could have been a dictionary.
 > >
 > >
 > > Oh, sorry, I forgot to describe it...Yes, it's a list like you said. I
 > > thought also adding maintenance of weights at nodes for struct::graph
 > > could be a good new functionality, so that nodeWeights could be found by
 > > "$G node weights" for example. In that case, it could be useful to
 > > change that list (nodeWeights) to work as a dictionary ( regarding "$G
 > > arc weights returns dict ).
 > > Weights at nodes could be widely used in graph coloring algorithms.

We already have general node attributes, i.e. each node in a graph can have an
arbitrary set of named values. The relevant methods are

	node set    $u $name $value	- Set named attribute to a value
	node append $u $name		- Append data to attribute
	node append $u $name		- Ditto, but list-like
	node get    $u $name		- Retrieve attribute value for node
	node getall $u			- Retrieve all attributes for node
	node unset  $u $name		- Delete attribute
	node keyexists $u $name		- Check if attribute is known to node.

And also, especially interesting for us:

	node attr $name			- Return attribute value for all nodes
					  as dictionary (node -> value).

http://docs.activestate.com/activetcl/8.5/tcllib/struct/graph.html

May I propose to use this facility ? In the first iteration we can use a fixed
attribute name, like 'weight', and later on the attribute name could be made
configurable.

I know that this is different from what we did last year for the arc weights.
This is actually intentional. Seeing them both I am hoping to get a feel for
the differences and similarities in the both approaches and which would be
better in general.


> I was writing test cases and now it appeared even more useful...e.g., 
> when testing, if input is proper...So, I will change that and then 
> update, so there will disappear that dictionary from input which 
> contains throughputs (in Busacker Gowen).

I see. Ok.


> But I've got a question...I need to use dijkstra ( or later other path 
> finding procedure ), but it finds the path using weights on edges ...

Yes.

> And I need it to search for costs....It forces me to place costs on edge 
> weights in graph G and throughputs as edge attributes...

Right.

> Or maybe I missed something and it's possible somehow to run dijkstra 
> with set of attributes as weights?

Unfortunately not. This is why I am driving a bit towards the arc/node 
attribute, to prevent problem like that in the future. For example, I see in 
the latest FordFulkerson who you are using a 'copyWeights' variable to 
temporarily save the capacities so that you can use dijkstra with weight 1 
everywhere, then reload the old weights. Right now we have to do it this way 
with a full graph copy, because of the distinct arc weights.

(I am not asking you to rewrite dijkstra yet. After the summer maybe).

>  
> Another option could be just setting those weights (from attribute 
> values) just before running Dijkstra....is that a good way?

Yes, that is a possibility. The 'arc attr' method will be of help. It provides 
a dictionary of the arc -> value mapping for a named attribute A.

 > Then I
> could use only attributes in implementation, both for costs and 
> throughputs ( arc weights would be set only for Dijkstra ).
>  
> Please, tell me which version you consider better? So, I will correct it 
> to get a final version.

I would say, try to use arc attributes (see the short doc above for node 
attributes, then replace node -> arc for the equivalent methods). Document the 
name of the arc attributes.


> About Dijkstra....I created test cases where Dijkstra easily 
> fails....so, BFS will be needed surely :) Regarding other mail....if we 
> would want to use Dijkstra anyway, it would need creating separate 
> version of it, or if we don't want any optimizations, just making sure 
> it won't get any negative weights should do the trick ...but still BFS 
> looks better....

I will leave that decision in your hands, you are nearer to the code and the 
possible effort required for either solution.

Andreas.