473,569 Members | 2,383 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Graph Data Structures

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"]
Nov 25 '06 #1
12 2860
i haven't read your code, but there are many graph implementations in
python.
in case you haven't found these yet:
http://wiki.python.org/moin/PythonGraphApi

if you only want to do some analysis i think you need this one (as it's
pretty complete and simple):
https://networkx.lanl.gov/

i also recommend Guido's essay to read:
http://www.python.org/doc/essays/graphs.html

Nov 25 '06 #2
On Sat, 25 Nov 2006 14:05:27 +0000, Nathan Harmston wrote:
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:
[snip]

http://www.python.org/doc/essays/graphs.html

http://mail.python.org/pipermail/pyt...il/137593.html
Hope this helps.
--
Steven.

Nov 25 '06 #3
Szabolcs Nagy wrote:
.........
if you only want to do some analysis i think you need this one (as it's
pretty complete and simple):
https://networkx.lanl.gov/
.........

seems to be broken at present with a python traceback coming out; not a
good advert for python and/or trac
--
Robin Becker
Nov 25 '06 #4
Szabolcs Nagy:
i haven't read your code, but there are many graph implementations in
python.
in case you haven't found these yet:
http://wiki.python.org/moin/PythonGraphApi

if you only want to do some analysis i think you need this one (as it's
pretty complete and simple):
https://networkx.lanl.gov/

i also recommend Guido's essay to read:
http://www.python.org/doc/essays/graphs.html
I can also suggest my one:
http://sourceforge.net/projects/pynetwork/

And boost graph bindings for Python, quite fast:
http://www.osl.iu.edu/~dgregor/bgl-python/

Bye,
bearophile

Nov 25 '06 #5
https://networkx.lanl.gov/

This was working for me earlier, I managed to get everything from
there earlier. It seems a very good package. It seems theres more out
there than what I had thought, which unfortunately makes it harder for
me to decide what to use (pynetwork and bgl look useful aswell). I m
going to do some testing on it later and see what happens with it.
Thanks a lot for your help.

Has anyone got an idea how I could split the contents of a node and
its representation (to save memory in my graph). ie.... the nodes
contain the start and end coordinates and id and the actual
representation contains the string. I was going to have :

class Node(object):
pass

class Section(Node):
pass

class Item(object):
pass

Where section contains a slice of the Item which im interested. I m
just not sure how I can access the contents of item without storing
it. ---If u get what I mean???

Many Thanks in advance

Nathan
Nov 25 '06 #6

Nathan Harmston wrote:
https://networkx.lanl.gov/

This was working for me earlier, I managed to get everything from
there earlier. It seems a very good package. It seems theres more out
there than what I had thought, which unfortunately makes it harder for
me to decide what to use (pynetwork and bgl look useful aswell). I m
going to do some testing on it later and see what happens with it.
Thanks a lot for your help.

Has anyone got an idea how I could split the contents of a node and
its representation (to save memory in my graph). ie.... the nodes
contain the start and end coordinates and id and the actual
representation contains the string. I was going to have :

class Node(object):
pass

class Section(Node):
pass

class Item(object):
pass

Where section contains a slice of the Item which im interested. I m
just not sure how I can access the contents of item without storing
it. ---If u get what I mean???
No. Not at all. "pass" is not very informative. Neither are
"representation " and "the string". Please tell us what you mean by
"slice". What is an "item", if it's not a "node"? Try listing out the
attributes of a node, with a couple of sample values for each, and then
we might get a clue.

What makes you think that you need to save memory?

What makes you think that you could save memory by splitting whatever
it is?

HTH,
John

Nov 25 '06 #7
Nathan Harmston wrote:
https://networkx.lanl.gov/
.......

I got it back just once, but when I clicked again I see this

RuntimeError Python 2.4.4c1: /usr/bin/python
Sat Nov 25 16:21:16 2006

