[Tutor] Multiple Dimension (array/list/whatever it is are).

[Danny Yoo]

> On Monday 10 May 2004 20:33, George Patterson wrote:
> > 1. What is the data structure below called? Apart from G :-P  Is it an
> > array, a list or something else. The original article was very vague on the
> > commenting. See bottom of email for URL.
> >
> > G = {'s':{'u':10, 'x':1},
> >      'u':{'v':1, 'x':2},
> >      'v':{'y':4},
> >      'x':{'u':3, 'v':9, 'y':2},
> >      'y':{'s':7, 'v':6}
> >     }


On Mon, 10 May 2004, Thomas Clive Richards wrote:
>
> This is a dictionary....containing other dictionaries. They're used to
> provide key->value mappings.




Hi George,


And in this particular case, G lets us get from a given vertex to its
"edges".  We can interpret:

###
G_simpler = {'s': {'u':10, 'x':1},
             'u': {'x':2} }
###

as representing a directed graph.  Graphs are made of vertices and edges
--- circles and arrows.

             10
      s  -----------> u
        \         /
         \       /
        1 \     / 2
           \   /
            \ /
             |
             V

             x


If it helps, treat the graph as an Abstract Data Structure: don't
explicitely touch the graph itself, but write helper functions that touch
the graph for you.

###
def neighbors(graph, vertex):
    """Returns all names of the neighbors of the vertex."""
    ## ...  [fill me in]


def setEdge(graph, start_vertex, end_vertex, cost):
    """Sets an edge between the start_vertex and the end_vertex with a
    cost."""
    ## ... [fill me in]


def getEdgeCost(graph, start_vertex, end_vertex):
    """Looks up the cost for the edge between start_vertex and end_vertex.
    If no such edge exists, throws LookupError."""
    ## ... [fill me in]
###


Something like that.  All of the implementations need to be filled in.



The advantage of writing helper functions is that we can then manipulate
graphs at a more meaningful level.  Instead of saying:

    G['s']['x'] = 42

and worrying about managing a dictionary that contains another dictionary,
we can say:

    setEdge(G, 's', 'x', 42)

where the "graphiness" of our problem become more transparent.  The code
in the Cookbook doesn't do this ADT stuff only because the author assumed
that a dictionary within a dictionary is "obvious".  Obviously, this isn't
obvious.  *grin*



> > 2. How would I alter the above data structure such that all instances
> > of 'x' ends up being equal to 5. As per sample below.
> >
> > {'s':{'u':10, 'x':5},
> >      'u':{'v':1, 'x':5},
> >      'v':{'y':4},
> >      'x':{'u':3, 'v':9, 'y':2},
> >      'y':{'s':7, 'v':6}
> > }


The question is ambiguous.  Are we trying to make all edges that go into
'x' into five?  Or are we trying to change all the edges that go out of x
into five?  Or something else?  The main problem is that the question is
in terms of dictionaries, but the intent is not clear to us.  Can you
rephrase your question in terms of graphs?


What's nice about Python is that it's very easy to create compound data
structures with dictionaries.  What's not so nice is that it's all too
easy to treat all compound data structures as dictionaries.  *grin*


You may find it less confusing to write helper functions, like the
"Abstract Data Type" stuff above, and manipulate your graph through these
ADT functions.  That way, you don't have to worry about manipulating
dictionaries within dictionaries: instead, you can think in terms of the
graph problem you're trying to solve.


Good luck!