NFAGraph.py

# !/usr/bin/env python3
from copy import copy

start_point = 1
'''graph_list = list of links represented by (orig, dest, value)'''
graph_list = [(1, 2, "a"), 
        (2, 3, "g"), 
        (2, 4, "c"), 
        (2, 5, ("SET", "F", "G", "H")), 
        (4, 2, ("NOT", ""))]

def graph_list2dict(graph_list):
    graph_dict = dict()

    for item in graph_list:
        orig = item[0]
        dest = item[1]
        value = item[2]

        if orig in graph_dict:
            if value in graph_dict[orig]:
                raise Exception("Each 2 links from the same link shouldn't have the same value.")
            '''
			else:
                for link_value in graph_dict[orig]:
                    if dest == graph_dict[orig][link_value]:
                        raise Exception("The orig-dest pair are duplicated.")'''

        else:
            graph_dict[orig] = dict()
        
        graph_dict[orig][value] = dest
    
    return graph_dict
        
graph_dict = graph_list2dict(graph_list)
print(graph_dict)

string1 = "ag"
string2 = "acxcxcxc"


def char_pattern_list_match(value, c):
    '''Match a char with char pattern list "value". Called with pattern match'''
    head = value[0]
    # char pattern ["NOT", "a"] = [^a]
    if head == "NOT":
        if len(value) > 2:
            raise Exception("in char pattern NOT contains only 1 sub-pattern")
        return not (value_match(value[1], c))
    
    # char pattern ["SET", "a", "b", ...] = [ab...]
    elif head == "SET":
        if len(value) == 1:
            raise Exception("in char pattern SET contains at least 1 sub-pattern")
        for i in value[1:]:
            if value_match(i, c):
                return True
        return False
    
    elif head == "RANGE":
        if len(value) != 3 or not (isinstance(value[1], str) and isinstance(value[2], str)):
            raise Exception("in char pattern RANGE contains only 2 chars")
        elif len(value[1]) > 1 or len(value[2]) > 1:
            raise Exception("in char pattern RANGE contains no string of which length > 1")
        else:
            lower_bound = ord(value[1])
            upper_bound = ord(value[2])
            if lower_bound > upper_bound:
                raise Exception(
                    "in char pattern RANGE the lower_bound must not bigger than upper bound.")

            if ord(c) >= lower_bound and ord(c) <= upper_bound:
                return True
            else:
                return False
    else:
        raise Exception("The head of a char pattern list is not acceptable.")

def value_match(value, c):
    if isinstance(value, str):
        is_meta_character = (len(value) == 2 and value[1] == "\\")
        if len(value) > 1 and not is_meta_character:
            raise Exception("Can't compare a char with 2 or more chars.")
        elif value == c:
            return True
        else:
            return False

    elif isinstance(value, tuple):
        return char_pattern_list_match(value, c)

    else:
        raise Exception("The argument called with match_value is not available.")    

print(value_match(("SET", ("RANGE", "a", "g")), "k"))

def transit_string_in_graph(graph_dict, start_point, string):
    status = start_point
    for c in string:
        for value in graph_dict[status]:
            if value_match(value, c):
                status = graph_dict[status][value]
    
    return status

print(transit_string_in_graph(graph_dict, start_point, string2))


def id_gen():
    id_num = 0
    while True:
        new_value = (yield id_num)
        if new_value != None:
            id_num = new_value
        else:
            id_num += 1

real_id_generator = id_gen()

class NFA():
    '''Definition of NFA graph'''
    def __init__(self):
        self.start = None
        self.end = []
        self.graph = [] # list of triary tuple
    
    '''def __repr__(self):
        return_string = ""
        return_string += "Start: %d\n" % self.start
        
        if self.graph == []:
            return_string += "EMPTY PATH"

        else:
            for path in self.graph:
                path_string = "%s -> %s : %s\n" % (path[0], path[1], path[2])
                return_string += path_string
        
        end_string = "End: " + str(self.end)
        return_string += end_string
        
        return return_string
    '''        
def make_simple_nfa(pattern):
    nfa = NFA()
    nfa.start = next(real_id_generator)
    nfa.end.append(next(real_id_generator))

    nfa.graph.append(tuple([nfa.start, nfa.end[0], pattern]))

    return nfa

