469,951 Members | 2,428 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,951 developers. It's quick & easy.

Graph Theory

Is there any library in Python which has implementation of graph
theoretic algorithms and models ?

Oct 5 '06 #1
10 4113
di********@gmail.com:
Is there any library in Python which has implementation of graph
theoretic algorithms and models ?
There are many of them, like:
https://networkx.lanl.gov/
Mine:
http://sourceforge.net/projects/pynetwork/
....and some other.

Bye,
bearophile

Oct 5 '06 #2
Thanks for your quick reply. Since I have not read the documentation, I
was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density. I am a
graph theory student and want to use python for development. Somebody
told me that Python has already so much bultin. Are there any
visualization tool which would depict the random graph generated by the
libraries.

Thanks for any kind of input.
be************@lycos.com wrote:
di********@gmail.com:
Is there any library in Python which has implementation of graph
theoretic algorithms and models ?

There are many of them, like:
https://networkx.lanl.gov/
Mine:
http://sourceforge.net/projects/pynetwork/
...and some other.

Bye,
bearophile
Oct 5 '06 #3
di********@gmail.com wrote:
Are there any visualization tool which would depict the random graph
generated by the libraries.
Google for DOT (.DOT format w/ renders to a variety of output formats).

--
--Scott David Daniels
sc***********@acm.org
Oct 5 '06 #4
di********@gmail.com:
>I was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density.
There are many kinds of random graphs, in that Graph lib I have added
few random generators, but you can add many more yourself, it's easy
(Then if you want you can send them back to be added to that lib, if
they are nice). Note that if you want to manage a LOT of nodes/arcs you
can use Boost Graph with Python.

I am a graph theory student and want to use python for development.
It can be useful for small and medium sized graphs.

Somebody told me that Python has already so much bultin.
Right.

Are there any visualization tool which would depict the random graph
generated by the libraries.
Graph exports in two common formats, like Dot and another. NetworkX
probably exports in Dot too. Look for Graphviz. And there is another
famous sofeware for huge graphs too.

Bye,
bearophile

Oct 5 '06 #5

di********@gmail.com wrote:
Thanks for your quick reply. Since I have not read the documentation, I
was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density. I am a
graph theory student and want to use python for development. Somebody
told me that Python has already so much bultin. Are there any
visualization tool which would depict the random graph generated by the
libraries.
networkx has several random graph generators, including:

barabasi_albert_graph
binomial_graph
erdos_renyi_graph
gnm_random_graph
gnp_random_graph
random_regular_graph
watts_strogatz_graph

and others (e.g. via configuration_model)

For drawing you can use pygraphviz (also available at
networkx.lanl.gov)
or the built-in drawing tools.

e.g.
>>from networkx import *
no_nodes=1000
for p in [ 0.1, 0.2, 0.3]:
g = watts_strogatz_graph(no_nodes, 4, p)
print density(g), average_clustering(g)
be warned that drawing large random graphs are not overly insightful

check the examples

Oct 5 '06 #6
di********@gmail.com wrote:
Is there any library in Python which has implementation of graph
theoretic algorithms and models ?
I don't know much about graph theory, but a coworker who does a lot of
it mentioned something about boost:

http://www.boost.org/libs/graph/doc/python.html
James

--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/
Oct 5 '06 #7
Thanks for all your responses.

Oct 6 '06 #8
Is there any documentation avaialbe for networkx ? I want to have an
implementation of random graphs including watts and strogatz graph.

bo****@comcast.net wrote:
di********@gmail.com wrote:
Thanks for your quick reply. Since I have not read the documentation, I
was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density. I am a
graph theory student and want to use python for development. Somebody
told me that Python has already so much bultin. Are there any
visualization tool which would depict the random graph generated by the
libraries.

networkx has several random graph generators, including:

barabasi_albert_graph
binomial_graph
erdos_renyi_graph
gnm_random_graph
gnp_random_graph
random_regular_graph
watts_strogatz_graph

and others (e.g. via configuration_model)

For drawing you can use pygraphviz (also available at
networkx.lanl.gov)
or the built-in drawing tools.

e.g.
>from networkx import *
no_nodes=1000
for p in [ 0.1, 0.2, 0.3]:
g = watts_strogatz_graph(no_nodes, 4, p)
print density(g), average_clustering(g)

be warned that drawing large random graphs are not overly insightful

check the examples
Oct 6 '06 #9
di********@gmail.com:
Is there any documentation avaialbe for networkx ? I want to have an
implementation of random graphs including watts and strogatz graph.
Try reading the code, often it's simple enough.

Bye,
bearophile

Oct 6 '06 #10
Other than reading the reference on the
website
https://networkx.lanl.gov/reference/networkx/

you can read the code (eg by browsing the
svn by pointing your web browser at
https://networkx.lanl.gov/browser/networkx/trunk

and then look at
networkx -generators -random_graphs.py)

If you are not in interactive python mode, try
pydoc networkx.watts_strogatz_graph

A great way to explore a python package is to
use ipython in interactive mode, then you merely
need to type
>>from networkx import *
watts_strogatz_graph?
and you will get the documentation.

di********@gmail.com wrote:
Is there any documentation avaialbe for networkx ? I want to have an
implementation of random graphs including watts and strogatz graph.
Oct 7 '06 #11

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

9 posts views Thread by Lilith | last post: by
25 posts views Thread by Magnus Lie Hetland | last post: by
11 posts views Thread by Andreas.Burman | last post: by
10 posts views Thread by andrea | last post: by
reply views Thread by bhadorn | last post: by
5 posts views Thread by chrispoliquin | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.