Graph Theory

[diffuser78]

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

[bearophileHUGS]

di********@gmai l.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

[diffuser78]

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********@gmai l.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

[Scott David Daniels]

di********@gmai l.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***********@a cm.org

[bearophileHUGS]

di********@gmai l.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

[boggom]

di********@gmai l.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_gra ph
gnm_random_grap h
gnp_random_grap h
random_regular_ graph
watts_strogatz_ graph

and others (e.g. via configuration_m odel)

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

e.g.

>>from networkx import *
no_nodes=10 00
for p in [ 0.1, 0.2, 0.3]:
g = watts_strogatz_ graph(no_nodes, 4, p)
print density(g), average_cluster ing(g)

be warned that drawing large random graphs are not overly insightful

check the examples

[James Stroud]

di********@gmai l.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/

[diffuser78]

Thanks for all your responses.

[diffuser78]

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********@gmai l.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_gra ph
gnm_random_grap h
gnp_random_grap h
random_regular_ graph
watts_strogatz_ graph

and others (e.g. via configuration_m odel)

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

e.g.

>from networkx import *
no_nodes=100 0
for p in [ 0.1, 0.2, 0.3]:
g = watts_strogatz_ graph(no_nodes, 4, p)
print density(g), average_cluster ing(g)

be warned that drawing large random graphs are not overly insightful

check the examples

[bearophileHUGS]

di********@gmai l.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