def nfa_concat(nfa1, nfa2):
    """xy"""
    new_nfa = NFA()
    new_nfa.start = copy(nfa1.start)

    connecting_point_pair = [nfa1.end, nfa2.start]
    
    new_graph = copy(nfa1.graph)
    new_end = []
    for path in nfa2.graph:
        if path[0] == connecting_point_pair[1]:
            for n in connecting_point_pair[0]:
                new_graph.append(tuple([n] + list(path[1:3])))
        else:
            new_graph.append(path)
    
    for e in nfa2.end:
        if e == connecting_point_pair[1]:
            new_end += nfa1.end
        else:
            new_end.append(e)
    
    new_nfa.graph = new_graph
    new_nfa.end = new_end

    return new_nfa

def nfa_or(nfa1, nfa2):
    """x|y"""
    new_nfa = NFA()
    new_nfa.start = copy(nfa1.start)

    new_end = copy(nfa1.end)
    
    new_graph = copy(nfa1.graph)

    for path in nfa2.graph:
        if path[0] == nfa2.start:
            appended_link = tuple([nfa1.start] + list(path[1:3]))
            new_graph.append(appended_link)
        else:
            new_graph.append(path)
    
    for e in nfa2.end:
        if e == nfa2.start:
            new_end.append(nfa1.start)
        else:
            new_end.append(e)
    
    new_nfa.graph = new_graph
    new_nfa.end = new_end

    return new_nfa

def nfa_once_or_none(nfa1, nfa2):
    """"xy?"""
    new_nfa = NFA()
    new_nfa.start = copy(nfa1.start)
    new_nfa.end = nfa1.end + filter(lambda x : x != nfa2.start, nfa2.end)

    new_graph = copy(nfa1.graph)
    for path in nfa2.graph:
        generated_links = []

        if path[0] == nfa2.start:
            for new_link_orig in nfa1.end:
                appended_link = tuple([new_link_orig] + list(path[1:]))
                generated_links.append(appended_link)
        else:
            generated_links = [path]

    new_graph += generated_links
    new_nfa.graph = new_graph

    return new_nfa


def nfa_repeat_or_none(nfa1, nfa2):
    """xy*"""
    new_nfa = NFA()
    new_nfa.start = copy(nfa1.start)
    new_nfa.end = copy(nfa1.end)

    new_graph = copy(nfa1.graph)

    for path in nfa2.graph:
        temp_links = []

        if path[0] == nfa2.start:
            for new_link_orig in nfa1.end:
                appended_link = tuple([new_link_orig] + list(path[1:]))
                temp_links.append(appended_link)
        else:
            temp_links = [path]
    
        generated_new_links = []
        for link in temp_links:
            if link[1] in nfa2.end:
                for new_link_end in nfa1.end:
                    appended_link = tuple([link[0]]+[new_link_end]+[link[2]])
                    generated_new_links.append(appended_link)
            else:
                generated_new_links.append(link)

    new_graph += generated_new_links
    new_nfa.graph = new_graph
    
    return new_nfa

nfa1 = make_simple_nfa("a")
nfa2 = make_simple_nfa(("NOT", "b"))
nfa3 = nfa_or(nfa1, nfa2)
print(nfa3)
print(nfa_repeat_or_none(nfa1, nfa2).graph)
print(nfa_once_or_none(nfa1, nfa2).graph)

NFATree.java

// package NFAGraph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Hashtable;
import dir.Tree;
/*
* Exception for NFA 
*/
class NFAException extends Exception
{
    private static final long serialVersionUID = 1L;

    public NFAException(String message)
  {
    super(message);
  }
}

/*
* structure for NFAGraph
*/
class NFAGraph{
    private Integer start;
    private ArrayList<Integer> endList; // List of end node num.
    private ArrayList<NFAGraphPath> graphTable; // graph shown as table

    public String toString(){
        String returnString = "";
        returnString += String.format("%d [shape=Diamond]\n" , this.start);

        if (this.graphTable.length == 0){
            returnString += "\n";
        }
        else{
            for (int i=0; i < this.graphTable.size() ; i++ ){
                Integer orig = this.graphTable.get(i).getOrig();
                Integer dest = this.graphTable.get(i).getDest();

                returnString += String.format("%d -> %d\n" , orig , dest);
            }
        }

        String endString = "";

        for (int i=0; i<this.endList.size(); i++){
            endString += String.format("%d [shape=square]\n", this.endList.get(i));   
        }
        
        returnString += endString;
    }

    public ArrayList<Integer> getEndList(){
        return this.endList;
    }

    /**
     * @return the start
     */
    public Integer getStart() {
        return this.start;
    }

    public ArrayList<NFAGraphPath> getGraphTable(){
        return this.graphTable;
    }

    public setEndList(ArrayList<Integer> endList){
        this.endList = endList;
    }

    public setStart(Integer startId){
        this.start = startId;
    }

