pygraph.algorithms.generators.generate creates too many edges for non-directed random graphs

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Run the following code:

from pygraph.algorithms.generators import generate
gr = generate(10, 10, False)
print len(gr.edges())  # prints 20 instead of the expected 10

What is the expected output? What do you see instead?
The function creates twice as many edges as needed for non-directed graphs.

What version of the product are you using? On what operating system?
python-graph-core 1.6.3

Original issue reported on code.google.com by wanderin...@gmail.com on 21 Mar 2010 at 1:57

[GoogleCodeExporter]

That's actually the expected behaviour. In a graph, an (non-directed) edge is
represented by two directed edges. So, if you have an edge (x, y) connecting 
nodes x
and y, gr.edges() will return both (x, y) and (y, x).

This means that the number of elements in gr.edges() output will be twice as the
number of edges in the graph. This allows us to have generic algorithms that 
work
both on graphs and digraphs, without modification.

I hope it's clearer for you now.

Original comment by pmatiello on 21 Mar 2010 at 5:44

• Changed state: Invalid

[GoogleCodeExporter]

Thanks pmatiello for the clarification.  I didn't see any note about this in the
documentation.  This should probably be added to the web-based documentation. 
Similarly, users might expect that adding one edge to an undirected graph would 
mean
that the number of edges is only increased by 1.  Like you said, it is in fact
increased by two.  Here's an example of how someone might get confused:

from pygraph.classes.graph import graph

# create a graph
grB = graph()
grB.add_node(1)
grB.add_node(2)

# adding 1 edge, actually adds 2 edges
edgeCountBefore = len(grB.edges())
print str(edgeCountBefore) + " edges" # prints "0 edges"

edge = (1,2) # create 1 edge
grB.add_edge(edge) # add 1 edge
edgeCountAfter = len(grB.edges())
print str(edgeCountAfter) + " edges" # prints "2 edges", but I only added 1 edge

Original comment by wanderin...@gmail.com on 22 Mar 2010 at 5:03