*** Extraction of dominant and absorbent kernels *** ** The Heawood graph data ** * direct neighbors : * {'11': (set(['2', '10', '12']), set(['2', '10', '12'])), '10': (set(['11', '9', '5']), set(['11', '9', '5'])), '13': (set(['0', '12', '4']), set(['0', '12', '4'])), '12': (set(['11', '13', '7']), set(['11', '13', '7'])), '1': (set(['0', '2', '6']), set(['0', '2', '6'])), '0': (set(['1', '9', '13']), set(['1', '9', '13'])), '3': (set(['8', '2', '4']), set(['8', '2', '4'])), '2': (set(['11', '1', '3']), set(['11', '1', '3'])), '5': (set(['10', '4', '6']), set(['10', '4', '6'])), '4': (set(['13', '5', '3']), set(['13', '5', '3'])), '7': (set(['8', '12', '6']), set(['8', '12', '6'])), '6': (set(['1', '5', '7']), set(['1', '5', '7'])), '9': (set(['10', '8', '0']), set(['10', '8', '0'])), '8': (set(['9', '3', '7']), set(['9', '3', '7']))} * not direct neighbors : * {'11': (set(['11', '13', '1', '0', '3', '5', '4', '7', '6', '9', '8']), set(['11', '13', '1', '0', '3', '5', '4', '7', '6', '9', '8'])), '10': (set(['10', '13', '12', '1', '0', '3', '2', '4', '7', '6', '8']), set(['10', '13', '12', '1', '0', '3', '2', '4', '7', '6', '8'])), '13': (set(['11', '10', '13', '1', '3', '2', '5', '7', '6', '9', '8']), set(['11', '10', '13', '1', '3', '2', '5', '7', '6', '9', '8'])), '12': (set(['10', '12', '1', '0', '3', '2', '5', '4', '6', '9', '8']), set(['10', '12', '1', '0', '3', '2', '5', '4', '6', '9', '8'])), '1': (set(['11', '10', '13', '12', '1', '3', '5', '4', '7', '9', '8']), set(['11', '10', '13', '12', '1', '3', '5', '4', '7', '9', '8'])), '0': (set(['11', '10', '12', '0', '3', '2', '5', '4', '7', '6', '8']), set(['11', '10', '12', '0', '3', '2', '5', '4', '7', '6', '8'])), '3': (set(['11', '10', '13', '12', '1', '0', '3', '5', '7', '6', '9']), set(['11', '10', '13', '12', '1', '0', '3', '5', '7', '6', '9'])), '2': (set(['10', '13', '12', '0', '2', '5', '4', '7', '6', '9', '8']), set(['10', '13', '12', '0', '2', '5', '4', '7', '6', '9', '8'])), '5': (set(['11', '13', '12', '1', '0', '3', '2', '5', '7', '9', '8']), set(['11', '13', '12', '1', '0', '3', '2', '5', '7', '9', '8'])), '4': (set(['11', '10', '12', '1', '0', '2', '4', '7', '6', '9', '8']), set(['11', '10', '12', '1', '0', '2', '4', '7', '6', '9', '8'])), '7': (set(['11', '10', '13', '1', '0', '3', '2', '5', '4', '7', '9']), set(['11', '10', '13', '1', '0', '3', '2', '5', '4', '7', '9'])), '6': (set(['11', '10', '13', '12', '0', '3', '2', '4', '6', '9', '8']), set(['11', '10', '13', '12', '0', '3', '2', '4', '6', '9', '8'])), '9': (set(['11', '13', '12', '1', '3', '2', '5', '4', '7', '6', '9']), set(['11', '13', '12', '1', '3', '2', '5', '4', '7', '6', '9'])), '8': (set(['11', '10', '13', '12', '1', '0', '2', '5', '4', '6', '8']), set(['11', '10', '13', '12', '1', '0', '2', '5', '4', '6', '8']))} * Connected Components : * 1: set(['11', '10', '13', '12', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8']) ** Extracting the kernels ** * Iterations * 1 ------------ Minimal dominant choice: frozenset(['11', '1', '13', '5', '7', '9', '3']) Minimal absorbent choice: frozenset(['11', '1', '13', '5', '7', '9', '3']) Minimal dominant choice: frozenset(['11', '1', '13', '5', '8']) Minimal absorbent choice: frozenset(['11', '1', '13', '5', '8']) Minimal dominant choice: frozenset(['11', '9', '13', '3', '6']) Minimal absorbent choice: frozenset(['11', '9', '13', '3', '6']) Minimal dominant choice: frozenset(['11', '8', '13', '6']) Minimal absorbent choice: frozenset(['11', '8', '13', '6']) Minimal dominant choice: frozenset(['11', '1', '9', '4', '7']) Minimal absorbent choice: frozenset(['11', '1', '9', '4', '7']) Minimal dominant choice: frozenset(['11', '1', '4', '8']) Minimal absorbent choice: frozenset(['11', '1', '4', '8']) Minimal dominant choice: frozenset(['11', '0', '3', '5', '7']) Minimal absorbent choice: frozenset(['11', '0', '3', '5', '7']) Minimal dominant choice: frozenset(['11', '0', '3', '6']) Minimal absorbent choice: frozenset(['11', '0', '3', '6']) Minimal dominant choice: frozenset(['11', '0', '5', '8']) Minimal absorbent choice: frozenset(['11', '0', '5', '8']) Minimal dominant choice: frozenset(['11', '0', '4', '7']) Minimal absorbent choice: frozenset(['11', '0', '4', '7']) Minimal dominant choice: frozenset(['11', '0', '8', '4', '6']) Minimal absorbent choice: frozenset(['11', '0', '8', '4', '6']) Minimal dominant choice: frozenset(['11', '9', '4', '6']) Minimal absorbent choice: frozenset(['11', '9', '4', '6']) 2 ------------ Minimal dominant choice: frozenset(['1', '10', '13', '3', '7']) Minimal absorbent choice: frozenset(['1', '10', '13', '3', '7']) Minimal dominant choice: frozenset(['1', '10', '13', '8']) Minimal absorbent choice: frozenset(['1', '10', '13', '8']) Minimal dominant choice: frozenset(['10', '13', '3', '6']) Minimal absorbent choice: frozenset(['10', '13', '3', '6']) Minimal dominant choice: frozenset(['10', '13', '2', '7']) Minimal absorbent choice: frozenset(['10', '13', '2', '7']) Minimal dominant choice: frozenset(['10', '13', '2', '8', '6']) Minimal absorbent choice: frozenset(['10', '13', '2', '8', '6']) Minimal dominant choice: frozenset(['1', '10', '3', '12']) Minimal absorbent choice: frozenset(['1', '10', '3', '12']) Minimal dominant choice: frozenset(['1', '10', '12', '4', '8']) Minimal absorbent choice: frozenset(['1', '10', '12', '4', '8']) Minimal dominant choice: frozenset(['10', '3', '12', '6', '0']) Minimal absorbent choice: frozenset(['10', '3', '12', '6', '0']) Minimal dominant choice: frozenset(['10', '2', '4', '0', '8', '12', '6']) Minimal absorbent choice: frozenset(['10', '2', '4', '0', '8', '12', '6']) Minimal dominant choice: frozenset(['1', '10', '4', '7']) Minimal absorbent choice: frozenset(['1', '10', '4', '7']) Minimal dominant choice: frozenset(['10', '3', '7', '0']) Minimal absorbent choice: frozenset(['10', '3', '7', '0']) Minimal dominant choice: frozenset(['10', '2', '4', '7', '0']) Minimal absorbent choice: frozenset(['10', '2', '4', '7', '0']) 3 ------------ Minimal dominant choice: frozenset(['9', '13', '2', '5', '7']) Minimal absorbent choice: frozenset(['9', '13', '2', '5', '7']) Minimal dominant choice: frozenset(['8', '13', '2', '5']) Minimal absorbent choice: frozenset(['8', '13', '2', '5']) Minimal dominant choice: frozenset(['9', '13', '2', '6']) Minimal absorbent choice: frozenset(['9', '13', '2', '6']) 4 ------------ Minimal dominant choice: frozenset(['1', '9', '3', '12', '5']) Minimal absorbent choice: frozenset(['1', '9', '3', '12', '5']) Minimal dominant choice: frozenset(['1', '8', '12', '5']) Minimal absorbent choice: frozenset(['1', '8', '12', '5']) Minimal dominant choice: frozenset(['1', '9', '12', '4']) Minimal absorbent choice: frozenset(['1', '9', '12', '4']) Minimal dominant choice: frozenset(['0', '3', '12', '5']) Minimal absorbent choice: frozenset(['0', '3', '12', '5']) Minimal dominant choice: frozenset(['2', '0', '12', '5', '8']) Minimal absorbent choice: frozenset(['2', '0', '12', '5', '8']) Minimal dominant choice: frozenset(['9', '3', '12', '6']) Minimal absorbent choice: frozenset(['9', '3', '12', '6']) Minimal dominant choice: frozenset(['9', '2', '12', '5']) Minimal absorbent choice: frozenset(['9', '2', '12', '5']) Minimal dominant choice: frozenset(['9', '12', '2', '4', '6']) Minimal absorbent choice: frozenset(['9', '12', '2', '4', '6']) 5 ------------ 6 ------------ Minimal dominant choice: frozenset(['0', '2', '5', '7']) Minimal absorbent choice: frozenset(['0', '2', '5', '7']) 7 ------------ 8 ------------ Minimal dominant choice: frozenset(['9', '2', '4', '7']) Minimal absorbent choice: frozenset(['9', '2', '4', '7']) 9 ------------ 10 ------------ 11 ------------ 12 ------------ 13 ------------ 14 ------------ * Statistics * Time : 0.03 History : 457 (visited independent choices in the graph) Solutions: 74/2 = 37 ** All kernel solutions: ** set([frozenset(['11', '0', '3', '6']), frozenset(['2', '0', '12', '5', '8']), frozenset(['10', '13', '2', '7']), frozenset(['1', '9', '3', '12', '5']), frozenset(['11', '1', '9', '4', '7']), frozenset(['11', '8', '13', '6']), frozenset(['10', '2', '4', '0', '8', '12', '6']), frozenset(['11', '0', '5', '8']), frozenset(['1', '10', '13', '8']), frozenset(['11', '9', '13', '3', '6']), frozenset(['1', '10', '4', '7']), frozenset(['9', '2', '12', '5']), frozenset(['8', '13', '2', '5']), frozenset(['10', '3', '7', '0']), frozenset(['11', '1', '13', '5', '7', '9', '3']), frozenset(['0', '3', '12', '5']), frozenset(['9', '12', '2', '4', '6']), frozenset(['1', '8', '12', '5']), frozenset(['1', '10', '3', '12']), frozenset(['11', '0', '8', '4', '6']), frozenset(['11', '1', '13', '5', '8']), frozenset(['1', '9', '12', '4']), frozenset(['9', '13', '2', '5', '7']), frozenset(['1', '10', '12', '4', '8']), frozenset(['10', '3', '12', '6', '0']), frozenset(['10', '13', '3', '6']), frozenset(['11', '1', '4', '8']), frozenset(['9', '13', '2', '6']), frozenset(['1', '10', '13', '3', '7']), frozenset(['9', '2', '4', '7']), frozenset(['11', '0', '4', '7']), frozenset(['10', '13', '2', '8', '6']), frozenset(['11', '0', '3', '5', '7']), frozenset(['10', '2', '4', '7', '0']), frozenset(['11', '9', '4', '6']), frozenset(['0', '2', '5', '7']), frozenset(['9', '3', '12', '6'])]) *** Isomorphic reduction of kernels *** ** Automorphic actions: ** 1. frozenset([('6', '12'), ('5', '11'), ('1', '13'), ('2', '4')]) 2. frozenset([('3', '11'), ('8', '12'), ('9', '13'), ('4', '10')]) 3. frozenset([('4', '8'), ('10', '12'), ('5', '7'), ('9', '13')]) 4. {'11': '8', '10': '9', '13': '6', '12': '7', '1': '2', '0': '1', '3': '4', '2': '3', '5': '10', '4': '5', '7': '12', '6': '11', '9': '0', '8': '13'} ** Reducing isomorphic solutions ** * Number of remaining solutions: 37 * current solution : frozenset(['11', '0', '3', '6']) 2 4 10 16 20 21 .... orbit: covered: frozenset(['11', '0', '3', '6']) covered: frozenset(['1', '9', '12', '4']) covered: frozenset(['10', '13', '2', '7']) covered: frozenset(['1', '10', '3', '12']) covered: frozenset(['11', '8', '13', '6']) covered: frozenset(['10', '13', '3', '6']) covered: frozenset(['1', '8', '4', '11']) covered: frozenset(['9', '13', '2', '6']) covered: frozenset(['1', '8', '13', '10']) covered: frozenset(['9', '2', '4', '7']) covered: frozenset(['11', '0', '5', '8']) covered: frozenset(['1', '10', '4', '7']) covered: frozenset(['9', '12', '2', '5']) covered: frozenset(['8', '13', '2', '5']) covered: frozenset(['0', '3', '7', '10']) covered: frozenset(['11', '9', '4', '6']) covered: frozenset(['0', '3', '12', '5']) covered: frozenset(['1', '8', '12', '5']) covered: frozenset(['0', '2', '5', '7']) covered: frozenset(['11', '0', '4', '7']) covered: frozenset(['9', '3', '12', '6']) * Number of remaining solutions: 16 * current solution : frozenset(['1', '10', '13', '3', '7']) 3 6 11 13 14 ..... orbit: covered: frozenset(['11', '0', '6', '4', '8']) covered: frozenset(['1', '8', '13', '5', '11']) covered: frozenset(['2', '0', '12', '5', '8']) covered: frozenset(['9', '13', '2', '5', '7']) covered: frozenset(['1', '9', '3', '12', '5']) covered: frozenset(['1', '9', '4', '7', '11']) covered: frozenset(['1', '8', '12', '4', '10']) covered: frozenset(['1', '10', '13', '3', '7']) covered: frozenset(['0', '3', '6', '12', '10']) covered: frozenset(['9', '11', '3', '13', '6']) covered: frozenset(['8', '13', '2', '10', '6']) covered: frozenset(['11', '0', '3', '5', '7']) covered: frozenset(['9', '12', '2', '4', '6']) covered: frozenset(['0', '2', '4', '7', '10']) * Number of remaining solutions: 2 * current solution : frozenset(['10', '2', '4', '0', '8', '12', '6']) 1 2 .... orbit: covered: frozenset(['10', '2', '4', '0', '8', '12', '6']) covered: frozenset(['1', '11', '3', '5', '7', '9', '13']) *** Results *** ** Not isomorph solutions: 3 ** 1. frozenset(['11', '0', '3', '6']), 2. frozenset(['1', '10', '13', '3', '7']), 3. frozenset(['10', '2', '4', '0', '8', '12', '6'])]) ************************ * allkernelsheawood.py * * R.B. August 2005 * ************************