CODEWITHSUNDEEP
pythongraphnetworkx
flyingmeatball
flyingmeatball

Reputation: 7997

Networkx has_edge for undirected graph only count once

I have the following graph:

full_graph = nx.Graph()

tgt_nodes = ['B','F']

full_graph.add_edge('A','B')
full_graph.add_edge('B','C')
full_graph.add_edge('B','D')
full_graph.add_edge('B','E')
full_graph.add_edge('E','F')

#display and save as img
p = nx.drawing.nx_pydot.to_pydot(full_graph)
p.layout = 'spring'

#p.write_png(outputDir+ version+ '//' + 'cluster_no' + str(clusterNo) + '.png')
display.Image(p.create_png())

enter image description here

I'm trying to find all nodes that are exactly two connections apart, and do things with them depending on the weight.

out_graph = nx.Graph()

for curr_node in tgt_nodes:

        #find all paths for curr_node that are <=2
        pot_paths = nx.single_source_dijkstra_path_length(full_graph, curr_node,2)
        print(pot_paths)

        #iterate over all potential paths. If length ==2 either increment weight or add with weight = 1
        for pot_node, dist in pot_paths.items():

            if dist == 2:
                print(pot_node)

                if out_graph.has_edge(curr_node, pot_node):

                    # we added this one before, just increase the weight by one. NEED TO LIMIT SO THAT THIS DOESN't TRIGGER ON INVERSES
                    out_graph[curr_node][pot_node]['weight'] += 1
                    print('incremented edge for '+ curr_node)
                else:
                    # new edge. add with weight=1
                    out_graph.add_edge(curr_node, pot_node, weight=1)
                    print('added edge for '+ pot_node)

This should only be triggering one time - in the comparison of B >F, it should add an edge. When it get's to F>B, I don't want it to increment, because it's the exact inverse. Here are my results:

>> {'B': 0, 'A': 1, 'C': 1, 'D': 1, 'F': 2, 'E': 1}
>> F
>> added edge for F
>> {'F': 0, 'B': 2, 'E': 1}
>> B
>> incremented edge for F

out_graph.edges(data = True)

>> EdgeDataView([('F', 'B', {'weight': 2})])

How can I modify so (F,B) and (B,F) over the same intermediary node counts once, not twice?

Thanks!

EDIT

Actually, here is an example that doesn't work:

full_graph = nx.Graph()

tgt_nodes = ['B','F']

full_graph.add_edge('A','B')
full_graph.add_edge('B','C')
full_graph.add_edge('B','D')
full_graph.add_edge('B','E')
full_graph.add_edge('E','F')
full_graph.add_edge('G','F')
full_graph.add_edge('B','G')
full_graph.add_edge('F','H')
full_graph.add_edge('B','H')


#display and save as img
p = nx.drawing.nx_pydot.to_pydot(full_graph)
p.layout = 'spring'

#p.write_png(outputDir+ version+ '//' + 'cluster_no' + str(clusterNo) + '.png')
display.Image(p.create_png())

It outputs an edge of 2, when it should be 3 (B & F are connected over G,E, and H)

Upvotes: 1

Views: 925

Answers (3)

flyingmeatball
flyingmeatball

Reputation: 7997

Per @Energya's request - here is the simple code that works:

out_graph = nx.bipartite.weighted_projected_graph(full_graph, ['B','F'])

Upvotes: 1

Joel
Joel

Reputation: 23827

So yes, if G is undirected, then G.has_edge(a,b) and G.has_edge(b,a) are both True if the edge exists and False if the edge doesn't.

So given the way your code is set up, you'll look at each pair of nodes twice and perform the same calculation twice.

How about adding one more condition: if G.has_edge(a,b) and a<b: (if you are doing this in a case where you could have a self-edge, you might think about a<=b).

Then one of the two times it will ignore the calculations. As long as the nodes have a comparison operation defined, it will work. So 'A'<1 won't work, but 'A'<'B' returns True.

A warning I should give is that this only works if you're guaranteed to see each edge in both directions, that is, if both nodes appear in your list tgt_nodes. If only the "bigger" node appears, then it won't count it. So you may need to refine your test for this.

Upvotes: 3

Energya
Energya

Reputation: 2673

You determine the path length based on full_graph, yet add the edges to out_graph. After adding the (B,F) edge to out_graph, it still doesn't exist in full_graph. After all, your out_graph is initialized to be empty. This is also why your out_graph at the end contains only the one edge (B,F).

If your goal is to update the original, you should initialize out_graph to be a copy of full_graph and do all your computations on that. Depending on your needs, networkx's built-in out_graph = full_graph.copy() might do the trick, otherwise you should look into Python's copy.deepcopy().

Upvotes: 0

Related Questions