    public addGraphPath(NFAGraphPath path){
        this.graphTable.add(path);
    }


    public static void main(String[] args) {
        NFAGraph _a = new NFAGraph();
        _a.start = 1;
        NFAGraphPath p1 = new NFAGraphPath(1, 2, "a");
        NFAGraphPath p2 = new NFAGraphPath(2, 3, "g");
        NFAGraphPath p3 = new NFAGraphPath(2, 4, "c");

        Tree<String> pattern = new Tree<String>("SET");
        pattern.appendChildrenList(Arrays.asList("F", "G", "H"));
        NFAGraphPath p4 = new NFAGraphPath(2, 5, pattern);

        _a.graphTable.add(p1);
        _a.graphTable.add(p2);
        _a.graphTable.add(p3);
        _a.graphTable.add(p4);

        try{
        Hashtable h = _a.nfaTableToHashMap();
        int z = 1 + 1;

        } catch (NFAException e) {
            System.out.println(e);
        }


    }

    public NFAGraph(int orig, int dest, NFAGraphPath path){
        this.start = (Integer) orig;
        this.endList = new ArrayList<Integer>(Arrays.asList((Integer) dest));
        this.graphTable = new ArrayList<NFAGraphPath>(Arrays.asList(path));
    }

    public NFAGraph(){
        this.start = (Integer)-1 ; // impossible value
        this.endList = new ArrayList<Integer>();
        this.graphTable = new ArrayList<NFAGraphPath>();
    }

    public NFAGraph(int orig, ArrayList<Integer> destList, NFAGraphPath path){
        this.start = (Integer)orig;
        this.endList = destList;
        this.graphTable = new ArrayList<NFAGraphPath>(Arrays.asList(path));
    }

    /* return a Hashtable in the form of:
    * Hashtable< OrigId, <Pattern, DestId>>
    *
    */
    Hashtable<Integer, Hashtable<Tree<String>,Integer>> nfaTableToHashMap () throws NFAException{
        Hashtable<Integer, Hashtable<Tree<String>,Integer>> graphHashMap  = new Hashtable();
        for (int i=0;i<this.graphTable.size(); i++){
            Integer orig = this.graphTable.get(i).getOrig();
            Integer dest = this.graphTable.get(i).getDest();
            Tree<String> pattern = this.graphTable.get(i).getPatt();

            if (graphHashMap.containsKey(orig)){
                if (graphHashMap.get(orig).containsKey(pattern)){
                    throw new NFAException(
                        "Each 2 links from the same link shouldn't have the same value.");
                }
                
            }else{
                // graph_dict[orig] = dict()
                graphHashMap.put(orig, new Hashtable());
            }

            graphHashMap.get(orig).put(pattern, dest);

        }
        return graphHashMap;
    }
    /*
    * (value_match)
    * Match a char string with char pattern string (1-char) "pattern". 
    */
    boolean charPatternMatch(String patt, String c) throws NFAException{
        if (c.length()>1){
            throw NFAException("Char or pattern input too many.");
        }
        else if(patt.length()>1){
            throw NFAException("patt or pattern input too many.");
        }
        else{
            if(c == patt){
                return true;
            }
            else{
                return false;
            }
        }
    }

    /*
    * Match a char string with char pattern (tree) "pattern".
    */
    boolean charPatternMatch(Tree<String> patt, String c) throws NFAException{
        if (c.length()>1){
            throw NFAException("Char input too many.");
        }
        else{
            head = patt.getNode();
            if (head == "NOT"){
                if(patt.getChildrenList().size()>1){
                    throw NFAException("in char pattern NOT contains only 1 sub-pattern");
                    return not(this.charPatternMatch(patt.getChildrenList().get(0),c));
                }
            }
            else if(patt.getNode() == "SET"){
                this.charPatternMatchSet(patt, c);
            }
            else if (patt.getNode() == "RANGE"){
                this.charPatternMatchRange(patt, c);
            }
            else if (patt.getNode().length() == 1){
                thischarPatternMatch(patt.getNode(),c); // char-to-char matching
            }
            else{
                throw NFAException("The form of a char pattern tree is not acceptable.");
            }
        }
    }



    /*
    * check part for patt of which head node is "SET". 
    */
    boolean charPatternMatchSet(Tree<String> patt, String c) throws NFAException{
        if (patt.getChildrenList().size() == 0){
            throw NFAException("in char pattern SET contains at least 1 sub-pattern");
        }else{
            for (int i=0;i<patt.getChildrenList().size();i++){
                if (this.charPatternMatch(patt, c)){
                    return true;
                }
                else{
                    return false;
                }
            }
        }
    }

