By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,660 Members | 1,102 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,660 IT Pros & Developers. It's quick & easy.

Graph Theory

P: n/a
Is there any library in Python which has implementation of graph
theoretic algorithms and models ?

Oct 5 '06 #1
Share this Question
Share on Google+
10 Replies


P: n/a
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

P: n/a
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

P: n/a
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

P: n/a
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

P: n/a

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

P: n/a
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

P: n/a
Thanks for all your responses.

Oct 6 '06 #8

P: n/a
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

P: n/a
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

P: n/a
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.