numpy-discussion

[Numpy-discussion] Graph class

[David G. <dav...@gm...>]

I have written my own graph class, it doesn't really do much, just has a few
methods, it might do more later. Up until now it has just had one piece of
data, an adjacency matrix, so it looks something like this:

class Graph:
    def __init__(self, Adj):
        self.Adj = Adj

I had the idea of changing Graph to inherit numpy.ndarray instead, so then I
can just access itself directly rather than having to type self.Adj. Is this
the right way to go about it? To inherit from numpy.ndarray?

The reason I'm using a numpy array to store the graph by the way is the
following:
-Memory is not a concern (yet) so I don't need to use a sparse structure
like a sparse array or a dictionary
-I run a lot of sums on it, argmin, blanking out of certain rows and columns
using fancy indexing, grabbing subgraphs using vector indexing

-- 
David Grant
http://www.davidgrant.ca

Re: [Numpy-discussion] Graph class

[Bill B. <wb...@gm...>]

Hi David,

For a graph, the fact that it's stored as a matrix, or stored as
linked nodes, or dicts, etc,  is an implementation detail.  So from a
classical OO point of view, inheritance is not what you want.
Inheritance says "this is a kind of that".  But a graph is not a kind
of matrix.  A matrix is merely one possible way to represent a graph.
Many matrix operations don't even make sense on a graph (although a
lot of them do...).  Also you say "memory is not a concern (yet)", but
maybe it will be later, and then you'll want to change the underlying
representation.  Ideally you will be able to do this in such a way
that all your graph-using code works completely without modification.
This will be harder to do if you derive from ndarray.  Because to
prevent existing code from breaking you have to duplicate ndarray's
interface exactly, because you don't know which ndarray methods are
being used by all existing Graph-using code.

On the other hand, in the short term it's probably easier to derive
from ndarray directly if all you need is something quick and dirty.
But maybe then you don't even need to make a graph class.  All you
need is

   Graph = ndarray

I've seen plenty of Matlab code that just uses raw matrices to
represent graphs without introducing any new type or class.  It may be
that's good enough for what you want to do.

Python is not really a "Classical OO" language, in the sense that
there's.no real data hiding, etc.  Python's philosophy seems to be
more like "whatever makes your life the easiest".  So do what you
think will make your life easiest based on the totality of your
circumstances (including need for future maintenance).

If memory is your only concern, then if/when it becomes and issue, a
switch to scipy.sparse matrix shouldn't be too bad if you want to just
use the ndarray interface.

--bill


On 8/2/06, David Grant <dav...@gm...> wrote:
> I have written my own graph class, it doesn't really do much, just has a few
> methods, it might do more later. Up until now it has just had one piece of
> data, an adjacency matrix, so it looks something like this:
>
> class Graph:
>     def __init__(self, Adj):
>         self.Adj = Adj
>
> I had the idea of changing Graph to inherit numpy.ndarray instead, so then I
> can just access itself directly rather than having to type self.Adj. Is this
> the right way to go about it? To inherit from numpy.ndarray?
>
> The reason I'm using a numpy array to store the graph by the way is the
> following:
> -Memory is not a concern (yet) so I don't need to use a sparse structure
> like a sparse array or a dictionary
> -I run a lot of sums on it, argmin, blanking out of certain rows and columns
> using fancy indexing, grabbing subgraphs using vector indexing
>
> --
> David Grant
> http://www.davidgrant.ca
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share your
> opinions on IT & business topics through brief surveys -- and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
>
> _______________________________________________
> Numpy-discussion mailing list
> Num...@li...
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
>
>
>

Re: [Numpy-discussion] Graph class

[David G. <dav...@gm...>]

Thanks Bill,

I think you are right, I think what I have is what I want (ie. not extending
ndarray). I guess do go along with the "whatever makes your life the
easiest" mantra, all I am really missing right now is the ability to access
my Graph object like this g[blah] with square brackets and to do vector
indexing and all that. What is the name of the double-underscored method
that I should implement (and then call the underlying datastructure's
corresponding method)? I see __getitem__ and __getslice__... hmm, this could
get messy. Maybe the way I have it is ok. Maybe I can live with G.Adj.

Dave