    /*
    * check part for patt of which head node is "RANGE". 
    */  
    boolean charPatternMatchRange(Tree<String> patt, String c) throws NFAException{
        if (patt.getChildrenList().size() > 2){
            throw NFAException("in char pattern RANGE contains only 2 chars");
        }
        else if (patt.getChildrenList().get(0).length()>1 || patt.getChildrenList().get(1).length()>1){
            throw NFAException("In char pattern RANGE contains no string of which length > 1.");
        }
        else {
            char lowerBound = patt.getChildrenList().get(0).charAt(0);
            char upperBound = patt.getChildrenList().get(1).charAt(0);
            if (lowerBound > upperBound){
                throw NFAException("In char pattern RANGE the lower_bound must not bigger than upper bound.");
            }
            else{
                if (c.charAt(0) >= lowerBound && c.charAt(0) <= upperBound){
                    return true;
                }
                else{
                    return false;
                }
            }
        
        }
    }

    public Integer transitStrInGraph(int startPoint, String str){
        Integer status = (Integer) startPoint;
        Hashtable<Integer, Hashtable<Tree<String>,Integer>> nfaHashMap = this.nfaTableToHashMap();
        for (int i=0;i<str.length();i++){
            String c = str.substring(i,i+1);
            // treeKey : the key is a tree
            for(Tree<String> treeKey : nfaHashMap.get(status).keySet()){
                boolean treeKeyMatched = this.charPatternMatch(treeKey, c);
                if (treeKeyMatched){
                    status = nfaHashMap.get(status).get(treeKey);
                }
            }
        }

        return status;
    }
}

/*
* Path for NFAGraph.graph
* [2]-- a ->[3]
* orig = 2;
* dest = 3;
* patt = ['a'];
*/
class NFAGraphPath {
    private Integer orig;
    private Integer dest;
    private Tree<String> patt;

    public NFAGraphPath(int ori, int des, String ptn) {
        this.orig = (Integer) ori;
        this.dest = (Integer) des;
        this.patt = new Tree<String>(ptn);

    }

    public NFAGraphPath(int ori, int des, Tree<String> ptnTree) {
        this.orig = (Integer) ori;
        this.dest = (Integer) des;
        this.patt = ptnTree;
    }

    Integer getOrig() {
        return this.orig;
    }

    Integer getDest() {
        return this.dest;
    }
    Tree<String> getPatt() {
        return this.patt;
    }
}

/**
 * containing mainaulations for the nfa graph genarating.
 */
class NfaManipulation{
    Integer id; // the id number that will be returned by nextId

    public NNfaManipulation(){
        this.id = (Integer) 0;
    }

    Integer nextId (){
        Integer retId = this.id;
        this.id += 1;
        return retId;
    }

    public NFAGraph makeSimpleNFA(String pattern){
        Integer start = this.nextId();
        Integer end = this.nextId();
        NFAGraphPath path = NFAGraphPath(start, end, pattern);
        NFAGraph nfa = NFAGraph(start, end, path);
        return nfa;
    }

    public NFAGraph makeSimpleNFA(Tree<String> pattern){
        Integer start = this.nextId();
        Integer end = this.nextId();
        NFAGraphPath path = NFAGraphPath(start, end, pattern);
        NFAGraph nfa = NFAGraph(start, end, path);
        return nfa;
    }

    /**
    * xy
    */
    public nfaConcat(NFAGraph nfa1, NFAGraph nfa2){
        Integer nfa1Start = nfa1.getStart();
        ArrayList<Integer> nfa1EndList = nfa1.getEndList();
        
        ArrayList<NFAGraphPath> nfa1NFAGraphList = nfa1.getGraphTable();
        ArrayList<NFAGraphPath> nfa2NFAGraphList = nfa2.getGraphTable();

        NFAGraph resultNFA = new NFAGraph();

        resultNFA.setStart(nfa1Start);

        concatNFAGraph(nfa2, nfa1EndList, nfa1NFAGraphList, nfa2NFAGraphList, resultNFA);

        resultNFA.setEndList(nfa2.getEndList());
        return resultNFA;
    }

    private void concatNFAGraph(NFAGraph nfa2, ArrayList<Integer> nfa1EndList, ArrayList<NFAGraphPath> nfa1NFAGraphList,
            ArrayList<NFAGraphPath> nfa2NFAGraphList, NFAGraph resultNFA) {
        for(int i=0; i<nfa1NFAGraphList.size();i++){
            resultNFA.addGraphPath(nfa1NFAGraphList.get(i));
        }

        for(int i=0; i<nfa1EndList.size();i++){
            for (int j=0; i<nfa2NFAGraphList.size();j++){
                NFAGraphPath path = nfa2NFAGraphList.get(j);

                if(path.getOrig() == (Integer) nfa1EndList.get(i)){
                    NFAGraphPath newPath =
                        new NFAGraphPath(nfa2.getStart(), path.getDest(), path.getPatt());
                    resultNFA.addGraphPath(newPath);
                }
                else{
                    resultNFA.addGraphPath(path);
                }
            }
        }
    }

