Discrepancy between Graph.modular_decomposition() and Wikipedia

asked 2012-08-26 16:55:25 +0100

akm gravatar image

I am either confused, or am seeing a bug, or there's a bug on Wikipedia.

There's a diagram on the page about modular decomposition referenced by the docs: http://en.wikipedia.org/wiki/Modular_... http://en.wikipedia.org/wiki/File:Mod...

It shows a 'series' module containing 2,3,4.

But when I recreate that graph and run modular_decomposition() on it I get something that seems different:

W = Graph() 
W.add_edges([[1,2],[1,4],[1,3],[2,4],[2,5],[2,6],[2,7],[3,4],[3,5],[3,6],[3,7],[4,5],[4,6],[4,7],[5,6],[5,7],[6,8],[6,9],[6,10],[6,11],[7,8],[7,9],[7,10],[7,11],[8,9],[8,10],[8,11],[9,10],[9,11]]) 
W.plot(vertex_size=100) 
W.modular_decomposition()

results in

('Prime', 
  [
    ('Serie', 
      [
        ('Parallel', 
          [
            10, 
            11
          ]
        ), 
        9, 
        8
      ]
    ), 
    ('Parallel', 
      [
        6, 
        7
      ]
    ), 
    5, 
    1, 
    4, 
    ('Parallel', 
      [
        2, 
        3
      ]
    )
  ]
)

Which shows 8,9,10,11 in a 'series' but not 2,3,4.

Am I getting something wrong or missing something?

edit retag flag offensive close merge delete

Comments

I agree that (2,3,4) is a module, and that sage isn't saying so. I think it's a bug. If you have an account on trac, I suggest opening a ticket. If you don't, I would encourage you to request a trac account.

Hugh Thomas gravatar imageHugh Thomas ( 2012-09-23 04:48:20 +0100 )edit