Re: [Tcllib-devel] Graph Manip

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

Michał Antoniewski wrote:
> 
> Some remarks about Adjacency List:
>  
> For now I've done it like this:
>         -  user have 2 main options for adjacency list:
>               1.    listing each adjacent node for each node (DEFAULT - 
> 			classic form of Adjacency List) - let's call it "1 A"
>               2.    for each node: listing each edge for which that node 
> 			is a adjacent- let's call it "2 A"
>               3.    for both options (1 and 2) exists option considering 
> 			weights - let's call it "1 B" and "2 B"

How so ? ... Reading further, ok, you are adding the weight info into the result.

>               4.    additional option for recognising 
> 			directed/undirected graphs ( I tend to set directed as default )

Using the following graph as example:

	A -(2)-> B -(-1)-> C
	A, B, C nodes
	2, -1 arcs weights
	no names for the arcs.

>         - so now, for graph G with N nodes:
>               1.    "1 A" gives something like this:    { node1 ..... 
> 			nodeN }  { list of nodes adjacent to node1 } ......  { list of nodes 
> 			adjacent to nodeN   }

	result = {A B C} {{B} {A C} {B}}

Is my understanding of your description correct ?

If yes, would
	{nodeX {list of nodes adjacent to X} ...}

not be simpler ? In the terms of the example:

	result = {	A B \
			B {A C} \
			C B}

I.e. instead of two lists which are synchronized by index a single dictionary. 
It feels easier to process. Either with foreach {key value} ... or dict commands.

>               2.    "1 B" gives: { node1 ..... nodeN } { { nodeK 
> weightOfArc1->K }.....} .......  { {nodeL weightOfArcN->L} .... }

>        so for each node, there is a list of lists containing adjacent 
> node and weight of the regarding arc.

	result =	{A B C} {{{B 2}} {{A 2} {C -1}} {{B -1}}}
	?

Again a dictionary feels simpler:

	A {{B 2}} \
	B {{A 2} {C -1}} \
	C {{B -1}}

>  
>               3.    "2 A" gives: { {} node1 ..... nodeN } { node1 
> edgeK......edgeL } ......{ nodeN edgeH.......edgeM }
>  
>               4.    "2 B" gives: { {} node1 ..... nodeN } { node1 {edgeK 
> weight1-K }......{edgeL weight1-L} } ...

I am getting confused about the structure ... Because I do not understand where 
the {} before node1 comes from and why here node is in both lists.

>  
> Directed and undirected case is just, taking only edges where node is a 
> source in first case, and in latter taking all adjacent edges ( where 
> node is both source and target).


> Doubts:
> - is edge form ( 2A and 2B ) good idea? Mostly, it is used classic form 
> with node lists, but it can be some improvement to make availiable also 
> that form.

Do we have concrete algorithms needing the edge form ?
How complex would the generation of the edge forms be ? (timewise)

These are the two main factors to consider coming to my mind.

> - return value ...
>                for 1A and 1B - should (before each set of adjacent 
> nodes) there be placed a node to which next nodes are adjacent?
>                e.g. like this: { all nodes } { {node1} {node2 node3 
> node6} } ....

My understanding of this form is that you have a list of all nodes followed by 
a dictionary as I mentioned above. What is the reason for including a list of 
all nodes in the result ? Is that not implicitly the list of all keys in the 
dictionary ?

>  
> Actually, returns values can be quickly set at the end but for now, what 
> do you think of that organisation of AdjacencyList?

See all my thoughts and musing above ...

> Best Regards,
> Michał Antoniewski