How should I create my object so it works with networkx pretty well?

Question

I'm trying to design a project that takes global positioning data, like city and state names along with latitudes and locations. I'll also have distances between every pair of cities. I want to make a graph with all of this information, and manipulate it to perform some graph algorithms. I've decided to have city objects which contains each location's data. Now should I have a hash function to differentiate objects? And how should I handle graph algorithms that combine nodes and remove edges?

def minCut(self):
    """Returns the lowest-cost set of edges that will disconnect a graph"""

    smcut = (float('infinity'), None)
    cities = self.__selectedcities[:]
    edges = self.__selectededges[:]
    g = self.__makeGRAPH(cities, edges)
    if not nx.is_connected(g):
        print("The graph is already diconnected!")
        return
    while len(g.nodes()) >1:
        stphasecut = self.mincutphase(g)
        if stphasecut[2] < smcut:
            smcut = (stphasecut[2], None) 
        self.__merge(g, stphasecut[0], stphasecut[1])
    print("Weight of the min-cut:  "+str(smcut[1]))

It's in really bad shape. I'm rewriting my original program, but this is the approach i took from the previous version.

Answer 1

Depending on what version of networkx you have installed, there is a built-in implementation of min_cut available.

I had the 1.0RC1 package installed and that was not available.. but I upgraded to 1.4 and min_cut is there.

Here's a (silly) example:

import networkx as nx
g = nx.DiGraph()
g.add_nodes_from(['London', 'Boston', 'NY', 'Dallas'])
g.add_edge('NY', 'Boston', capacity)
g.add_edge('Dallas', 'Boston')
g.add_edge('Dallas', 'London')
# add capacity to existing edge
g.edge['Dallas']['London']['capacity'] = 2
# create edge with capacity attribute
g.add_edge('NY', 'London', capacity=3)
print nx.min_cut(g, 'NY', 'London')

Answer 2

You don't need to create a hash function for the city objects, you can pass the city object directly to Networkx - from the tutorial "nodes can be any hashable object e.g. a text string, an image, an XML object, another Graph, a customized node object, etc."

You can iterate over the list of cities and add them as nodes and then iterate the distance information to make a graph.

Have you looked at the tutorial? http://networkx.lanl.gov/tutorial/tutorial.html

Answer 3

As you merge nodes, you can create new nodes and hash these new nodes to list of cities that have been merged. For example, in the above code you can name the new node len(g) and hash it to stphasecut[0]+ stphasecut[1] # assuming stphasecut[1] and[2] are lists.