On 8/1/06, Bill Baxter <wb...@gm...> wrote:
>
> Hi David,
>
> For a graph, the fact that it's stored as a matrix, or stored as
> linked nodes, or dicts, etc,  is an implementation detail.  So from a
> classical OO point of view, inheritance is not what you want.
> Inheritance says "this is a kind of that".  But a graph is not a kind
> of matrix.  A matrix is merely one possible way to represent a graph.
> Many matrix operations don't even make sense on a graph (although a
> lot of them do...).  Also you say "memory is not a concern (yet)", but
> maybe it will be later, and then you'll want to change the underlying
> representation.  Ideally you will be able to do this in such a way
> that all your graph-using code works completely without modification.
> This will be harder to do if you derive from ndarray.  Because to
> prevent existing code from breaking you have to duplicate ndarray's
> interface exactly, because you don't know which ndarray methods are
> being used by all existing Graph-using code.
>
> On the other hand, in the short term it's probably easier to derive
> from ndarray directly if all you need is something quick and dirty.
> But maybe then you don't even need to make a graph class.  All you
> need is
>
>    Graph = ndarray
>
> I've seen plenty of Matlab code that just uses raw matrices to
> represent graphs without introducing any new type or class.  It may be
> that's good enough for what you want to do.
>
> Python is not really a "Classical OO" language, in the sense that
> there's.no real data hiding, etc.  Python's philosophy seems to be
> more like "whatever makes your life the easiest".  So do what you
> think will make your life easiest based on the totality of your
> circumstances (including need for future maintenance).
>
> If memory is your only concern, then if/when it becomes and issue, a
> switch to scipy.sparse matrix shouldn't be too bad if you want to just
> use the ndarray interface.
>
> --bill
>
>
> On 8/2/06, David Grant <dav...@gm...> wrote:
> > I have written my own graph class, it doesn't really do much, just has a
> few
> > methods, it might do more later. Up until now it has just had one piece
> of
> > data, an adjacency matrix, so it looks something like this:
> >
> > class Graph:
> >     def __init__(self, Adj):
> >         self.Adj = Adj
> >
> > I had the idea of changing Graph to inherit numpy.ndarray instead, so
> then I
> > can just access itself directly rather than having to type self.Adj. Is
> this
> > the right way to go about it? To inherit from numpy.ndarray?
> >
> > The reason I'm using a numpy array to store the graph by the way is the
> > following:
> > -Memory is not a concern (yet) so I don't need to use a sparse structure
> > like a sparse array or a dictionary
> > -I run a lot of sums on it, argmin, blanking out of certain rows and
> columns
> > using fancy indexing, grabbing subgraphs using vector indexing
> >
> > --
> > David Grant
> > http://www.davidgrant.ca
> >
> -------------------------------------------------------------------------
> > Take Surveys. Earn Cash. Influence the Future of IT
> > Join SourceForge.net's Techsay panel and you'll get the chance to share
> your
> > opinions on IT & business topics through brief surveys -- and earn cash
> >
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> >
> > _______________________________________________
> > Numpy-discussion mailing list
> > Num...@li...
> > https://lists.sourceforge.net/lists/listinfo/numpy-discussion
> >
> >
> >
>



-- 
David Grant
http://www.davidgrant.ca

Re: [Numpy-discussion] Graph class

[Charles R H. <cha...@gm...>]

Hi David,

I often have several thousand nodes in a graph, sometimes clustered into
connected components. I suspect that using an adjacency matrix is an
inefficient representation for graphs of that size while for smaller graphs
the overhead of more complicated structures wouldn't be noticeable. Have you
looked at the boost graph library? I don't like all their stuff but it is a
good start with lots of code and a suitable license.

Chuck

On 8/1/06, David Grant <dav...@gm...> wrote:
>
> I have written my own graph class, it doesn't really do much, just has a
> few methods, it might do more later. Up until now it has just had one piece
> of data, an adjacency matrix, so it looks something like this:
>
> class Graph:
>     def __init__(self, Adj):
>         self.Adj = Adj
>
> I had the idea of changing Graph to inherit numpy.ndarray instead, so then
> I can just access itself directly rather than having to type self.Adj. Is
> this the right way to go about it? To inherit from numpy.ndarray?
>
> The reason I'm using a numpy array to store the graph by the way is the
> following:
> -Memory is not a concern (yet) so I don't need to use a sparse structure
> like a sparse array or a dictionary
> -I run a lot of sums on it, argmin, blanking out of certain rows and
> columns using fancy indexing, grabbing subgraphs using vector indexing
>
> --
> David Grant
> http://www.davidgrant.ca
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share
> your
> opinions on IT & business topics through brief surveys -- and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
>
> _______________________________________________
> Numpy-discussion mailing list
> Num...@li...
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
>
>
>

Re: [Numpy-discussion] Graph class

[David G. <dav...@gm...>]

I actually just looked into the boost graph library and hit a wall. I
basically had trouble running bjam on it. It complained about a missing
build file or something like that.

