Graph Data Structures

[Nathan Harmston]

Hi All,

Currently I am working on a generic graph library  so I can do various
graph based analysis for various projects I have ideas for. Currently
I am implementing Graph as a wrapper around a dictionary. Currently my
implementation works like this:

        t = Graph()
        n1 = Node("Node1")
        n2 = Node("Test2")
        edge1 = Edge("Test3")
        t += n1                                    { n1:{}}
        t[n1][n2] = edge1                    { n1:{n2:edge1}

However this isnt actually ending up with the structure I want. I want
it to finally end up as ......            { n1:{n2:edge1}, n2:{}}. Is
there anyway I can do this simply????

Also I am looking at having a large graph and was wondering if anyone
knew of anyway I could reduce the memory requirements of this
structure and improve the speed of queries on it. I m thinking writing
a C extension for it....is this a good idea and where would I start?
Or does Python have some kind of transparent memory access module I
can implement.

Many Thanks in advance,

Nathan

PS.....Please find my code below:

class Graph(object):
        def __init__(self, g= { } ):
                self.graph = g
        def __iadd__(self, p):
                if p not in self.graph:
                        self.graph[p] = PathsDict()
                return self
        def __getitem__(self, p):
                try:
                        return self.graph[p]
                except KeyError:
                        raise KeyError( "%s not in graph" %(repr(p)) )
        def __str__(self):
                return str(self.graph)
        def filter(self, filter):
                pass

class PathsDict(object):
        def __init__(self):
                self.paths = { }
        def __setitem__(self, p, val):
                if p not in self.paths:
                        self.paths[p] = val
        def __getitem__(self, p):
                return self.paths[p]
                # catch exception here
        def paths(self):
                for k, v in self.paths:
                        yield (k, v)
        def edges(self):
                return self.paths.values()
        def __str__(self):
                return str(self.paths)
        def __len__(self):
                return len(self.paths)

class Node(object):
        def __init__(self, name):
                self.name = name
        def __str__(self):
                return self.name

class Edge(dict):
        def __init__(self, name, weight = 1):
                self["name"] = name
                self["weight"] = weight
        def __str__(self):
                return self["name"]