Wie soll ich mein Objekt erstellen, so dass es ziemlich gut mit NetworkX funktioniert?

Question

Ich versuche, ein Projekt zu entwickeln, die globalen Positionierungsdaten, wie Stadt und Staat Namen zusammen mit Breiten und Orten stattfindet. Ich werde auch Abstände zwischen jedem Paar von Städten. Ich möchte ein Diagramm mit all diesen Informationen machen, und manipulieren sie einige Graphenalgorithmen auszuführen. Ich habe beschlossen, Stadt Objekte zu haben, die die Lage jedes Daten enthält. Nun sollte ich eine Hash-Funktion zu unterscheiden Objekte haben? Und wie soll ich Graphenalgorithmen verarbeiten, die Knoten und Kanten entfernen kombinieren?

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]))

Es ist in sehr schlechten Zustand. Ich mein ursprüngliches Programm umgeschrieben, aber dies ist der Ansatz, den ich von der vorherige Version habe.

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.