Structuring TensorFlow Models

Danijar Hafner has an excellent tutorial on Structuring Your TensorFlow Models. I really liked it so I am posting it here so its always easy to find. He is using Python’s decorators to provide a lazy initialization for the graph components. Its a neat trick. Totally separate from TensorFlow, I am actively working on improving my Python programming and will definitely be using this approach in the future.

NetworkX Graph library for Python

I’ll admit – I still try and write Python like it was C or C++. To fix that for a while I am going to switch to writing things in Python for a while, while working on actually writing good Python.

Graph algorithms are the kidneys of computer science – there in the background filtering out all the bad things for us. In my switch over to writing in Python I needed to find a solid python graph library, and decided to try NetworkX. Here is a simple example program using it. These are mostly just notes for myself – but I am posting it here in case it is useful to anyone else.

This code is basically the NetworkX weighted graph example, with some annotations. Here is some code to create and plot a weighted graph.


import matplotlib.pyplot as plt
import networkx as nx

# Populate the graph...
map_graph = nx.Graph()

map_graph.add_edge('Issaquah','Bellevue', weight=0.11 )
map_graph.add_edge('Bellevue','Kirkland', weight=0.05 )
map_graph.add_edge('Bellevue','Redmond', weight=0.06 )
map_graph.add_edge('Kirkland','Redmond', weight=0.24 )
map_graph.add_edge('Bellevue','Seattle', weight=0.01 )
map_graph.add_edge('Renton','Seattle', weight=0.03 )
map_graph.add_edge('Renton','Bellevue', weight=0.48 )

# Determine the layout of points in the graph. Some other layouts that 
# would work here are spring_layout, shell_layout, and random_layout                                                                                                 
pos = nx.circular_layout( map_graph ) # Sets positions for nodes

# Put "dots" down for each node                                                     
nx.draw_networkx_nodes( map_graph, pos, node_size=700)

# Attaches Labesl to each node                                                               
nx.draw_networkx_labels( map_graph, pos, font_size=14, font_family='sans-serif')

map_edges = [(u,v) for (u, v, d) in map_graph.edges(data=True) ]

nx.draw_networkx_edges( map_graph,
                        pos,             # Spring
                        map_edges,       # List of edges                                     
                        width=5, alpha=0.5, edge_color='b', style='dashed' )

plt.axis('off')
plt.show()

The plotted graph looks something like this.

Screen Shot 2018-04-29 at 5.01.30 PM

One of the things I want from a graph library is the standard graph algorithms – like finding me the shortest path between nodes, or testing for the presence of a path at all. So for example to find the shortest path from Issaquah to Renton we could add the following code to the example above?:


# Generates the shortest path - but since there could be more than                                                   
# one of them what you get back is a "generator" from which you                                                      
# need to pluck the shortest path.                                                                                   
a_shortest_path = nx.all_shortest_paths(map_graph, source='Issaquah', target='Renton')                              

print( [p for p in a_shortest_path] )    

The added code will give the path [['Issaquah', 'Bellevue', 'Renton']], which is the shortest path by number of edges traversed. To obtain the shortest path by edge weight we can use dijkstras like so:


a_shortest_path = nx.dijkstra_path(map_graph, ‘Issaquah’, ‘Renton’)
print( a_shortest_path )

Which gives the path: ['Issaquah', 'Bellevue', 'Seattle', 'Renton']

The problem is that this implementation of dijkstra’s fails when a path is not present between the origin and destination nodes. So for example if we add a disconnected vertex with no edges like below, searches on a path to that vertex will cause the call to fail.


map_graph.add_node(‘Mercer Island’)

Screen Shot 2018-04-29 at 8.15.15 PM

I think you need to use the has_path method to test for the existence of any path first, then if there is a path use dijkstras to find the minimum cost path. Something like this:


# Create a helper function for testing for a path
def shortest_weighted(from_node, to_node):
    if nx.has_path( map_graph, from_node, to_node ) == True :
	a_shortest_path = nx.dijkstra_path(map_graph, from_node, to_node)
        return( a_shortest_path )
    else:
        print("No path from",from_node,"to", to_node, "\r\n")
        return( False )

Then checking for the minimum path can look something like this:


# Test where path does not exist
shortest_weighted_path = shortest_weighted( 'Issaquah', 'Mercer Island' )
if shortest_weighted_path != False:
    print( shortest_weighted_path )

# Test where path does exist
shortest_weighted_path = shortest_weighted( 'Issaquah', 'Renton' )
if shortest_weighted_path != False:
    print( shortest_weighted_path )

