NanoPy #1

documentation / classes / lists and dictionaries / modules, namespaces, and import

Documentation

The Python Programming Language web page: www.python.org, especially the Documentation page at www.python.org/doc
From within the ipython interpreter: help(name) or name? where name is a Python module/class/object that is currently accessible

Classes

Most programming languages provide built-in data types (e.g., integers, floating point numbers, character strings), and many provide capabilities for adding new user-defined data types. Object-oriented (OO) languages allow programmers to define new data types that have behavior, i.e., functionality associated with them. Many OO languages - including Python - have a notion of a class, which is used to define new types of objects.

`class`

For our network/graph problem, we want to define a new data type describing undirected graphs, allowing us to add nodes and edges, query nodes for what other nodes they are connected to, etc. We're going to use the Python class keyword to define this new type:


class UndirectedGraph:
    # define undirected graph class within this block
    # by the way, Python comments begin with a pound sign #
    # also note that code blocks need to be consistently indented

`def`

Behaviors associated with a class are called methods, which are functions attached to the class definition. Methods are identified with the Python keyword def (short for define). To our UndirectedGraph class, we can begin to define methods to add nodes and edges:


class UndirectedGraph:
    def AddNode(self, node):
        # provide code to add a node to this instance of a graph 
        # (which we call, by convention, "self")
    def AddEdge(self, node1, node2):
        # provide code to add an edge connecting node1 and node2

`self`

The self argument in the methods above may seem confusing. In those methods, self refers to a particular instance of the UndirectedGraph class on which a method is being called. Let's say we have two graphs, named g1 and g2. The following happens when we execute methods on these graphs:


g1.AddNode(12)  means  UndirectedGraph.AddNode(g1, 12)   # g1 is self, 12 is node
g2.AddNode('hello') means  UndirectedGraph.AddNode(g2, 'hello')   # g2 is self, 'hello' is node

There is nothing special about the word "self", however; i.e., it is not a Python keyword. Any name would serve to identify the class instance in question; "self" is merely used by convention. If you were using def to define a standalone function that was not attached to a class definition, then you would not use the self argument. If you forget to provide the self argument in a method definition, you will see syntax errors that you have not provided the correct number of arguments.

`init`

Some special method names are reserved by Python to be associated with special behaviors. (Many of these methods are associated with overloaded operators.) Special method names begin and end with double underscores; the __init__ method, for example, is used to define a constructor method for a class, specifying how a new instance of a class is initialized.


class UndirectedGraph:
    def __init__(self):
        # provide code to initialize a new UndirectedGraph instance

A new instance g of an UndirectedGraph would be constructed as such: g = UndirectedGraph()

Lists and Dictionaries

Lists and dictionaries are two built-in container data types in Python (i.e., those that can hold other data types), and form the basis of many more complicated objects.

List: an ordered sequence of items

can consist of mixture of different types of items (including other lists)
can be grown or shrunk dynamically, e.g., list.append(newitem)

access via indexing, using the [] operator; starts counting at 0


alist = [3, 5.0, 'abc', [1, 2, 3]]
print alist[2], alist[3][0]      # prints 'abc', 1

Dictionary: an unordered set of keys and associated values

a.k.a., associative array, hash table, map; links keys to values
key can be any non-mutable Python type (e.g., numbers, strings, tuples, but not lists)

uses same indexing operator [] as lists


adict = {}          # make an empty dictionary
adict['a'] = 1      # associate key 'a' with value 1
print alist['a']    # prints 1

Think about what we need to be able to represent an UndirectedGraph. Sometimes graphs are represented via adjacency matrices, where a matrix element m[i][j] is 1 if nodes i and j are linked, and 0 otherwise. For graphs that are sparsely connected, however, most matrix elements are 0 and much storage is wasted. Another approach would be to hold a list of all pairs of nodes that define edges in a graph; but then a node with many edges is represented many times, and finding all the nodes connected to a given node is cumbersome. We will instead use dictionaries and lists to represent a graph: a dictionary can be used to associate a node ID with a list of neighboring node IDs:


class UndirectedGraph:
    def __init__(self):
	self.neighbor_dict = {}  # create an empty neighbor_dict dictionary
	# AddNode and AddEdge need to populate the dictionary

It should be noted that a dictionary which associates a key (node1) with a value (node2) implies a directionality of the edge. For an undirected graph, we should equally well be able to identify node1 as a neighbor of node2. Object-oriented programming (OOP) lets us encapsulate internal details of how an object is implemented without affecting the external interfaces describing how an object behaves.

Modules, namespaces, and import

Modules are units of Python code that can be used by other units, and form the building blocks of larger Python programs. Each module has a namespace, identifying the set of names (of variables, functions, classes, modules, etc.) available therein. One module becomes available for use within another when it is imported with an import statement. In the network problem, you will be creating a module implementing an UndirectedGraph. Fortunately, we have provided you with a separate module for displaying these graphs, implemented in file NetGraphics.py. All you need to do is import that module in order to access the graph drawing functions defined there:


import NetGraphics                 # import module, but without the ".py" suffix 
NetGraphics.DisplayCircleGraph(g)  # display graph g, laid out in a circle