A problem occurred in a Python script. Here is the sequence of function
calls leading up to the error, in the order they occurred.
/build/bdist.linux-x86_64/egg/tracrst/macro.py in
render_macro(se lf=<tracrst.mac ro.TracReSTMacr o object>, req=<trac.web.a pi

.......

782 self.__dict__["_parent_po ol"] = \
783 parent_pool or libsvn.core.app lication_pool;
784 if self.__dict__["_parent_po ol"]:
self = <libsvn.repos.s vn_repos_t; proxy of C svn_repos_t instance>,
self.__dict__ = {'this': <Swig Object of type 'svn_repos_t *'>},
parent_pool = <libsvn.core.ap r_pool_t; proxy of C apr_pool_t instance>,
libsvn = <module 'libsvn' from
'/usr/lib/python2.4/site-packages/libsvn/__init__.pyc'>, libsvn.core =
<module 'libsvn.core' from
'/usr/lib/python2.4/site-packages/libsvn/core.pyc'>,
libsvn.core.app lication_pool = <libsvn.core.ap r_pool_t; proxy of C
apr_pool_t instance>

RuntimeError: instance.__dict __ not accessible in restricted mode
args = ('instance.__di ct__ not accessible in restricted mode',)
perhaps I'm seeing different apache processes or something
--
Robin Becker
Nov 25 '06 #8
Hi,

The idea is that I m going to use it to build graphs for sequence
alignment (at the moment), I read a discussion on the corebio
(reimplementati on of biopython) group about using intervals to
represent sequence slices. The idea being that, my graph may contain
millions of alignments and storing the sequence (the actual ATGC) is
not required.

class Node(object):
pass

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

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

So one interval on one sequence would align to another interval from
another sequence, but I want changes I make to the interval to be
reflected in the representation later. If I reverse complement it i
want the interval to store this information but the Sequence only
shows this later on when I call use it calling repr or str.

Do you get what I mean.
Many Thanks

Nathan
Nov 25 '06 #9

Nathan Harmston wrote:
Hi,

The idea is that I m going to use it to build graphs for sequence
alignment (at the moment), I read a discussion on the corebio
(reimplementati on of biopython) group about using intervals to
represent sequence slices. The idea being that, my graph may contain
millions of alignments and storing the sequence (the actual ATGC) is
not required.

class Node(object):
pass

class Interval(Node):
_id = "gene1"
_start = 50
_end = 200
_strand = 1
What is the point of subclassing Node if it's just a dummy?
>
class Sequence(object ):
_sequence = "atgtcgtgagagag agttgtgag...... ..........."

So one interval on one sequence would align to another interval from
another sequence, but I want changes I make to the interval to be
reflected in the representation later. If I reverse complement it i
want the interval to store this information but the Sequence only
shows this later on when I call use it calling repr or str.

Do you get what I mean.
Only vaguely. You use several terms which appear to be from your trade
jargon as they are not understandable when interpreted in either the
context of Python-speak or ordinary English e.g. "sequence",
"alignment" , "ATGC", "reverse complement", "interval".

Two options:
(a) communicate understandably
(b) wait till your wontoks are back from holidays.

Nov 25 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

25
3768
by: Magnus Lie Hetland | last post by:
Is there any interest in a (hypothetical) standard graph API (with 'graph' meaning a network, consisting of nodes and edges)? Yes, we have the standard ways of implementing graphs through (e.g.) dicts mapping nodes to neighbor-sets, but if one wants a graph that's implemented in some other way, this may not be the most convenient (or...
2
2769
by: Christian Christmann | last post by:
Hi, I need to write a graph which provides at least the following functions: 1) stores nodes and edges (both store further information which can be of any type) 2) manipulations on nodes and edges like delete, add ... 3) provides a list of all successors/predecessors for a given node 4) provides a list of all nodes that can be reached...
4
9012
by: Sameer | last post by:
Hello, A data structure for the implementation of graph can be struct node { int index; struct node *next; };
1
2743
by: Gregor Rot | last post by:
Hi, i am interested in the fastest possible representation of an undirected graph G=(V,E) (vertex, edge representation) in connection with the Kruskal's algorithm (finding a minimal spanning tree)...anyway, what's the best way to represent a graph in c (talking about data structures)? tnx, Greg
3
2816
by: alice | last post by:
hi all, I am very new to graphs.So can somebody please give me a link to some graphs tutorial as well as their assignment. Thanks, Alice Walls
10
1890
by: andrea | last post by:
I'm studying some graphs algorithm (minumum spanning tree, breath search first topological sort etc etc...) and to understand better the theory I'm implementing them with python... I made my own graph class, the constructor is simply this: class graph: "in forma di matrice e' una matrice normale, in forma di lista uso un dizionario" def...
2
1959
by: tmuldner | last post by:
Hi, I am looking for existing software/description of a directed graph representation of an XML Schema. Any help will be appreciated.
2
4126
by: sriniwas | last post by:
Hi Frnd's, m using prefuse visulation,it's have one display class and this class have one saveImage(outPutStream, String jpg,double size);. now graph is converting ia jpg image properly.now my problem is tht,If graph is to large if it going out of screen thn ,i m getting jpg image on screen disply graph,m not getting the image of tht graph...
5
4433
by: chrispoliquin | last post by:
I need to represent the hyperlinks between a large number of HTML files as a graph. My non-directed graph will have about 63,000 nodes and and probably close to 500,000 edges. I have looked into igraph (http://cneurocvs.rmki.kfki.hu/igraph/doc/ python/index.html) and networkX (https://networkx.lanl.gov/wiki) for generating a file to store...
0
7926
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8132
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
6286
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5514
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5222
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3656
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3644
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2116
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
944
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.