djhenderson / python-graph Goto Github PK

Would it be possible to make pydot be an optional requirement so that those
who won't be interacting with Graphviz don't need it?

Quite often there is problem to view or debug created graph visually. It
would be nice to get simple rendering/plotting capability inside of graph
package.

Looking over the source code, it is obvious that people are using DAGs a lot. 
It might be nice to 
have an explicit class that make sure the graph is acyclic, and raised an error 
if an edge was 
added that created a cycle. I attach a patch that provides a simple subclass of 
digraph, with two 
test cases. 

The subclass uses breadth_first_search with the child node as the root to find 
if the new edge 
would create a circle. This is obviously non-optimal for large graphs; however, 
the alternative (as 
well as I can understand) would be to maintain a complicated series of caching, 
or perhaps to 
create a separate iterable breadth-first search that ends when a condition is 
met. Probably you 
can do the second option already, but the patch attached is OK for my needs for 
now. I don't 
know if there is a difference between breadth and depth-first in this case, and 
chose breadth 
first arbitrarily.

I tried to follow the library coding style; if you have any critiques or 
opportunities for 
improvement, please let me know. I am only a beginning programmer, so please 
forgive any 
stupid mistakes.

The new packages are not listed in the Python Package Index
(http://pypi.python.org/pypi). Removing the old package breaks packages
that had it listed as a dependency.

What steps will reproduce the problem?
1. Make SVN Check Out
2. Go to Project Directory
3. Run Setup.py

What is the expected output? What do you see instead?

Traceback (most recent call last):
  File "C:\Other\python-graph-read-only\setup.py", line 12, in <module>
    docfiles = os.listdir('docs')
WindowsError: [Error 3] The system cannot find the path specified: 
'docs/*.*'


What version of the product are you using? On what operating system?
Python 2.5
OS: Win XP SP3

What steps will reproduce the problem?
1. Use generate() to create a new graph. All edges will be initialized with
 default weight 1.0
2. Try to create a more "interesting" graph from the above by assigning
random weight to existing links.
3. To do so you need to know the internal representation of the graph,
which defeats the purpose of the nice graph class

What is the expected output? What do you see instead?

- expected to see a set_weight((n1, n2), weight) method (or similar).

What version of the product are you using? On what operating system?

- 1.0/1.1(HEAD), Linux

Please provide any additional information below.

Would be nice to have a more extended generate() with optional weight
envelope as argument. Use of a uniformly distributed random number would be
adequate. The signature may be. (I can write this tomorrow, if you want,
and submit it.)

Contributed by Dave Bowman <[email protected]>.

What steps will reproduce the problem?
1. Unzip python-graph-1.6.2.zip
2. cd to .\python-graph-1.6.2 
3. type 'easy_install'

What is the expected output? What do you see instead?
  Expect installation of the package.
  Instead get error message:
"[I:\_498.22=INCOMMON_DLOADS\PYTHON_DLOADS]easy_install python-graph
Retrieved config from: C:\Documents and Settings\Administrator\enstaller.ini
Searching for python-graph
Reading http://pypi.python.org/simple/python-graph/
Reading http://code.google.com/p/python-graph/
Reading http://code.google.com/p/python-graph/downloads/list
Best match: python-graph 1.6.2
Downloading http://python-graph.googlecode.com/files/python-graph-1.6.2.zip
Processing python-graph-1.6.2.zip
error: Couldn't find a setup script in
c:\docume~1\admini~1\locals~1\temp\easy_install-zxdygz\python-graph-1.6.2.zip"

What version of the product are you using? On what operating system?
python-graph-1.6.2 on python 2.5 on a Windows XP platform with lots of
previously loaded packages in f:\python25\lib\site-packages.

Please provide any additional information below.
 Also tried to run setup.py files from the \core and \dot subdirectories.   
 Error messages indicated 'NameError: name 'ssl' is not defined'
 e.g. 
"[I:\_498.22=INCOMMON_DLOADS\PYTHON_DLOADS\python-graph-1.6.2\core]setup.py
install
Traceback (most recent call last):
  File
"I:\_498.22=INCOMMON_DLOADS\PYTHON_DLOADS\python-graph-1.6.2\core\setup.py", 
line
11, in <module>
    ez_setup.use_setuptools()
  File
"I:\_498.22=INCOMMON_DLOADS\PYTHON_DLOADS\python-graph-1.6.2\core\ez_setup\__ini
t__.py",
line 95, in use_setuptools
    return do_download()
  File
"I:\_498.22=INCOMMON_DLOADS\PYTHON_DLOADS\python-graph-1.6.2\core\ez_setup\__ini
t__.py",
line 89, in do_download
    egg = download_setuptools(version, download_base, to_dir, download_delay)
  File
"I:\_498.22=INCOMMON_DLOADS\PYTHON_DLOADS\python-graph-1.6.2\core\ez_setup\__ini
t__.py",
line 124, in download_setupto
ols
    import urllib2, shutil
  File "F:\python25\lib\urllib2.py", line 92, in <module>
    import httplib
  File "F:\python25\lib\httplib.py", line 71, in <module>
    import socket
  File "F:\python25\lib\socket.py", line 70, in <module>
    _realssl = ssl
NameError: name 'ssl' is not defined
"

What steps will reproduce the problem?
1. Execute this code: http://pastebin.ca/1336228

What is the expected output? What do you see instead?
digraph.find_cycle() should return a list, and should not throw an exception.
Here is the exception w/ stack trace: http://pastebin.ca/1336229

What version of the product are you using? On what operating system?
Latest stable python-graph, Python 2.6.1, Windows Vista

Implemented and tested (albeit briefly) using the references in the
comments.  Please feel free to email me with any questions.  I believe this
code should reside in minmax.py.

Contributed by Johannes Reinhardt <[email protected]>.

What steps will reproduce the problem?
1. Fedora 11
2. python setup.py bdist_rpm

What is the expected output? What do you see instead?

Expects rpm to be found in dist/

BUT it fails.

Adding 
COPYING
Changelog
to python_graph.egg-info/SOURCES.txt makes it work correctly.

Alternatively they can be removed from datafiles in setup.py.


What version of the product are you using? On what operating system?

python-graph-1.6.1.tar.bz2 on Fedora 11

Python 2.6.2,
easy_install python-graph

# Graph creation
gr = pygraph.digraph()

# Add nodes and edges

gr.add_nodes( [ "1", "2", "3" ] );
gr.add_edge( "1", "2" )
gr.add_edge( "2", "3" )

trs = transitive_edges( gr )
print trs

I would expect to see the edge "1" "3" printed, instead, I get an empty list 
"[]".

I also added a call to transitive_edges to ex1.py after changing

gr = pygraph.graph()

to

gr = pygraph.digraph()

...
At the bottom of the file:

trs = transitive_edges( gr )
for tr in trs:
   print tr

...

output

('Switzerland', 'Germany')
('Switzerland', 'Italy')
('Switzerland', 'Germany')
('Switzerland', 'Germany')
('Switzerland', 'Italy')
('Austria', 'Slovakia')
('Austria', 'Germany')
('Austria', 'Hungary')
('Poland', 'Slovakia')
('Poland', 'Germany')
('England', 'Wales')
('France', 'Belgium')
('Germany', 'Netherlands')

Note that this does not produce an edge between Portugal and France, which you 
would expect 
since there is an edge from Portugal to Spain and an edge from Spain to France.

Adding Bellman-Ford algorithm (shortest path family) to the algorithms
package. 

Quote:
The Bellman–Ford algorithm, a label correcting algorithm,[1] computes
single-source shortest paths in a weighted digraph (where some of the edge
weights may be negative). 
http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

digraph.add_graph function fails as follows:

Traceback (most recent call last):
  File "/home/sal/workspace/python-graph/tests/unittests-digraph.py", line
195, in test_add_graph_into_diagraph
    d.add_graph( g )
  File "/home/sal/workspace/python-graph/core/pygraph/classes/digraph.py",
line 484, in add_graph
    self.add_edge(each_node, each_edge)
  File "/home/sal/workspace/python-graph/core/pygraph/classes/digraph.py",
line 222, in add_edge
    if (v not in self.node_neighbors[u] and self.node_neighbors[v] is not
None):
KeyError: 'B'


    def test_add_graph_into_diagraph(self):
        d = digraph()
        g = graph()

        A = "A"
        B = "B"

        g.add_node( A )
        g.add_node( B )
        g.add_edge( A,B )

        d.add_graph( g )

        assert d.has_node( A )
        assert d.has_node( B )
        assert d.has_edge( A,B )
        assert d.has_edge( B,A )  

What steps will reproduce the problem?
1. Install on a win32 platform.
2. Attempt to run one of the examples.
3.

What is the expected output? What do you see instead?
When I run one of the examples it appears to be missing the 'filters' package.

What version of the product are you using? On what operating system?
1.4.0 on Win32 but it happens on Linux if installed from source as well.

Please provide any additional information below.

I changed setup.py to include graph.algorithms.filters in the packages
parameter and it appears to fix that problem.

Markup and dot read/write need associated hypergraph tests.

I find requiring pydot is an unfavorable development, as it requires
further inclusion of pyparsing and Graphviz.  This tight coupling should
not be required, but should be an optional extension.  These requirements
may prevent me from using the graph library in some applications.

Related to issue 16, DIMACS graph formats are a well accepted standard and
adapters should be written for them as well.

What steps will reproduce the problem?
1. build python-graph
2. setup python-graph
3. run example (draw.py for example)

What is the expected output? What do you see instead?
Expected anything else than: ImportError: No module named gv

What version of the product are you using? On what operating system?
Latest now, Windows XP

Please provide any additional information below.

A setuptools setup.py script would be nice. Really, it would just be nice
to use easy_install.

please add also import of  .dot files.

DOT format is better than XML for giving the graph.

There is no testing for this file.

There seems to be a serious lack of testing for the functions in this file.
At the time of filing, the only two tests seem to be:

- test_mutual_accessibility_in_digraph
- test_connected_components_hypergraph

I have installed python-graph with easy_install (easy_install python-graph)

In the tutorial (http://code.google.com/p/python-graph/wiki/Example) you
say to import a module called 'gv'.

This module is not installed in my system, and wasn't installed by
easy_install.
Is it graphviz? This one: http://www.graphviz.org ?
How do I install it? 
You are using a python api to graphviz - but which one? Where do I install
them?

The SVN version of the program is producing double edges for undirected
graphs when writing to a dot file or the such. The attached patch fixes
that by checking to see if an edge has already been added to dotG before
adding it.

Thanks a bunch.

PS: please tell me if I'm doing something wrong... I'm a long-time user of
free/open source software, but I'm new to contributing...

Purpose of code changes on this branch:
- added 2 new algorithms

When reviewing my code changes, please focus on:
- 2 new functions need some testing:
* digraph.critical_path
* digraph.transitive_edges

- see examples/ex_critical.py for a simple dev example

Purpose of code changes on this branch:
  To generalize the behaviour / use of edges.

When reviewing my code changes, please focus on:
  The general classes added by the last merge and how they're used in the
various parts of the code.

After the review, I'll merge this branch into:
/trunk

The graph class has a a method that gives the shortest distance between one
point and all other points in the graph, however is there an efficient
method which will give the shortest distance between any two paths?

Thanks

Graph.add_node currently performs the following check:
    if (not node in self.node_neighbors.keys()):

This causes a list containing the keys of node_neighbors to be created
every time the function is called, resulting in O(n) time-complexity (where
n is the number of nodes in the graph).  Adding n nodes (to an empty graph)
is then O(n^2).  For large graphs, this is prohibitively expensive.

Fortunately, there is a solution -- don't call keys()!!!  In other words,
    if (not node in self.node_neighbors):
accomplishes the exact same thing with the benefit of being approximately O(1).

I'm attaching a diff that implements the proposed changes.  The diff is
against SVN revision 236.

What steps will reproduce the problem?
1. I use IPython, here is the dump

In [3]: a = graph.digraph()

In [4]: a.addedge(1,2)

In [6]: a.add_node(1)

In [7]: a.add_node(2)

In [8]: a.add_edge(1, 2)

In [9]: a.del_node(1)

In [11]: print a.get_edges()
>> [(1, 2)]

What is the expected output? What do you see instead?

The edges list should be empty. The reason is that del_node (in
__init__.py) didn't handle the outgoing links properly by deleting it from
edges list. 

I would suggest a clear way to write the code as:


----------

    def del_node(self, node):
        """
        Remove a node from the graph.

        @type  node: node
        @param node: Node identifier.
        """
        # Remove the incoming link
        for each in list(self.get_incidents(node)):
            self.nodes[each].remove(node)
            del(self.edges[(each, node)])

        # Remove the outgoing link
        for each in self.nodes[node]:
            self.incidence[each].remove(node)
            del(self.edges[(node, each)])

        del(self.nodes[node])
        del(self.incidence[node])
        del(self.node_attr[node])
---------------------

It would be nice to have a way to test graph's connectivity :
 - weakly connected
 - strongly connected
 - ...
http://en.wikipedia.org/wiki/Connectivity_(graph_theory)

If it is already possible with existing functions, could you please
document an example on the wiki ?

What steps will reproduce the problem?
1. import graph
2. gr=graph.graph()
3. gr.add_node(u"aéùi")
4. gr.write(fmt='dot')

What is the expected output? What do you see instead?
No output but UnicodeEncodeError traceback.

What version of the product are you using? On what operating system?
1.3.1 on arch linux

Please provide any additional information below.
Not being a unicode guru I may be wrong, but
http://code.activestate.com/recipes/466341/ may help (or do some sort of
conversion to only store unicode inside) ? 

The 'dotwt' format isn't producing edge weight information. This can be
fixed by adding:

if wt:
    attrlist += [('label',graph.get_edge_weight(u, v))]

after:

attrlist = graph.get_edge_attributes(u, v) +
[('label',graph.get_edge_label(u, v))]

on line 193 of 'graph/classes/readwrite.py'

What steps will reproduce the problem?
1. python setup.py install --prefix=$HOME

What is the expected output? What do you see instead?
Expecting install to happen with no failures.  Instead, I get this failure:
error: could not create '/usr/share/doc/python-graph-1.1.1': Permission denied

What version of the product are you using? On what operating system?
python-graph-1.1.1
sysname = x86-64_linux_2.6.5_ImageSLES9SP3-3

Please provide any additional information below.
This is fantastic software, btw.  I work for Intel, and I am using it to
profile and document state machines in SystemVerilog.

I have never dealt with dist-tools before, but I suspect that when you
specify --prefix, the script should copy the documents to the $PREFIX/share
area.  Otherwise you will get this kind of problem with users who don't
have root privilege.

  Modular decomposition refers to the process of building a modular 
decomposition tree. These can yield very interesting properties about 
graphs (directed, undirected, and hypergraphs alike). More info can be 
found here:

http://en.wikipedia.org/wiki/Modular_decomposition

  In short, a 'module' is a set of nodes M that is indistinguishable from 
the rest of the graph (call it N\M), where indistinguishable indicates that 
if an edge exists from u in N\M to some node v in M, then an edge /must/ 
exist from u to all nodes in M. The intuition behind this is that if you 
only had the information of what the nodes inside M were connected to 
outside of M, you wouldn't see any difference between them.

  An important notion that surrounds this is a Co-graph (we'll consider 
only undirected graphs for now). It's definition is recursive:
- A single node is a cograph.
- The complement of a cograph is a cograph.
- The union of two cographs is a cograph, where the union of graphs G1 and 
G2, G1_G2 is defined as N(G1_G2) = N(G1) + N(G2) and E(G1_G2) = E(G1) + 
E(G2)

  A modular decomposition tree (MDT) is a (unique) representation of a 
graph. The tree has three types of nodes -- series, parallel, and prime. 
The children of each node represent modules. Children of parallel nodes 
have 0 edges between them. Children of series nodes have all edges between 
them. Children of prime nodes have edges between them as defined by a 
'prime graph' associated with the prime node parent. (* while this may 
sound complicated, pictures make things loads easier, and a better 
explanation is attached *)

  Some other things to note / motivate:
- Any graph has a unique modular decomposition tree.
- Many graph algorithms are simple on cographs.
- If a graph's MDT has only series / parallel nodes, then it is a cograph.

  I propose to implement:
- A recently published approach for a linear time modular decomp of 
undirected graphs.
- A divide-and-conquer algorithm algorithm (I think n log n) for directed 
graphs that is conceptually easy.
- An n^2 algorithm for hypergraphs that is currently the best known 
approach.

  Attached is a flash video explaining the linear time MD of undirected 
graphs.

What steps will reproduce the problem?

import graph
test_graph = graph.digraph()
test_graph.add_node('1')
test_graph.add_node('2')
test_graph.add_node('3')
test_graph.add_node('4')
test_graph.add_edge('1','2')
test_graph.add_edge('2','3')
test_graph.add_edge('2','4')
heur = graph.heuristics.euclidean()
heur.optimize(test_graph)

Causes error!

Traceback (most recent call last):
  File "<pyshell#129>", line 1, in <module>
    heur.optimize(test_graph)
  File "build\bdist.win32\egg\graph\algorithms\heuristics\Euclidean.py",
line 63, in optimize
    for i in xrange(len(start_attr)):
UnboundLocalError: local variable 'start_attr' referenced before assignment

What version of the product are you using? On what operating system?

Problem occurs on python 2.5 and 2.6
Using python-graph 1.4.1

Please provide any additional information below.

It is not possible to use attributes in edges
(http://www.graphviz.org/doc/info/attrs.html).

GvGen solves this with

graph.propertyAppend(postman, "color", "red")

I whink that for python-graph it would be nice to have:

add_edge(self, u, v, wt=1, attributes=None)

where attributes could be a list of tuples like [("color", "red"),
("penwidth", 4), ...]

I was just about to roll out my own code for handling graphs when I came
upon this.

Any chance of getting hypergraph support? At least for representation? Thanks

None currently exist.

This is a bit nit-picky, but the correct spelling is 'neighbor', without
the 'u'.

"for each in hyperedges:" SHOULD BE "for each in self.hyperedges():"

right?

accessibility
(Move to accessibility.py as accessibility_hypergraph)

connected_components
(Move to accessibility.py as connected_components_hypergraph)

cut_hyperedges
(Move to accessibility.py)

cut_nodes
(Move to accessibility.py as cut_hypernodes)

What steps will reproduce the problem?

>>> g = pygraph.digraph()
>>> [g.add_node(x) for x in range(5)]
[None, None, None, None, None]
>>> g.add_edge(1, 2)
>>> g.add_edge(1, 3)
>>> g.add_edge(2, 3)
>>> g.add_edge(3, 4)

# A thinko
>>> g.add_edge(2, 5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/classes/Digraph.py", line 221, in add_edge
KeyError: 5

# Correct behaviour (reject adding an edge to a nonexistant node) so far, 
buuuuut...

>>> g.add_edge(1, 0)

>>> list(g.traversal(1))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/classes/Digraph.py", line 508, in traversal
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 60, in traversal
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 82, in _dfs
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 82, in _dfs
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 80, in _dfs
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/classes/Digraph.py", line 103, in __getitem__
KeyError: 5

The graph should know nothing about node 5 nor about the edge I accidentally 
tried to add.

What version of the product are you using? On what operating system?

pygraph-1.6.1 from pypi on Python 2.6

Few things should happen here.

- cut_nodes / cut_edges for graphs / digraphs should have the docstrings 
updated to fully describe what it is that the method does.
- The methods themselves should be documented to explain what's going on / 
how (at least at a high level).
- Testing must be done (related to issue 44).
- Hypergraph equivalents need to be examined for validity.

[deleted issue]

What steps will reproduce the problem?
1. Create the following graph:
    <node id="1"/>
    <node id="2"/>
    <node id="3"/>
    <edge from="1" label="M1" to="2" wt="277317"/>
    <edge from="3" label="M6" to="2" wt="112344"/>
    <edge from="1" label="M3" to="3" wt="478726"/>
    <edge from="3" label="M4" to="1" wt="930382"/>
    <edge from="2" label="M2" to="1" wt="26247"/>
    <edge from="2" label="M5" to="3" wt="370287"/>
2. Run minimal_spanning_tree () on it

What is the expected output? What do you see instead?
This is what we get:
    <node id="1"/>
    <node id="2"/>
    <node id="3"/>
    <edge from="2" label="" to="3" wt="1"/>
    <edge from="2" label="" to="1" wt="1"/>

Original weights are lost! Plus this is not really the MST for the above graph!

What version of the product are you using? On what operating system?
python_graph-1.4.2 on Python 2.5.1

What steps will reproduce the problem?
1. have any graph gr with nodes as integers and one of the node is 0
2. call gr.minimal_spanning_tree(0), for example, and unexpected
   result is produced

What is the expected output? What do you see instead?

I expect to see a spanning tree with node 0 being its root.
Instead, it provides result as if root was not given at all

What version of the product are you using? On what operating system?

version 1.0.0 on Linux

Please provide any additional information below.

The problem seems rather systemic: in many places in the code the node
value is tested as a bool value, e.g.:

    if (node):
        ...

In Python this expression cannot distinguish between node=0 (which may be a
legitimate node) and node=None (which in many places in the code is used to
denote an invalid node). The proper coding requires explicit test against
None, e.g., 

    if node is not None:
        ...

A patch fixing this in a very few places is attached for convenience, but i
have only tested what I was using.

Please note that the generate() method does create graphs with node==0
always included, so the bug described here should come up in every run of
minimal_spanning_tree() made on graphs obtained via generate().

What steps will reproduce the problem?
1. Click on the external link (epydoc documentation), you get an apache 
forbidden access to a 
website.

I think one way to solve this would be to put the generated apidoc inside 
subversion, and set the 
svn properties of files to HTML. They will be served normally by google (but 
you should probably 
test it before ;)

- Benjamin

Purpose of code changes on this branch:
 * A demo of an alternative implementation of digraph intended to be more
scalable. This is mainly intended for discussion, rather than immediate
inclusion.
 * Some changes to Christian's digraph interface to make it work with
Python 3.x (spesifically removal of the argument unpacking on edge methods)
 * Removal of the "attrs" feature
 * A new way of doing labeling where labels are merely extra properties on
a dict representing neighbours of an object.

When reviewing my code changes, please focus on:

 * Consistency with our existing API
 * Scalability to very large orders.

This code is intended for inclusion in /trunk after the next release, or
possibly after that.