Index: darg.py ================================================================== --- darg.py +++ darg.py @@ -1,19 +1,16 @@ #!python3 -# RULE GRAPH BUILDER -# +""" +RULE GRAPH BUILDER +""" + # by Olivier R. # License: MPL 2 -import json -import time -import traceback - from graphspell.progressbar import ProgressBar - class DARG: """DIRECT ACYCLIC RULE GRAPH""" # This code is inspired from Steve Hanov’s DAWG, 2011. (http://stevehanov.ca/blog/index.php?id=115) @@ -30,11 +27,11 @@ self.oRoot = Node() self.lUncheckedNodes = [] # list of nodes that have not been checked for duplication. self.lMinimizedNodes = {} # list of unique nodes that have been checked for duplication. self.nNode = 0 self.nArc = 0 - + # build lRule.sort() oProgBar = ProgressBar(0, len(lRule)) for aRule in lRule: self.insert(aRule) @@ -45,13 +42,14 @@ self.countArcs() self.displayInfo() # BUILD DARG def insert (self, aRule): + "insert a new rule (tokens must be inserted in order)" if aRule < self.aPreviousRule: - sys.exit("# Error: tokens must be inserted in order.") - + exit("# Error: tokens must be inserted in order.") + # find common prefix between word and previous word nCommonPrefix = 0 for i in range(min(len(aRule), len(self.aPreviousRule))): if aRule[i] != self.aPreviousRule[i]: break @@ -70,11 +68,11 @@ iToken = nCommonPrefix for sToken in aRule[nCommonPrefix:]: oNextNode = Node() oNode.dArcs[sToken] = oNextNode self.lUncheckedNodes.append((oNode, sToken, oNextNode)) - if iToken == (len(aRule) - 2): + if iToken == (len(aRule) - 2): oNode.bFinal = True iToken += 1 oNode = oNextNode oNode.bFinal = True self.aPreviousRule = aRule @@ -94,26 +92,30 @@ # add the state to the minimized nodes. self.lMinimizedNodes[oChildNode] = oChildNode self.lUncheckedNodes.pop() def countNodes (self): + "count nodes within the whole graph" self.nNode = len(self.lMinimizedNodes) def countArcs (self): + "count arcs within the whole graph" self.nArc = 0 for oNode in self.lMinimizedNodes: self.nArc += len(oNode.dArcs) def displayInfo (self): + "display informations about the rule graph" print(" * {:<12} {:>16,}".format("Rules:", self.nRule)) print(" * {:<12} {:>16,}".format("Nodes:", self.nNode)) print(" * {:<12} {:>16,}".format("Arcs:", self.nArc)) def createGraph (self): + "create the graph as a dictionary" dGraph = { 0: self.oRoot.getNodeAsDict() } for oNode in self.lMinimizedNodes: - sHashId = oNode.__hash__() + sHashId = oNode.__hash__() if sHashId not in dGraph: dGraph[sHashId] = oNode.getNodeAsDict() else: print("Error. Double node… same id: ", sHashId) print(str(oNode.getNodeAsDict())) @@ -120,20 +122,23 @@ return dGraph class Node: + """Node of the rule graph""" + NextId = 0 - + def __init__ (self): self.i = Node.NextId Node.NextId += 1 self.bFinal = False self.dArcs = {} # key: arc value; value: a node @classmethod def resetNextId (cls): + "reset to 0 the node counter" cls.NextId = 0 def __str__ (self): # Caution! this function is used for hashing and comparison! cFinal = "1" if self.bFinal else "0" @@ -148,11 +153,11 @@ return self.__str__().__hash__() def __eq__ (self, other): # Used as a key in a python dictionary. # Nodes are equivalent if they have identical arcs, and each identical arc leads to identical states. - return self.__str__() == other.__str__() + return self.__str__() == other.__str__() def getNodeAsDict (self): "returns the node as a dictionary structure" dNode = {} dReValue = {}