Neither call will fail and checking for the existing path from Issaquah to Renton will return: ['Issaquah', 'Bellevue', 'Seattle', 'Renton']

Since the graphs are weighted – list comprehensions can be used to conditionally act based on edge weights. For example:


# Segment the nodes by weight                                                                                                  
map_red_edges  = [(u,v) for (u, v, d) in map_graph.edges(data=True) if d['weight'] >  0.1  ]
map_blue_edges = [(u,v) for (u, v, d) in map_graph.edges(data=True) if d['weight'] <= 0.1  ]

Then use the segmentation to perform multiple colorings.


nx.draw_networkx_edges( map_graph,
                        pos,             # Spring                                                                    
                        map_red_edges,   # List of edges                                                             
                        width=5,
                        alpha=0.5,
                        edge_color='r',
                        style='dashed' )

nx.draw_networkx_edges( map_graph,
                        pos,             # Spring                                                                    
                        map_blue_edges,  # List of edges                                                             
                        width=5,
                        alpha=0.5,
                        edge_color='b',
                        style='solid' )

Which will produce the following graph:

Screen Shot 2018-04-29 at 9.49.43 PM

Also useful is shortest_path, which returns all the paths between all nodes, but sorted by vertex traversal path length. So the following code:


paths = nx.shortest_path(map_graph)
print( paths )

Generates the following paths.


{'Issaquah': {'Issaquah': ['Issaquah'], 'Bellevue': ['Issaquah', 'Bellevue'], 'Kirkland': ['Issaquah', 'Bellevue', 'Kirkland'], 'Redmond': ['Issaquah', 'Bellevue', 'Redmond'], 'Seattle': ['Issaquah', 'Bellevue', 'Seattle'], 'Renton': ['Issaquah', 'Bellevue', 'Renton']}, 'Bellevue': {'Bellevue': ['Bellevue'], 'Issaquah': ['Bellevue', 'Issaquah'], 'Kirkland': ['Bellevue', 'Kirkland'], 'Redmond': ['Bellevue', 'Redmond'], 'Seattle': ['Bellevue', 'Seattle'], 'Renton': ['Bellevue', 'Renton']}, 'Kirkland': {'Kirkland': ['Kirkland'], 'Bellevue': ['Kirkland', 'Bellevue'], 'Redmond': ['Kirkland', 'Redmond'], 'Issaquah': ['Kirkland', 'Bellevue', 'Issaquah'], 'Seattle': ['Kirkland', 'Bellevue', 'Seattle'], 'Renton': ['Kirkland', 'Bellevue', 'Renton']}, 'Redmond': {'Redmond': ['Redmond'], 'Bellevue': ['Redmond', 'Bellevue'], 'Kirkland': ['Redmond', 'Kirkland'], 'Issaquah': ['Redmond', 'Bellevue', 'Issaquah'], 'Seattle': ['Redmond', 'Bellevue', 'Seattle'], 'Renton': ['Redmond', 'Bellevue', 'Renton']}, 'Seattle': {'Seattle': ['Seattle'], 'Bellevue': ['Seattle', 'Bellevue'], 'Renton': ['Seattle', 'Renton'], 'Issaquah': ['Seattle', 'Bellevue', 'Issaquah'], 'Kirkland': ['Seattle', 'Bellevue', 'Kirkland'], 'Redmond': ['Seattle', 'Bellevue', 'Redmond']}, 'Renton': {'Renton': ['Renton'], 'Seattle': ['Renton', 'Seattle'], 'Bellevue': ['Renton', 'Bellevue'], 'Issaquah': ['Renton', 'Bellevue', 'Issaquah'], 'Kirkland': ['Renton', 'Bellevue', 'Kirkland'], 'Redmond': ['Renton', 'Bellevue', 'Redmond']}, 'Mercer Island': {'Mercer Island': ['Mercer Island']}}

A Cool way to do tree / graph traversal

As part of the latest skills review – I am going back over my coding and trying to get better. Being honest I have been pleasantly surprised, but embarrassed, by some of the places I have found I have room for improvement. It is worth it though – cause sometimes you catch gems like this.

When traversing trees, I tend to traverse them like they were graphs, and using queues. So for the problem of traverse a binary tree (not a BST), and return the largest value in each row I wrote the following code:


    vector largestValues(TreeNode* root) {
        vector maxrowval;
        
        if( root == NULL )
            return(maxrowval);
        
        queue > treesearch;
        treesearch.push(make_pair(root,0));
        
        while( !treesearch.empty()){
            TreeNode* curNode = treesearch.front().first;
            int curDepth = treesearch.front().second;
            treesearch.pop();
            
            if( maxrowval.size() <= curDepth ){
                maxrowval.push_back(curNode->val);
            }
            
            if( maxrowval[curDepth] < curNode->val ){
                maxrowval[curDepth] = curNode->val;
            }
            
            if( curNode->left != NULL ){
                treesearch.push(make_pair(curNode->left, curDepth+1));
            }
            
            if( curNode->right != NULL ){
                treesearch.push(make_pair(curNode->right, curDepth+1));
            }
        }
        
        return( maxrowval );
    }