    /**
    * x | y
    */
    public nfaOr(NFAGraph nfa1, NFAGraph nfa2){
        Integer nfa1Start = nfa1.getStart();
        Integer nfa2Start = nfa2.getStart();

        ArrayList<Integer> nfa1EndList = nfa1.getEndList();
        ArrayList<Integer> nfa2EndList = nfa2.getEndList();

        ArrayList<NFAGraphPath> nfa1NFAGraphList = nfa1.getGraphTable();
        ArrayList<NFAGraphPath> nfa2NFAGraphList = nfa2.getGraphTable();

        NFAGraph resultNFA = new NFAGraph();
        resultNFA.setStart(nfa1Start);
        ArrayList<Integer> NewEndList = nfa1EndList;

        for(int i=0; i<nfa1NFAGraphList.size();i++){
            resultNFA.addGraphPath(nfa1NFAGraphList.get(i));
        }

        for(int i=0;i<nfa2NFAGraphList.size();i++){
            NFAGraphPath path = nfa2NFAGraphList.get(i);

            if(path.getOrig() == nfa2Start){
                NFAGraphPath newPath = new NFAGraphPath(nfa1Start, path.getDest(), path.getPatt());
                resultNFA.addGraphPath(newPath);
            }
            else{
                resultNFA.addGraphPath(path);
            }
        }

        for (int i=0;i<nfa2EndList.size();i++){
            if (nfa2EndList.get(i) == nfa2Start){
                NewEndList.add(nfa1Start);
            }
            else{
                NewEndList.add(nfa2EndList.get(i));
            }
        }

        resultNFA.setEndList(NewEndList);
    
    return resultNFA;
    }

    /**
     * xy?
     */
    public NFAGraph nfaOnceOrNone(NFAGraph nfa1, NFAGraph nfa2){
        NFAGraph resultNFA = new NFAGraph();
        resultNFA.setStart(nfa1.getStart());

        ArrayList<Integer> resultNFAEndList = nfa1.getEndList();

        for (int i=0; i<nfa1.getGraphTable().size();i++){
            resultNFA.addGraphPath(nfa1.getGraphTable.get(i));
        }
        
        for(int i=0; i<nfa2.getEndList().size();i++){
            Integer item = nfa2.getEndList().get(i);
            if(item != nfa2.getStart()){
                resultNFAEndList.add(item);
            }
        }

        resultNFA.setEndList(resultNFAEndList);
        
        concatNFAGraph(nfa2, nfa1.getEndList(), nfa1.getGraphTable(), nfa2.getGraphTable(), resultNFA);

        return resultNFA;
    }

    /**
     * xy*
     */
    public NFAGraph nfaRepeatOrNone(NFAGraph nfa1, NFAGraph nfa2){
        NFAGraph resultNFA = new NFAGraph();

        resultNFA.setEndList(nfa1.getEndList());
        resultNFA.setStart(nfa1.getStart());

        Integer nfa2Start = nfa2.getStart();

        ArrayList<Integer> nfa1EndList = nfa1.getEndList();
        ArrayList<Integer> nfa2EndList = nfa2.getEndList();

        for(int i=0;i<nfa1.getGraphTable().size();i++){
            resultNFA.addGraphPath(nfa1.getGraphTable().get(i));
        }

        for(int i=0;i<nfa1EndList.size();i++){
            Integer currentNfa1End = nfa1EndList.get(i);
            
            for(int j=0;j<nfa2.getGraphTable().size();j++){
                NFAGraphPath path = nfa2.getGraphTable().get(j);
                
                Integer pathOrig = path.getOrig();
                Integer pathDest = path.getDest();

                if(pathOrig == nfa2.getStart()){
                    pathOrig = currentNfa1End;
                }
                
                if(nfa2EndList.contains(pathDest)){
                    pathDest = currentNfa1End;
                }

                path = new NFAGraphPath((int)pathOrig,(int) pathDest, path.getPatt());

                if (!resultNFA.getGraphTable().contains(path)){
                    resultNFA.addGraphPath(path);
                }
            
            }
        }

        return resultNFA;
    
    }
}
    
/*

*/