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
|
