Why does nx.dfs_edges() give different results for essentially the same graphs?

37 views
Skip to first unread message

Peng Yu

unread,
Sep 22, 2018, 2:49:21 PM9/22/18
to networkx-discuss
The results of dfs_edges() on G1 and G2 are different. But G1 and G2 are essentially the same. Should dfs_edges() give the same number of edges on both graphs?

$ cat main.py
#!/usr/bin/env python

import networkx as nx

G1=nx.DiGraph()
G1.add_path(['a', 'b'])
G1.add_path(['c', 'd', 'e'])
G1.add_path(['f', 'g', 'h', 'i'])
G1.add_path(['j', 'k', 'l', 'm', 'n'])

for e in nx.dfs_edges(G1):
    print 'G1', '\t'.join(e)

G2=nx.DiGraph()
G2.add_path(reversed(['a', 'b']))
G2.add_path(reversed(['c', 'd', 'e']))
G2.add_path(reversed(['f', 'g', 'h', 'i']))
G2.add_path(reversed(['j', 'k', 'l', 'm', 'n']))

for e in nx.dfs_edges(G2):
    print 'G2', '\t'.join(e)
$ ./main.py
G1 a    b
G1 c    d
G1 d    e
G1 g    h
G1 h    i
G1 k    l
G1 l    m
G1 m    n
G2 e    d
G2 g    f
G2 i    h
G2 k    j
G2 m    l

Dan Schult

unread,
Sep 22, 2018, 4:59:30 PM9/22/18
to networkx...@googlegroups.com
I can't reproduce this result in python 2.7 or 3.6.
It seems to work fine.  What version nx? python?

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

Peng Yu

unread,
Sep 22, 2018, 5:07:52 PM9/22/18
to networkx-discuss
Here you are. What is your output of my test case?

$ python
Python 2.7.15 (v2.7.15:ca079a3ea3, Apr 29 2018, 20:59:26)
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import networkx
>>> print networkx.__version__
2.2
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.

Dan Schult

unread,
Sep 22, 2018, 5:37:03 PM9/22/18
to networkx...@googlegroups.com
Ahh.. I think there is a bug.  It depends on the order the nodes get used as roots for dfs.
So if the order of the nodes is OK you don't see the bug. But if you start, eg with a node
that has no outgoing edges like 'a', that node gets marked as "visited". Then (when source is 
not specified) the tree is searched for the root 'b' and the edge ('b','a') is checked, but 'a' is 
marked as "visited" so that edge is incorrectly not reported.

Please add this as an Issue on the github page (or I will eventually). 
Thanks!

Temporary workarounds include 
- switching to Python 3.6 -- works for most cases because 3.6 dicts are ordered... but the bug is still there. not sure if it could rise up.
- calling repeatedly with "source" identified.

visited = set([])
dfse = []
for node in G:
    if node in visited:
        continue
    new_edges = list(nx.dfs_edge(G, source=node))
    for e in new_edges:
        visited.update(e) .  # note: this doesn't mark the source node unless an edge is produced
    dfse.extend(new_edges)

print(dfse)


Thanks for reporting this!

Peng Yu

unread,
Sep 22, 2018, 6:04:11 PM9/22/18
to networkx...@googlegroups.com
The walkaround seems still buggy (for both python2 and python3). See below.

$ cat ./main.py
#!/usr/bin/env python
# vim: set noexpandtab tabstop=2 shiftwidth=2 softtabstop=-1 fileencoding=utf-8:

import sys
import networkx as nx
G = nx.DiGraph()

for line in sys.stdin:
array = line.rstrip('\n').split('\t')
G.add_edge(array[1], array[0])

def dfs_edges(G):
visited = set([])
dfse = []
for node in G:
if node in visited:
continue
new_edges = list(nx.dfs_edges(G, source=node))
for e in new_edges:
visited.update(e)
dfse.extend(new_edges)

return dfse

