Graph Data Structures

Pieter Swart pieterswart at comcast.net
Sat Nov 25 23:49:55 EST 2006


Nathan Harmston wrote:

> 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????

Nathan

By now you probably discovered that the networkx package can handle
this.
If I have this right, you want to create a digraph with
a directed edge from "Node1" to "Node2" and this edge
has the string "Test3" attached to it. In networkx, this is exacty what
the  XDiGraph class was designed to do. Here DiGraph means
directed graph and the X means you are allowed to add (any)
data to the edge,for example:

>>> import networkx as nx
>>> t = nx.XDiGraph()
>>> t.add_edge( "Node1", "Node2", "Test3")


> 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.
>

Networkx was designed so that you can hook your own
C extension in. However, making it ispeed or memory efficient
is quite application dependent. I am still not clear as to exactly what

class of algorithms you want to implement via a string-interval
representation, and whether you demand exact alignment or whether
missing/incorrect data etc. is allowed as part of the alignment
problem.

HTH
Pieter Swart




More information about the Python-list mailing list