CoCalc Shared Filesresearch / posets / linear_extensions.sagewsOpen in CoCalc with one click!
Author: Fidel Barrera-Cruz
Views : 9
import sys from copy import copy from sage.combinat.combinat import CombinatorialClass class LinearExtensions(CombinatorialClass): def __init__(self, dag): r""" Creates an object representing the class of all linear extensions of the directed acyclic graph \code{dag}. Note that upon construction of this object some pre-computation is done. This is the "preprocessing routine" found in Figure 7 of "Generating Linear Extensions Fast" by Preusse and Ruskey. This is an in-place algorithm and the list self.le keeps track of the current linear extensions. The boolean variable self.is_plus keeps track of the "sign". EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: l == loads(dumps(l)) True """ self.dag = dag self._name = "Linear extensions of %s"%dag self.precompute() def switch(self, i): """ This implements the Switch procedure described on page 7 of "Generating Linear Extensions Fast" by Pruesse and Ruskey. If i == -1, then the sign is changed. If i > 0, then self.a[i] and self.b[i] are transposed. Note that this meant to be called by the generate_linear_extensions method and is not meant to be used directly. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: _ = l.list() sage: l.le = [0, 1, 2, 3, 4] sage: l.is_plus True sage: l.switch(-1) sage: l.is_plus False sage: l.a [1, 4] sage: l.b [2, 3] sage: l.switch(0) sage: l.le [0, 2, 1, 3, 4] sage: l.a [2, 4] sage: l.b [1, 3] """ if i == -1: self.is_plus = not self.is_plus if i >= 0: a_index = self.le.index(self.a[i]) b_index = self.le.index(self.b[i]) self.le[a_index] = self.b[i] self.le[b_index] = self.a[i] self.b[i], self.a[i] = self.a[i], self.b[i] if self.is_plus: self.linear_extensions.append(self.le[:]) def gswitch(self, i): """ This implements the Switch procedure described on page 7 of "Generating Linear Extensions Fast" by Pruesse and Ruskey. If i == -1, then the sign is changed. If i > 0, then self.a[i] and self.b[i] are transposed. Note that this meant to be called by the generate_linear_extensions method and is not meant to be used directly. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: _ = l.list() sage: l.le = [0, 1, 2, 3, 4] sage: l.is_plus True sage: l.switch(-1) sage: l.is_plus False sage: l.a [1, 4] sage: l.b [2, 3] sage: l.switch(0) sage: l.le [0, 2, 1, 3, 4] sage: l.a [2, 4] sage: l.b [1, 3] """ if i == -1: self.is_plus = not self.is_plus if i >= 0: a_index = self.le.index(self.a[i]) b_index = self.le.index(self.b[i]) self.le[a_index] = self.b[i] self.le[b_index] = self.a[i] self.b[i], self.a[i] = self.a[i], self.b[i] if self.is_plus: yield self.le[:] #self.linear_extensions.append(self.le[:]) def move(self, element, direction): """ This implements the Move procedure described on page 7 of "Generating Linear Extensions Fast" by Pruesse and Ruskey. If direction is "left", then this transposes element with the element on its left. If the direction is "right", then this transposes element with the element on its right. Note that this is meant to be called by the generate_linear_extensions method and is not meant to be used directly. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: _ = l.list() sage: l.le = [0, 1, 2, 3, 4] sage: l.move(1, "left") sage: l.le [1, 0, 2, 3, 4] sage: l.move(1, "right") sage: l.le [0, 1, 2, 3, 4] """ index = self.le.index(element) if direction == "right": self.le[index] = self.le[index+1] self.le[index+1] = element elif direction == "left": self.le[index] = self.le[index-1] self.le[index-1] = element else: print("Bad direction!") sys.exit() if self.is_plus: self.linear_extensions.append(self.le[:]) def gmove(self, element, direction): """ This implements the Move procedure described on page 7 of "Generating Linear Extensions Fast" by Pruesse and Ruskey. If direction is "left", then this transposes element with the element on its left. If the direction is "right", then this transposes element with the element on its right. Note that this is meant to be called by the generate_linear_extensions method and is not meant to be used directly. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: _ = l.list() sage: l.le = [0, 1, 2, 3, 4] sage: l.move(1, "left") sage: l.le [1, 0, 2, 3, 4] sage: l.move(1, "right") sage: l.le [0, 1, 2, 3, 4] """ index = self.le.index(element) if direction == "right": self.le[index] = self.le[index+1] self.le[index+1] = element elif direction == "left": self.le[index] = self.le[index-1] self.le[index-1] = element else: print("Bad direction!") sys.exit() if self.is_plus: yield self.le[:] #self.linear_extensions.append(self.le[:]) def right(self, i, letter): """ If letter =="b", then this returns True if and only if self.b[i] is incomparable with the elements to its right in self.le. If letter == "a", then it returns True if and only if self.a[i] is incomparable with the element to its right in self.le and the element to the right is not self.b[i] This is the Right function described on page 8 of "Generating Linear Extensions Fast" by Pruesse and Ruskey. Note that this is meant to be called by the generate_linear_extensions method and is not meant to be used directly. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: _ = l.list() sage: l.le [0, 1, 2, 4, 3] sage: l.a [1, 4] sage: l.b [2, 3] sage: l.right(0, "a") False sage: l.right(1, "a") False sage: l.right(0, "b") False sage: l.right(1, "b") False """ if letter == "a": x = self.a[i] yindex = self.le.index(x) + 1 if yindex >= len(self.le): return False y = self.le[ yindex ] if self.incomparable(x,y) and y != self.b[i]: return True return False elif letter == "b": x = self.b[i] yindex = self.le.index(x) + 1 if yindex >= len(self.le): return False y = self.le[ yindex ] if self.incomparable(x,y): return True return False else: raise ValueError("Bad letter!") def generate_linear_extensions(self, i): """ This a Python version of the GenLE routine found in Figure 8 of "Generating Linear Extensions Fast" by Pruesse and Ruskey. Note that this is meant to be called by the list method and is not meant to be used directly. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: l.linear_extensions = [] sage: l.linear_extensions.append(l.le[:]) sage: l.generate_linear_extensions(l.max_pair) sage: l.linear_extensions [[0, 1, 2, 3, 4], [0, 2, 1, 3, 4]] """ if i >= 0: self.generate_linear_extensions(i-1) mrb = 0 typical = False while self.right(i, "b"): mrb += 1 self.move(self.b[i], "right") self.generate_linear_extensions(i-1) mra = 0 if self.right(i, "a"): typical = True cont = True while cont: mra += 1 self.move(self.a[i], "right") self.generate_linear_extensions(i-1) cont = self.right(i, "a") if typical: self.switch(i-1) self.generate_linear_extensions(i-1) if mrb % 2 == 1: mla = mra -1 else: mla = mra + 1 for x in range(mla): self.move(self.a[i], "left") self.generate_linear_extensions(i-1) if typical and (mrb % 2 == 1): self.move(self.a[i], "left") else: self.switch(i-1) self.generate_linear_extensions(i-1) for x in range(mrb): self.move(self.b[i], "left") self.generate_linear_extensions(i-1) def ggenerate_linear_extensions(self, i): """ This a Python version of the GenLE routine found in Figure 8 of "Generating Linear Extensions Fast" by Pruesse and Ruskey. Note that this is meant to be called by the list method and is not meant to be used directly. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: l.linear_extensions = [] sage: l.linear_extensions.append(l.le[:]) sage: l.generate_linear_extensions(l.max_pair) sage: l.linear_extensions [[0, 1, 2, 3, 4], [0, 2, 1, 3, 4]] """ if i >= 0: for le in self.ggenerate_linear_extensions(i-1): yield le mrb = 0 typical = False while self.right(i, "b"): mrb += 1 for le in self.gmove(self.b[i], "right"): yield le for le in self.ggenerate_linear_extensions(i-1): yield le mra = 0 if self.right(i, "a"): typical = True cont = True while cont: mra += 1 for le in self.gmove(self.a[i], "right"): yield le for le in self.ggenerate_linear_extensions(i-1): yield le cont = self.right(i, "a") if typical: for le in self.gswitch(i-1): yield le for le in self.ggenerate_linear_extensions(i-1): yield le if mrb % 2 == 1: mla = mra -1 else: mla = mra + 1 for x in range(mla): for le in self.gmove(self.a[i], "left"): yield le for le in self.ggenerate_linear_extensions(i-1): yield le if typical and (mrb % 2 == 1): for le in self.gmove(self.a[i], "left"): yield le else: for le in self.gswitch(i-1): yield le for le in self.ggenerate_linear_extensions(i-1): yield le for x in range(mrb): for le in self.gmove(self.b[i], "left"): yield le for le in self.ggenerate_linear_extensions(i-1): yield le def list(self): """ Returns a list of the linear extensions of the directed acyclic graph. Note that once they are computed, the linear extensions are cached in this object. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: LinearExtensions(D).list() [[0, 1, 2, 3, 4], [0, 1, 2, 4, 3], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [0, 2, 4, 1, 3]] """ if self.linear_extensions is not None: return self.linear_extensions[:] self.linear_extensions = [] self.linear_extensions.append(self.le[:]) self.generate_linear_extensions(self.max_pair) self.switch(self.max_pair) self.generate_linear_extensions(self.max_pair) self.linear_extensions.sort() return self.linear_extensions[:] def precompute(self): ################ #Precomputation# ################ dag_copy = copy(self.dag) le = [] a = [] b = [] #The preprocessing routine found in Figure 7 of #"Generating Linear Extensions Fast" by #Pruesse and Ruskey while dag_copy.num_verts() != 0: #Find all the minimal elements of dag_copy minimial_elements = [] for node in dag_copy.vertices(): if len(dag_copy.incoming_edges(node)) == 0: minimial_elements.append(node) if len(minimial_elements) == 1: le.append(minimial_elements[0]) dag_copy.delete_vertex(minimial_elements[0]) else: ap = minimial_elements[0] bp = minimial_elements[1] a.append(ap) b.append(bp) le.append(ap) le.append(bp) dag_copy.delete_vertex(ap) dag_copy.delete_vertex(bp) self.max_pair = len(a) - 1 self.le = le self.a = a self.b = b self.mrb = 0 self.mra = 0 self.is_plus = True self.linear_extensions = None def generate(self): """ Returns a generator of the linear extensions of the directed acyclic graph. Note that once they are computed, the linear extensions are cached in this object. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: LinearExtensions(D).list() [[0, 1, 2, 3, 4], [0, 1, 2, 4, 3], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [0, 2, 4, 1, 3]] """ self.linear_extensions = [] #self.linear_extensions.append(self.le[:]) yield self.le[:] for le in self.ggenerate_linear_extensions(self.max_pair): yield le #self.generate_linear_extensions(self.max_pair) for le in self.gswitch(self.max_pair): yield le for le in self.ggenerate_linear_extensions(self.max_pair): yield le def incomparable(self, x, y): """ Returns True if vertices x and y are incomparable in the directed acyclic graph when thought of as a poset. EXAMPLES:: sage: from sage.graphs.linearextensions import LinearExtensions sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: l = LinearExtensions(D) sage: l.incomparable(0,1) False sage: l.incomparable(1,2) True """ if (not self.dag.shortest_path(x, y)) and (not self.dag.shortest_path(y, x)): return True return False
P=Posets.BooleanLattice(3)
old_les =[ list(le) for le in P.linear_extensions()]
d=P.hasse_diagram()
dles=LinearExtensions(d)
new_les=[[Integer(x) for x in le] for le in dles.generate()]
new_les.sort()
new_les==old_les
True