Anyways, for now I can live with non-sparse implementation. This is mostly
prototyping code for integeration in to a largely Java system (with some
things written in C). So this will be ported to Java or C eventually.
Whether or not I will need to protoype something that scales to thousands of
nodes remains to be seen.

Dave

On 8/1/06, Charles R Harris <cha...@gm...> wrote:
>
> Hi David,
>
> I often have several thousand nodes in a graph, sometimes clustered into
> connected components. I suspect that using an adjacency matrix is an
> inefficient representation for graphs of that size while for smaller graphs
> the overhead of more complicated structures wouldn't be noticeable. Have you
> looked at the boost graph library? I don't like all their stuff but it is a
> good start with lots of code and a suitable license.
>
> Chuck
>
> On 8/1/06, David Grant <dav...@gm...> wrote:
>
> > I have written my own graph class, it doesn't really do much, just has a
> few methods, it might do more later. Up until now it has just had one piece
> of data, an adjacency matrix, so it looks something like this:
>
> class Graph:
>     def __init__(self, Adj):
>         self.Adj = Adj
>
> I had the idea of changing Graph to inherit numpy.ndarray instead, so then
> I can just access itself directly rather than having to type self.Adj. Is
> this the right way to go about it? To inherit from numpy.ndarray?
>
> The reason I'm using a numpy array to store the graph by the way is the
> following:
> -Memory is not a concern (yet) so I don't need to use a sparse structure
> like a sparse array or a dictionary
> -I run a lot of sums on it, argmin, blanking out of certain rows and
> columns using fancy indexing, grabbing subgraphs using vector indexing
>
> --
> David Grant
> http://www.davidgrant.ca
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share
> your
> opinions on IT & business topics through brief surveys -- and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
>
> _______________________________________________
> Numpy-discussion mailing list
> Num...@li...
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
>
>
>
>


-- 
David Grant
http://www.davidgrant.ca

Re: [Numpy-discussion] Graph class

[Pau G. <pau...@gm...>]

you may be interested in this python graph library
https://networkx.lanl.gov/

pau

On 8/1/06, David Grant <dav...@gm...> wrote:
> I actually just looked into the boost graph library and hit a wall. I
> basically had trouble running bjam on it. It complained about a missing
> build file or something like that.
>
> Anyways, for now I can live with non-sparse implementation. This is mostly
> prototyping code for integeration in to a largely Java system (with some
> things written in C). So this will be ported to Java or C eventually.
> Whether or not I will need to protoype something that scales to thousands of
> nodes remains to be seen.
>
> Dave
>
>
> On 8/1/06, Charles R Harris <cha...@gm...> wrote:
> >
> > Hi David,
> >
> > I often have several thousand nodes in a graph, sometimes clustered into
> connected components. I suspect that using an adjacency matrix is an
> inefficient representation for graphs of that size while for smaller graphs
> the overhead of more complicated structures wouldn't be noticeable. Have you
> looked at the boost graph library? I don't like all their stuff but it is a
> good start with lots of code and a suitable license.
> >
> > Chuck
> >
> >
> >
> > On 8/1/06, David Grant < dav...@gm...> wrote:
> >
> > >
> >
> >
> > I have written my own graph class, it doesn't really do much, just has a
> few methods, it might do more later. Up until now it has just had one piece
> of data, an adjacency matrix, so it looks something like this:
> >
> > class Graph:
> >     def __init__(self, Adj):
> >         self.Adj = Adj
> >
> > I had the idea of changing Graph to inherit numpy.ndarray instead, so then
> I can just access itself directly rather than having to type self.Adj. Is
> this the right way to go about it? To inherit from numpy.ndarray?
> >
> > The reason I'm using a numpy array to store the graph by the way is the
> following:
> > -Memory is not a concern (yet) so I don't need to use a sparse structure
> like a sparse array or a dictionary
> > -I run a lot of sums on it, argmin, blanking out of certain rows and
> columns using fancy indexing, grabbing subgraphs using vector indexing
> >
> >
> > --
> > David Grant
> > http://www.davidgrant.ca
> >
> >
> -------------------------------------------------------------------------
> > Take Surveys. Earn Cash. Influence the Future of IT
> > Join SourceForge.net's Techsay panel and you'll get the chance to share
> your
> > opinions on IT & business topics through brief surveys -- and earn cash
> >
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> >
> > _______________________________________________
> > Numpy-discussion mailing list
> > Num...@li...
> >
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
> >
> >
> >
> >
> >
>
>
>
> --
> David Grant
> http://www.davidgrant.ca
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share your
> opinions on IT & business topics through brief surveys -- and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
>
> _______________________________________________
> Numpy-discussion mailing list
> Num...@li...
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
>
>
>

