Ask Your Question
2

Error with is_prime

asked 2018-03-05 03:28:47 -0500

Acksl gravatar image

updated 2018-03-05 18:13:42 -0500

tmonteil gravatar image

I'm getting an error message when trying to check if a certain graph is prime with the following code:

G=Graph({
     1:[4,9,19,26],
     2:[4,26],
     3:[4,22],
     4:[5,6,7,8,16,17,21,27,1,2,3],
     5:[9,13,22,26,4],
     6:[9,13,26,4],
     7:[9,4],
     8:[9,13,22,4],
     9:[10,11,12,16,20,24,1,5,6,7,8],
     10:[19,9],
     11:[13,9],
     12:[13,19,26,9],
     13:[14,15,16,17,18,27,5,6,8,11,12],
     14:[26,13],
     15:[22,13],
     16:[19,26,4,9,13],
     17:[19,22,4,13],
     18:[19,22,13],
     19:[20,21,23,24,25,1,10,12,16,17,18],
     20:[22,9,19],
     21:[22,4,19],
     22:[23,24,27,3,5,8,15,17,18,20,21],
     23:[26,19,22],
     24:[26,9,19,22],
     25:[26,19],
     26:[27,1,2,5,6,12,14,16,23,24,25],
     27:[4,13,22,26]
     })
G.is_prime()

which gives me the following error message:

Error in lines 30-30
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 7233, in is_prime
    D = self.modular_decomposition()
  File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 7199, in modular_decomposition
    return relabel(D)
  File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 7197, in <lambda>
    relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type != NodeType.NORMAL else id_label[x.children[0]]
  File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 7197, in <lambda>
    relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type != NodeType.NORMAL else id_label[x.children[0]]
KeyError: 27
edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
2

answered 2018-03-05 04:20:48 -0500

tmonteil gravatar image

updated 2018-03-05 04:24:22 -0500

There is definitely an error due to wrong relabelling in the modular_decomposition method, see a minimal example:

sage: G=Graph({1:[2],2:[1]})
sage: G.modular_decomposition()
KeyError: 2

Thanks for reporting ! This is now trac ticket 24898.

edit flag offensive delete link more
2

answered 2018-03-05 20:40:52 -0500

Thanks. This is the fix (the whole id_label business was a leftover from an old buggy implementation of the modular decomposition, now replaced with this one. Will be fixed in the upcoming release.

diff --git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py index 617881e4a7..57504aaecd 100644
--- a/src/sage/graphs/graph.py
+++ b/src/sage/graphs/graph.py
@@ -7180,9 +7180,7 @@ class Graph(GenericGraph):

         D = modular_decomposition(self)

-        id_label = dict(enumerate(self.vertices()))
-
-        relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type !=NodeType.NORMAL else id_label[x.children[0]]
+        relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type != NodeType.NORMAL else x.children[0]

          return relabel(D)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-03-05 03:28:47 -0500

Seen: 65 times

Last updated: Mar 05