for e in nx.dfs_edges(G):
print(e)
$ ./main.sh # use python2
function cmd {
cat <<-EOF
a b
c d e
f g h i
j k l m n
A B
C D E
F G H I
J K L M N
EOF
}

cmd | awk -e 'NF>1 { for(i=1;i<NF;++i) { print $i, $(i+1) } }' | ./main.py
('E', 'D')
('G', 'F')
('I', 'H')
('K', 'J')
('M', 'L')
('e', 'd')
('g', 'f')
('i', 'h')
('k', 'j')
('m', 'l')
$ ./main.sh # use python3
function cmd {
cat <<-EOF
a b
c d e
f g h i
j k l m n
A B
C D E
F G H I
J K L M N
EOF
}

cmd | awk.sh -e 'NF>1 { for(i=1;i<NF;++i) { print $i, $(i+1) } }' | ./main.py
('b', 'a')
('d', 'c')
('g', 'f')
('k', 'j')
('B', 'A')
('D', 'C')
('G', 'F')
('K', 'J')
> --
> You received this message because you are subscribed to a topic in the
> Google Groups "networkx-discuss" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/networkx-discuss/v-LrYjkPKaI/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> networkx-discu...@googlegroups.com.
> To post to this group, send email to networkx...@googlegroups.com.
> Visit this group at https://groups.google.com/group/networkx-discuss.
> For more options, visit https://groups.google.com/d/optout.



--
Regards,
Peng

Dan Schult

unread,
Sep 22, 2018, 8:10:50 PM9/22/18
to networkx...@googlegroups.com
I think you aren't getting all the edges you want -- only the first two nodes from each line are added...?  (nodes using array[0] and array[1])


> networkx-discuss+unsubscribe@googlegroups.com.
> To post to this group, send email to networkx-discuss@googlegroups.com.

> Visit this group at https://groups.google.com/group/networkx-discuss.
> For more options, visit https://groups.google.com/d/optout.



--
Regards,
Peng

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.

Peng Yu

unread,
Sep 22, 2018, 8:22:43 PM9/22/18
to networkx...@googlegroups.com
No. I used awk to get all the edges.

> networkx-discu...@googlegroups.com.
> To post to this group, send email to networkx...@googlegroups.com.



--
Regards,
Peng

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.

To post to this group, send email to networkx...@googlegroups.com.

--
You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/v-LrYjkPKaI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
--
Regards,
Peng

Dan Schult

unread,
Sep 22, 2018, 10:24:11 PM9/22/18
to networkx...@googlegroups.com
You are right that the workaround isn't reliable. 
I seem to be able to mess with it and get it better, but it still breaks in some cases.
In particular, by starting at each of the nodes in turn, sometimes you start in the middle of, say, a path.
Later you start at the beginning of the path and you repeat all the edges you already saw. 
We could make it not report those edges again, but then what order are you expecting?

I'm beginning to think that we should require a source to be provided for DiGraphs.
Other suggestions?






--
Regards,
Peng

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.

To post to this group, send email to networkx-discuss@googlegroups.com.

--
You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/v-LrYjkPKaI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.
--
Regards,
Peng

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.

Peng Yu

unread,
Sep 22, 2018, 10:33:52 PM9/22/18
to networkx...@googlegroups.com
For my special cases, the graph is a forest and I just need to find the path of each node to its root given all the edges. So I end up with a simple code without using networks, as networkx seems to be an overkill for this specific problem. I don't know how to fix the bug in networkx in general.

> networkx-discu...@googlegroups.com.
> To post to this group, send email to networkx...@googlegroups.com.



--
Regards,
Peng

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.

To post to this group, send email to networkx...@googlegroups.com.

--
You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/v-LrYjkPKaI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
--
Regards,
Peng

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.

--
You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/v-LrYjkPKaI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
--
Regards,
Peng
Reply all
Reply to author
Forward
0 new messages