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__(sel f, 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(objec t):
def __init__(self):
self.paths = { }
def __setitem__(sel f, p, val):
if p not in self.paths:
self.paths[p] = val
def __getitem__(sel f, 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.valu es()
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"]

[Nathan Harmston]

Hi,

It seems that by just going through the problem writing out a better
explanation for the reply I have figured out a solution and the
problem isnt as difficult as I thought it would be.

What is a wontok?

Thanks

Nathan

PS --the start of my reply:

class Interval(object ):
_id = "gene1"
_start = 50
_end = 200
_strand = 1

class Sequence(object ):
_sequence = "atgtcgtgagagag agttgtgag...... ..........."

Only vaguely. You use several terms which appear to be from your trade
jargon

Sequence is a string made from a restricted alphabet (A,T,G,C...).
Sequences can be aligned: 1 ATGCTGCAT
2 TAGCTGTTA
-------
2 5

I m trying to represent this as a graph Interval(id=1, start=2, end=6,
strand=1) ---edge------Interval(id=2, start=2, end=6, strand=1)

The problem is I was planning on storing the sequences in a dictionary
{id:Seq}, however each dictionary would represent a different source
of sequences. File1, File2....... (
STORE THE SOURCES AS A DICT AND HAVE SOURCE IN INTERVAL ASWELL

[John Machin]

Nathan Harmston wrote:

Hi,

It seems that by just going through the problem writing out a better
explanation for the reply I have figured out a solution and the
problem isnt as difficult as I thought it would be.

Often happens.

>
What is a wontok?

It's Melanesian Pidgin (from the English "one talk") meaning a person
who speaks the same language as you, a member of your clan, ... the
context being that [at least in Papua New Guinea] there are relatively
many languages each with relatively not many speakers :-)

>
Thanks

Nathan

PS --the start of my reply:

class Interval(object ):
_id = "gene1"
_start = 50
_end = 200
_strand = 1

class Sequence(object ):
_sequence = "atgtcgtgagagag agttgtgag...... ..........."

Only vaguely. You use several terms which appear to be from your trade
jargon

Sequence is a string made from a restricted alphabet (A,T,G,C...).
Sequences can be aligned: 1 ATGCTGCAT
2 TAGCTGTTA
-------
2 5

I'm sure they can be, but appearances can be deceptive when you mix
tabs and spaces -- or whatever caused the above 4 lines to be not
vertically aligned but staggered diagonally like a flight of ducks
heading equatorwards for winter.

Sometimes a line of code (e.g. str1[2:6] == str2[2:6]) is worth a
thousand pictures :-)

>
I m trying to represent this as a graph Interval(id=1, start=2, end=6,
strand=1) ---edge------Interval(id=2, start=2, end=6, strand=1)

The problem is I was planning on storing the sequences in a dictionary
{id:Seq}, however each dictionary would represent a different source
of sequences. File1, File2....... (
STORE THE SOURCES AS A DICT

Mapping what keys to what values?

AND HAVE SOURCE IN INTERVAL ASWELL

So you had a data modelling problem. These are often better solved as a
separate step before you think about implementation details like
dictionaries.

Good luck with your project.

Cheers,
John

[Pieter Swart]

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