bug_matching.py

#!/usr/bin/env python

"""
Test case for a bug in networkx.algorithms.maximal_matching version 1.8.1

It seems that depending on the order of the nodes in the edges ( (a,b) vs (b,a) )
maximal_matching does return different results.
"""

import networkx as nx
from networkx.algorithms import maximal_matching
from itertools import combinations

def test_matching(G):
    matching = maximal_matching(G)

    #verify matching: each node should only appear once in the matching
    incidents = dict((node,0) for node in G.nodes())
    for u,v in matching:
        incidents[u] += 1
        incidents[v] += 1
        
        if not (incidents[u] <= 1 and incidents[v] <= 1):
            return False, matching

    return True, matching


G = nx.Graph(
    [(0, 312), (0, 233), (0, 138), (0, 159), (1, 128), (1, 258), (1, 9), (1, 267), (1, 14), (1, 271), (1, 151), (1, 157), (1, 42), (1, 305), (1, 309), (1, 54), (1, 61), (1, 191), (1, 64), (1, 204), (1, 86), (1, 221), (1, 99), (1, 239), (1, 241), (1, 115), (1, 247), (1, 298), (1, 127), (2, 49), (2, 51), (2, 262), (2, 289), (3, 233), (3, 50), (3, 138), (4, 225), (4, 83), (4, 203), (4, 292), (4, 101), (4, 70), (4, 39), (4, 266), (4, 235), (4, 46), (4, 112), (4, 147), (4, 250), (4, 279), (4, 249), (4, 154), (4, 223), (4, 189), (4, 254), (4, 287), (5, 312), (5, 234), (5, 138), (5, 37), (5, 30), (6, 66), (6, 52), (6, 87), (7, 96), (7, 262), (8, 49), (8, 51), (8, 262), (9, 200), (9, 186), (9, 51), (9, 77), (10, 160), (10, 200), (10, 149), (10, 166), (11, 66), (11, 163), (11, 87), (11, 52), (11, 85), (11, 23), (11, 90), (11, 29), (11, 63), (12, 49), (12, 51), (12, 262), (12, 289), (13, 114), (13, 164), (14, 200), (14, 186), (14, 51), (15, 272), (15, 48), (15, 52), (15, 295), (16, 96), (16, 176), (16, 37), (16, 167), (16, 108), (16, 207), (16, 208), (16, 56), (17, 96), (17, 166), (17, 233), (17, 234), (17, 140), (17, 272), (17, 52), (18, 288), (18, 295), (18, 148), (18, 87), (18, 56), (18, 52), (19, 196), (20, 56), (20, 80), (20, 52), (20, 134), (20, 23), (21, 23), (21, 87), (22, 120), (22, 297), (22, 289), (23, 136), (23, 265), (23, 275), (23, 153), (23, 283), (23, 291), (23, 173), (23, 310), (23, 58), (23, 187), (23, 188), (23, 64), (23, 139), (23, 54), (23, 221), (23, 182), (23, 224), (23, 226), (23, 99), (23, 239), (23, 241), (23, 127), (24, 200), (24, 272), (24, 114), (25, 297), (26, 96), (26, 160), (26, 165), (26, 233), (26, 297), (26, 121), (27, 96), (27, 176), (27, 37), (28, 272), (28, 48), (28, 87), (29, 226), (29, 113), (29, 228), (29, 71), (29, 173), (29, 175), (29, 273), (29, 82), (29, 310), (29, 311), (29, 88), (29, 100), (29, 187), (30, 192), (30, 79), (30, 226), (30, 68), (30, 162), (30, 72), (30, 169), (30, 106), (30, 44), (30, 141), (30, 143), (30, 177), (30, 211), (30, 246), (30, 105), (30, 280), (30, 91), (30, 124), (30, 286), (30, 133), (31, 272), (31, 312), (31, 96), (31, 166), (31, 233), (32, 160), (32, 164), (32, 60), (32, 297), (32, 63), (33, 56), (33, 67), (33, 295), (34, 49), (34, 51), (34, 262), (34, 289), (35, 312), (35, 233), (35, 138), (35, 159), (36, 84), (36, 258), (36, 293), (36, 232), (36, 267), (36, 144), (36, 243), (36, 276), (36, 247), (36, 281), (36, 252), (36, 61), (37, 135), (37, 264), (37, 210), (37, 278), (37, 152), (37, 185), (37, 92), (37, 118), (37, 158), (38, 272), (38, 96), (38, 148), (38, 262), (38, 60), (39, 140), (39, 67), (39, 121), (40, 80), (41, 56), (41, 67), (41, 87), (41, 52), (41, 295), (42, 200), (42, 77), (43, 160), (43, 200), (43, 77), (43, 149), (44, 184), (44, 137), (44, 176), (45, 145), (46, 140), (46, 67), (46, 121), (47, 261), (48, 188), (48, 283), (48, 179), (48, 263), (48, 284), (48, 171), (48, 300), (48, 79), (48, 144), (48, 124), (48, 275), (48, 190), (48, 89), (48, 153), (48, 58), (48, 111), (48, 122), (48, 158), (49, 227), (49, 261), (49, 146), (49, 71), (49, 110), (49, 216), (49, 82), (49, 212), (49, 55), (49, 88), (50, 64), (50, 257), (50, 291), (50, 199), (50, 136), (50, 74), (50, 139), (50, 174), (50, 239), (50, 99), (50, 241), (50, 54), (50, 221), (50, 127), (51, 204), (51, 146), (51, 276), (51, 309), (51, 86), (51, 88), (52, 263), (52, 270), (52, 144), (52, 146), (52, 296), (52, 170), (52, 171), (52, 180), (52, 310), (52, 187), (52, 190), (52, 214), (52, 89), (52, 221), (52, 226), (52, 236), (52, 119), (52, 251), (53, 100), (53, 260), (54, 148), (55, 262), (55, 289), (56, 133), (56, 109), (56, 274), (56, 150), (56, 280), (56, 162), (56, 177), (56, 68), (56, 72), (56, 73), (56, 79), (56, 214), (56, 169), (56, 91), (56, 230), (56, 103), (56, 236), (56, 146), (56, 119), (56, 124), (57, 114), (57, 140), (58, 215), (58, 148), (59, 288), (59, 148), (59, 295), (60, 195), (60, 168), (60, 141), (60, 183), (60, 219), (61, 233), (62, 293), (62, 263), (62, 75), (62, 300), (62, 144), (62, 82), (62, 71), (63, 273), (63, 282), (63, 168), (64, 148), (65, 164), (65, 202), (65, 301), (65, 207), (65, 149), (65, 90), (66, 226), (66, 170), (66, 173), (66, 206), (66, 180), (66, 277), (66, 310), (66, 119), (66, 187), (67, 131), (67, 266), (67, 274), (67, 147), (67, 150), (67, 287), (67, 292), (67, 293), (67, 189), (67, 70), (67, 203), (67, 83), (67, 95), (67, 225), (67, 101), (67, 103), (67, 235), (67, 112), (67, 119), (67, 250), (67, 254), (68, 137), (68, 234), (68, 184), (68, 218), (68, 138), (69, 289), (69, 165), (69, 167), (69, 297), (69, 215), (69, 90), (69, 186), (70, 140), (70, 121), (71, 289), (71, 165), (71, 262), (71, 140), (72, 138), (73, 138), (73, 234), (75, 272), (76, 87), (77, 128), (77, 259), (77, 139), (77, 271), (77, 151), (77, 299), (77, 286), (77, 291), (77, 173), (77, 302), (77, 309), (77, 314), (77, 192), (77, 204), (77, 211), (77, 86), (77, 224), (77, 226), (77, 105), (77, 115), (77, 246), (78, 96), (78, 297), (78, 164), (78, 85), (79, 138), (80, 224), (80, 290), (80, 291), (80, 139), (80, 303), (80, 299), (81, 288), (81, 148), (81, 295), (82, 289), (82, 165), (82, 262), (82, 140), (83, 140), (83, 121), (84, 121), (84, 114), (84, 137), (85, 193), (85, 290), (85, 100), (85, 162), (85, 226), (85, 98), (85, 220), (86, 200), (86, 297), (86, 186), (87, 130), (87, 171), (87, 144), (87, 274), (87, 290), (87, 170), (87, 180), (87, 310), (87, 187), (87, 213), (87, 214), (87, 226), (87, 229), (87, 104), (87, 236), (87, 146), (87, 119), (87, 251), (88, 289), (88, 294), (88, 262), (88, 218), (89, 272), (89, 295), (90, 226), (90, 187), (90, 228), (90, 145), (90, 296), (90, 170), (90, 270), (90, 206), (90, 273), (90, 180), (90, 181), (90, 310), (90, 119), (90, 251), (90, 168), (90, 94), (90, 245), (91, 233), (91, 138), (91, 234), (92, 176), (93, 297), (93, 164), (94, 288), (94, 148), (94, 295), (96, 264), (96, 269), (96, 278), (96, 152), (96, 162), (96, 306), (96, 183), (96, 185), (96, 193), (96, 195), (96, 290), (96, 141), (96, 210), (96, 231), (96, 240), (96, 118), (96, 248), (97, 134), (98, 289), (98, 163), (99, 148), (100, 289), (100, 163), (100, 262), (101, 140), (101, 121), (102, 272), (102, 301), (102, 159), (103, 295), (103, 149), (103, 301), (104, 163), (104, 164), (104, 202), (104, 301), (104, 149), (104, 186), (104, 159), (105, 184), (105, 137), (105, 218), (106, 234), (107, 297), (107, 289), (108, 205), (109, 138), (110, 262), (110, 289), (111, 215), (112, 140), (113, 160), (113, 165), (113, 186), (113, 215), (114, 196), (114, 308), (114, 172), (114, 255), (115, 200), (115, 186), (116, 204), (116, 245), (117, 272), (118, 176), (118, 207), (119, 295), (120, 242), (120, 243), (120, 205), (121, 266), (121, 139), (121, 147), (121, 287), (121, 291), (121, 292), (121, 168), (121, 298), (121, 189), (121, 203), (121, 224), (121, 225), (121, 235), (121, 239), (121, 241), (121, 250), (121, 253), (121, 254), (122, 272), (123, 312), (123, 233), (123, 138), (123, 159), (124, 138), (125, 297), (125, 289), (125, 167), (126, 176), (127, 148), (128, 200), (128, 186), (129, 297), (130, 163), (130, 207), (130, 272), (130, 186), (130, 159), (131, 295), (132, 301), (133, 138), (133, 234), (134, 299), (134, 255), (135, 164), (135, 202), (135, 301), (135, 176), (135, 149), (137, 192), (137, 259), (137, 143), (137, 178), (137, 211), (137, 246), (137, 286), (138, 142), (138, 280), (138, 154), (138, 162), (138, 169), (138, 303), (138, 177), (138, 178), (138, 287), (138, 198), (138, 230), (138, 237), (139, 272), (140, 266), (140, 147), (140, 279), (140, 154), (140, 287), (140, 292), (140, 306), (140, 189), (140, 203), (140, 223), (140, 225), (140, 235), (140, 240), (140, 248), (140, 250), (141, 262), (143, 184), (143, 218), (144, 272), (144, 295), (145, 202), (145, 301), (145, 149), (146, 289), (146, 262), (148, 256), (148, 270), (148, 275), (148, 153), (148, 283), (148, 156), (148, 168), (148, 181), (148, 188), (148, 194), (148, 214), (148, 221), (148, 224), (148, 296), (148, 251), (149, 193), (149, 203), (149, 197), (149, 201), (149, 302), (149, 271), (149, 307), (149, 244), (149, 245), (149, 311), (149, 152), (149, 217), (149, 314), (150, 295), (151, 200), (151, 186), (152, 164), (152, 202), (152, 301), (152, 176), (153, 215), (154, 233), (155, 297), (155, 289), (155, 167), (156, 288), (156, 295), (157, 186), (159, 178), (159, 293), (159, 199), (159, 237), (159, 287), (159, 274), (159, 213), (159, 285), (159, 254), (159, 229), (160, 193), (160, 314), (160, 209), (160, 168), (160, 201), (160, 172), (160, 302), (160, 271), (160, 313), (160, 253), (160, 244), (160, 279), (160, 308), (160, 273), (160, 298), (160, 255), (161, 272), (162, 289), (162, 163), (162, 234), (163, 193), (163, 229), (163, 274), (163, 213), (163, 285), (164, 260), (164, 279), (164, 290), (164, 168), (164, 193), (164, 299), (164, 307), (164, 311), (164, 197), (164, 217), (164, 220), (164, 245), (164, 298), (164, 253), (165, 228), (165, 231), (165, 273), (165, 269), (165, 240), (165, 199), (165, 254), (166, 193), (166, 198), (166, 231), (166, 201), (166, 269), (166, 302), (166, 271), (166, 240), (166, 306), (166, 276), (166, 247), (166, 248), (166, 244), (166, 314), (166, 252), (167, 293), (167, 243), (167, 242), (167, 307), (167, 276), (167, 247), (168, 288), (168, 295), (168, 297), (169, 234), (171, 200), (171, 272), (172, 200), (176, 192), (176, 246), (176, 259), (176, 278), (176, 264), (176, 201), (176, 302), (176, 303), (176, 273), (176, 210), (176, 286), (176, 185), (178, 312), (178, 233), (181, 288), (182, 215), (183, 262), (184, 192), (184, 259), (184, 198), (184, 211), (184, 246), (184, 286), (186, 229), (186, 199), (186, 298), (186, 204), (186, 271), (186, 274), (186, 285), (186, 309), (186, 273), (186, 191), (188, 215), (190, 272), (190, 295), (191, 200), (192, 218), (193, 200), (193, 202), (193, 301), (194, 288), (194, 295), (195, 262), (196, 202), (197, 202), (197, 301), (198, 312), (198, 233), (199, 272), (200, 271), (200, 298), (200, 302), (200, 308), (200, 309), (200, 314), (200, 204), (200, 244), (200, 255), (202, 290), (202, 307), (202, 245), (202, 311), (202, 260), (202, 217), (202, 219), (205, 297), (205, 289), (207, 245), (209, 218), (211, 218), (212, 262), (214, 288), (214, 295), (215, 228), (215, 273), (215, 265), (215, 284), (215, 275), (215, 283), (216, 289), (217, 301), (218, 273), (218, 308), (218, 246), (218, 286), (222, 243), (224, 272), (227, 262), (227, 289), (230, 234), (233, 258), (233, 269), (233, 276), (233, 281), (233, 293), (233, 306), (233, 303), (233, 287), (233, 237), (233, 240), (233, 247), (233, 248), (233, 252), (234, 306), (234, 248), (235, 294), (238, 288), (238, 295), (242, 297), (243, 297), (245, 301), (251, 288), (251, 295), (253, 297), (256, 288), (256, 295), (259, 289), (260, 301), (261, 262), (263, 272), (263, 295), (268, 299), (269, 272), (270, 288), (270, 295), (272, 273), (272, 291), (272, 300), (272, 306), (274, 295), (287, 312), (288, 296), (289, 290), (289, 293), (289, 304), (289, 307), (293, 297), (295, 296), (297, 307), (297, 298), (301, 303), (301, 307), (301, 308), (301, 311), (303, 312), (308, 312)]
)
G.remove_nodes_from(
    (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 304, 305, 306, 307)
)

import pdb
def main():
    print "nodes: %r" % G.nodes()
    print "edges: %r" % G.edges()
    
    success, matching = test_matching(G)
    
    print "Matching ok? %r" % success
    print "Matching: %r" % matching
    
    print ""
    
    print "Retrying with the same edges in H"
    H = nx.Graph(G.edges())
    
    success, matching = test_matching(H)
    
    print "Matching ok? %r" % success
    print "Matching: %r" % matching

if __name__ == "__main__":
    main()