Re: [Numpy-discussion] Graph class

[David G. <dav...@gm...>]

I saw that one as well. Looks neat! Too bad they rarely mention the word
"graph" so they never come up on my google searches. I found them through
del.icio.us by searching for python and graph.

Dave

On 8/1/06, Pau Gargallo <pau...@gm...> wrote:
>
> you may be interested in this python graph library
> https://networkx.lanl.gov/
>
> pau
>
> On 8/1/06, David Grant <dav...@gm...> wrote:
> > I actually just looked into the boost graph library and hit a wall. I
> > basically had trouble running bjam on it. It complained about a missing
> > build file or something like that.
> >
> > Anyways, for now I can live with non-sparse implementation. This is
> mostly
> > prototyping code for integeration in to a largely Java system (with some
> > things written in C). So this will be ported to Java or C eventually.
> > Whether or not I will need to protoype something that scales to
> thousands of
> > nodes remains to be seen.
> >
> > Dave
> >
> >
> > On 8/1/06, Charles R Harris <cha...@gm...> wrote:
> > >
> > > Hi David,
> > >
> > > I often have several thousand nodes in a graph, sometimes clustered
> into
> > connected components. I suspect that using an adjacency matrix is an
> > inefficient representation for graphs of that size while for smaller
> graphs
> > the overhead of more complicated structures wouldn't be noticeable. Have
> you
> > looked at the boost graph library? I don't like all their stuff but it
> is a
> > good start with lots of code and a suitable license.
> > >
> > > Chuck
> > >
> > >
> > >
> > > On 8/1/06, David Grant < dav...@gm...> wrote:
> > >
> > > >
> > >
> > >
> > > I have written my own graph class, it doesn't really do much, just has
> a
> > few methods, it might do more later. Up until now it has just had one
> piece
> > of data, an adjacency matrix, so it looks something like this:
> > >
> > > class Graph:
> > >     def __init__(self, Adj):
> > >         self.Adj = Adj
> > >
> > > I had the idea of changing Graph to inherit numpy.ndarray instead, so
> then
> > I can just access itself directly rather than having to type self.Adj.
> Is
> > this the right way to go about it? To inherit from numpy.ndarray?
> > >
> > > The reason I'm using a numpy array to store the graph by the way is
> the
> > following:
> > > -Memory is not a concern (yet) so I don't need to use a sparse
> structure
> > like a sparse array or a dictionary
> > > -I run a lot of sums on it, argmin, blanking out of certain rows and
> > columns using fancy indexing, grabbing subgraphs using vector indexing
> > >
> > >
> > > --
> > > David Grant
> > > http://www.davidgrant.ca
> > >
> > >
> >
> -------------------------------------------------------------------------
> > > Take Surveys. Earn Cash. Influence the Future of IT
> > > Join SourceForge.net's Techsay panel and you'll get the chance to
> share
> > your
> > > opinions on IT & business topics through brief surveys -- and earn
> cash
> > >
> >
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> > >
> > > _______________________________________________
> > > Numpy-discussion mailing list
> > > Num...@li...
> > >
> > https://lists.sourceforge.net/lists/listinfo/numpy-discussion
> > >
> > >
> > >
> > >
> > >
> >
> >
> >
> > --
> > David Grant
> > http://www.davidgrant.ca
> >
> -------------------------------------------------------------------------
> > Take Surveys. Earn Cash. Influence the Future of IT
> > Join SourceForge.net's Techsay panel and you'll get the chance to share
> your
> > opinions on IT & business topics through brief surveys -- and earn cash
> >
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> >
> > _______________________________________________
> > Numpy-discussion mailing list
> > Num...@li...
> > https://lists.sourceforge.net/lists/listinfo/numpy-discussion
> >
> >
> >
>



-- 
David Grant
http://www.davidgrant.ca

Re: [Numpy-discussion] Graph class

[David M. C. <co...@ph...>]

On Tue, 1 Aug 2006 23:44:59 +0200
"Pau Gargallo" <pau...@gm...> wrote:

> you may be interested in this python graph library
> https://networkx.lanl.gov/

There's also http://wiki.python.org/moin/PythonGraphApi, which lists a bunch.
It's the result of a discussion on c.l.py a few years ago about trying to come
up with a standard API for graphs. I don't believe they came up with
anything, but that page contains ideas to consider.

-- 
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke                      http://arbutus.physics.mcmaster.ca/dmc/
|co...@ph...