What I just ran across was someone who wrote the following code for the same problem. He is using a list as opposed to a queue – but the logic of what we are doing is about the same. Only his double nested loop traversal of the list should be much faster. It avoids a lot of pushing and popping operations, and leaves the constructed search list intact. I am posting this here so I can come back and look at this later. This is the kind of thing I am going to want to stew on and see where else it might be a useful thing to have in the toolbox.


    vector largestValues(TreeNode* root) {
        vector result;
        list current;
        
        if (root != nullptr) {
            current.push_back(root);
        }
        
        while (current.size()) {
            int max_value = INT_MIN;
            int size = current.size();
            while (size) {
                TreeNode* node = current.front();
                max_value = max(max_value, node->val);
                current.pop_front();
                if (node->left != nullptr) {
                    current.push_back(node->left);
                }
                
                if (node->right != nullptr) {
                    current.push_back(node->right);
                }
                size--;
            }
            result.push_back(max_value);
        }
        
        return result;
    }

Mathematical Quickies No.122

This problem kind of bugs me. Here is the problem and my first step:

Mathematical Quickies No.122

So I like my first step – but then my way of solving {a(a-1)(a-2)(a-3) = 120} is wonky. I want to expand it and use the quadratic equation – which is not slick enough to be what they are after. I am not seeing synthetic division, or any usual suspects – so I think I am missing something obvious.

Rick, someone I work with, looked at the problem and immediately said you could tell that the solution needed to be divisible by 5, which happens to be a valid solution here. However I don’t believe that is always the case though.

My way to get the solution shows a solution of {-2,5}. Work shown here.

Mathematical Quickies No.84

This is another example of a substitution problem. Normally I would have just worked it out long hand, expanding thing and solving. That’s a lot of work and frankly kind of a foolish way to attack the problem looking at it now. Since I started looking for substitutions first – the problem collapses to simple in one substitution. Unfortunately its still fairly un-elegant – so I don’t think this is the solution they book is looking for.

The problem is stated as: “Solve: (6x+28)^1/3 – (6×-28)^1/3 = 2″

My solution

Mathematical Quickies No.205

I kind of hate problems where the solution is to find the most elegant answer possible. This problem is an excellent example of why. My solution (here), solves the problem as stated – but I took a grinder solution just wearing the problem away. My gut says that there is no way that this is the solution they want – however I do solve it with multiple applications of the quadratic equation, which the problem framing hinted at, so I am posting it for now.

Knowing that this is not the solution they wanted, I want to go look at the back of the book to confirm that is the case, and see what they were after. The problem with looking though is that I ruin the problem. So, I pretty much never want to look – hence my dislike of problems I where I can not prove I have the right solution. They all seem to be asking me to prove that someone smarter than I am could not solve the problem in a more elegant manner, but since the person in question is by definition smarter than I am – well – it seems a might ridiculous.

Here we have the problem:

“Solve this equation using nothing higher tan quadratic equations:

X = Sqrt( (X-(1/X)) + Sqrt(1-(1/X)) )”

My Solution

Mathematical Quickies No.226

So for some reason I never started looking for substitutions when solving equations. It was certainly something I learned to do when analyzing circuits, but when I see a math problem I never started looking for substitutions that might simplify the problem. Until recently.

Looking at, I think this problem, it “just clicked” – and I started looking for substitutions. Then used them to nock out answers for the next half dozen puzzle problems I tackled. Weird, since I am not doing anything I did not know before, but I just started looking at problems differently.

This one is fairly straight forward:

Solve: (x-a)/b + (x-b)/a = b/(x-a) + a/(x-b)

It becomes way easier to solve after a simple substitution.
My Solution.

Calculating N^2 as a series?

I am working on a problem from project Euler solving for Pythagorean triplets. I think it is supposed to be a simple coding problem solved brute force with two for loops. Something about the problem has my gut telling to try to solve the problem a little more elegantly.  To that end I was looking at trying to calculate N^2 as a series so I could break up the triplets into over common and different components to manipulate.

This is the first thing that jumped out at me – obvious pattern when I thought about N^2 having 2N as the first derivative and 2 as the second – but I did not see it right away. Might be useful.