[Tutor] Fwd: Re: "Path tree"

[Martin A. Brown]

Hello and good afternoon,

The image:

> http://imgur.com/a/CwA2G

To me, this looks like a 'graph', which is a more general data 
structure -- it does not look like a 'tree' (in the computer-science 
meaning of the term, anyway).

For purposes of all of my comments and answers below, I confess that 
I completely ignored the (x, y) in the image, because it seemed like 
every node ('dot') in your image was decorated with that.  See 
question(s) at the bottom of my message.

>> So in modeling this in your program you need to describe not just the
>> x,y coordinates, but also the connections. point 1 can only reach point
>> 2, so it has one link.  point 2 can reach 3 and 5, so two links.
>>
>> How can you describe this in your data model?

>I dont know what a data model is :(

'Data model' is a term to describe how you represent the world in 
your computer program.  Clearly, you have a question about the world 
and you want to use the computer to solve that question.  How do you 
do this?  Well, you create something in a computer language that 
tries to capture the important parts of the world for solving your 
problem.

Defining the data model in any problem is one of the great 
challenges of this game with computers that many of us play.  You 
gain experience simply by trying to solve problems.  (Sometimes, 
modelling the problem is harder than solving the problem.)

>I am thinking with one entry, I can have (x,y,z). Z is probably a 
>list and it says to what point it connects to. so it's a list of 
>lists. The problem then becomes: how do I generate a list of 
>possible routes? So I'll potentially have a very big list of routes 
>and then I choose the shortest one?

With your description of what you are looking to solve, my eye was 
drawn to the terms "list of possible routes" and "shortest [path]", 
it seems (that somebody has given you or) you have a classic graph 
problem.

>Please look at the picture attached: Those dots are coordinates of 
>(x,y), and this tree can be thought of as a list of tuples, with 
>each tuple consisting of (x,y).

I found this sentence the most confusing part of your description of 
the problem that you posted a day or two ago.  I'm still a bit 
confused, but if I ignore the above sentence entirely and focus on 
the rest of your questions, I think I know what you are asking.

<for_the_record>

Here are some things that confused me:

  * you used the word 'tree' which has a special meaning when 
    talking about data structures; a tree is a special form of 
    one class of graph
  * you used the word 'dots' because you were looking at a drawing 
    on a whiteboard, where many of us were thinking in more 
    abstract terms (well, I was, at least); so the word 'dots' meant 
    nothing to me until I saw your picture and realized that, to 
    you, these represented 'nodes' or 'vertices' (plural of 
    'vertex') in a 'graph' (data structure terminology)
  * you talked about 'coordinates' which suggests a measurable 
    geometric space -- I think you actually were trying to express 
    the notion of graph 'edges' (but I'm not sure! see below)

I was interested in your question (when you originally posted it), 
but couldn't figure out what you were actually trying to do and also 
did not understand what your real question was, so I would not have 
understood except that you posted the picture.

So, your follow-ups helped clarify that you are actually searching 
for data structure tools like the third-party graph library called 
networkx [0].

And, of course, I'll readily admit that sometimes expressing the 
problem in domain-specific or domain-relevant language is harder 
than solving the actual problem.

</for_the_record>

>Now I am trying to make a function go through this list of tuples 
>and then return the "path." to go from, say, 4 to 8. If I simply 
>compute for the dot for shortest distance, then the solution would 
>be to go from 4 to 8 direct, but that doesn't work, because the 
>correct solution should have been 4,3,2,5,6,8.

OK, so if the solution is 4,3,2,5,6,8, then your problem is a 
shortest path sort of graph theory problem and you can use the 
networkx library which has a huge number of tools for dealing with 
graphs (of many forms).

Below is a tailor-made example of how to model your picture in graph 
form using the networkx library.  My solution creates a data model 
representation of your graph (from your image) and then lists out 
the nodes ('dots'), the edges (lines connecting the dots) and then 
tries to find whether there's a path from node 4 to node 8.  Since 
there is a path from node 4 to node 8, it will print out the 
shortest such path.  You should recognize the answer:

Printed to STDOUT from my function below:

  Graph has nodes: [1, 2, 3, 4, 5, 6, 7, 8]
  Graph has edges: [(1, 2), (2, 3), (2, 5), (3, 4), (5, 6), (5, 7), (6, 8)]
  If there is a path in this graph from node 4 to node 8: True
  Path from 4 to 8: [4, 3, 2, 5, 6, 8]

>I am trying to formulate a "path-finding" function, and I am stuck 
>on this problem:

My main remaining questions:

  Why are you trying to find a path?
  What does the path (through this graph) tell you?
  What do (x, y) represent in that picture?

Good luck, Michael, in exploring Python for playing with graphs.  I 
think you may find that networkx will address almost anything you 
can throw at it for quite some time.  And, welcome to the Python 
world if you are new to it!

-Martin

 [0] https://networkx.github.io/


import networkx as nx


def solve_graph():
    g = nx.Graph()

    # -- my interpretation of http://i.imgur.com/MSq0p6z.png
    #    assumption:  not a tree
    #                 not a directed acyclic graph
    #                 not a directed graph
    #                 just a plain, undirected graph
    #
    description = [(1, 2), (2, 3), (3, 4), (2, 5), (5, 7), (5, 6), (6, 8)]
    g.add_edges_from(description)

    # -- nodes are also known as vertices in a graph
    #
    nodes = g.nodes()
    print("Graph has nodes: %r" % (nodes,))

    # -- the edges should be familiar -- identical to the above
    #
    edges = g.edges()
    print("Graph has edges: %r" % (edges,))

    # -- can you get to destination from source?
    source = 4
    destination = 8
    reachable = nx.has_path(g, source, destination)
    print("If there is a path in this graph from node %s to node %s: %s" %
          (source, destination, reachable,))

    # -- can you get to destination from source?
    if reachable:
        path = nx.shortest_path(g, source, destination)
        print("Path from %s to %s: %r" % (source, destination, path,))


-- 
Martin A. Brown
http://linux-ip.net/