pythongraphnodesnetworkxedges

How to detect redundant edge in graph networkx python?


I have a question, how can I detect and get the redundant value from graph connection? i already set the redundant graph connection in add_edges_from() like (1,2) and (1,2). But when i print list of edges, it only detected as 1 connection. Here is my example:

test_graph = nx.Graph()
test_graph.add_edges_from([(1, 2), (1, 2), (1, 3), (1, 4), (3, 4), (4, 5), (5,6), (6,7), (7,8), (6,8)])

posxx = nx.spring_layout(test_graph, scale = 1, k = 2 / np.sqrt(test_graph.order())) #planar -> no intersect
nx.draw(test_graph, posxx, node_color='red', font_size = 10, node_size = 350, with_labels=True)

list(test_graph.edges)

enter image description here

Output :

[(1, 2), (1, 3), (1, 4), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8)]

I want those redundant connection have output like integer number. Such as if i have (1,2),(1,2),(1,2), it is detected as 3 in edge value. Anyone have solution?


Solution

  • Graphs with what you call "redundant" edges are typically called multigraphs. In networkx, you can either (1) use the MultiGraph class to keep track of all edges individually, or (2) you can count the edges and then create a weighted Graph.

    #!/usr/bin/env python
    
    import matplotlib.pyplot as plt
    import networkx as nx
    
    from collections import Counter
    
    edges = [
        (1, 2), (1, 2),
        (1, 3),
        (1, 4),
        (3, 4),
        (4, 5),
        (5, 6),
        (6, 7),
        (6, 8),
        (7, 8),
    ]
    
    # option 1: MultiGraph
    g = nx.MultiGraph(edges)
    print(g.edges)
     # MultiEdgeDataView([(1, 2), (1, 2), (1, 3), (1, 4), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8)])
    
    # option 2: weighted Graph
    edge_to_count = Counter(edges)
    weighted_edges = [(source, target, {'weight' : count}) for (source, target), count in edge_to_count.items()]
    g = nx.Graph(weighted_edges)
    
    print(g.edges())
    # EdgeView([(1, 2), (1, 3), (1, 4), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8)])
    
    g.get_edge_data(1, 2)
    # {'weight': 2}