lg.py

################################################################
# lg.py - Label Graph Class
#
# Authors: R. Zanibbi and H. Mouchere, 2012
# Copyright (c) 2012-2014 Richard Zanibbi and Harold Mouchere
################################################################
import csv
import sys
import math
import copy
import os
from collections import OrderedDict
from smallGraph import SmallGraph
from compareTools import cmpNodes, cmpEdges

class Lg(object):
    """Class for bipartite graphs where the two node sets are identical, and
    multiple node and edge labels are permited. The graph and individual nodes
    and edges have associated values (e.g. weights/probabilities)."""

# Define graph data elements ('data members' for an object in the class)
    __slots__ = ('file','gweight','nlabels','elabels','error','absentNodes',\
                    'absentEdges','hiddenEdges', 'cmpNodes', 'cmpEdges')

##################################
# Constructors (in __init__)
##################################
    def __init__(self,*args): 
        """Graph data is read from a CSV file or provided node and edge label
        dictionaries.  If invalid entries are found, the error flag is set to
        true, and graph input continues.  In .lg files, blank lines are
        ignored, and # may be used for comment lines in CSV graph files."""
        self.error = False
        self.gweight = 1.0
        # self.nlabels = {}
        # self.elabels = {}
        self.nlabels = OrderedDict()
        self.elabels = OrderedDict()
        self.absentNodes = set([])
        self.absentEdges = set([])
        self.hiddenEdges = {}
        self.cmpNodes = cmpNodes
        self.cmpEdges = cmpEdges

        
        fileName = None
        nodeLabels = {}
        edgeLabels = {}
        
        validAsteriskEdges = set()
        invalidAsteriskNodes = set()

        if len(args) == 1:
            fileName = args[0]
            self.file = fileName # DEBUG: add filename for debugging purposes.
        elif len(args) == 2:
            nodeLabels = args[0]
            edgeLabels = args[1]

        if fileName == None:
            # CONSTRUCTOR 1: try to read in node and edge labels.
            self.file = None
            # Automatically convert identifiers and labels to strings if needed.
            for nid in list(nodeLabels):
                if not isinstance(nid, str):
                    nid = str(nid)

                newdict = {}
                for label in list(nodeLabels[nid]):
                    if not isinstance(nid, str):
                        label = str(label)
            
                    # Weights need to be floats.
                    if not isinstance( nodeLabels[nid][label], float ):
                        self.error = True
                        sys.stderr.write('  !! Invalid weight for node ' + nid + ', label \"' \
                                            + label +"\": " + str(nodeLabels[nid][label]) + "\n")
                    newdict[ label ] = nodeLabels[nid][label]
                self.nlabels[nid] = newdict

            # WARNING: self-edges are not detected if edge labels used
            # for initialization.
            for eid in list(edgeLabels):
                if not isinstance(eid[0], str) or not isinstance(eid[1],str):
                    eid[0] = str(eid[0])
                    eid[1] = str(eid[1])

                newdict = {}
                for label in list(edgeLabels[eid]):
                    if not isinstance(label, str):
                        label = str(label)
                    if not isinstance( edgeLabels[eid][label], float ):
                        self.error = True
                        sys.stderr.write('  !! Invalid weight for edge ' + str(eid) + ', label \"' \
                                            + label +"\": " + str(edgeLabels[eid][label]) + "\n")
                    newdict[ label ] = edgeLabels[eid][label]

                self.elabels[eid] = newdict
        else:
            # CONSTRUCTOR 2: Read graph data from CSV file.
            MIN_NODE_ENTRY_LENGTH = 3
            MIN_EDGE_ENTRY_LENGTH = 4
            MIN_OBJECT_ENTRY_LENGTH = 5
            MIN_OBJECT_EDGE_ENTRY_LENGTH = 5
            try:
                    fileReader = csv.reader(open(fileName))
            except:
                    # Create an empty graph if a file cannot be found.
                    # Set the error flag.
                    sys.stderr.write('  !! IO Error (cannot open): ' + fileName + '\n')
                    self.error = True
                    return
            objectDict = dict([])
            for row in fileReader:
                    # Skip blank lines.
                    if len(row) == 0 or len(row) == 1 and row[0].strip() == '':
                            continue

                    entryType = row[0].strip()
                    if entryType == 'N':
                            if len(row) < MIN_NODE_ENTRY_LENGTH:
                                    sys.stderr.write(' !! Invalid node entry length: ' +str(len(row))+\
                                                    '\n\t' + str(row) + '\n')
                                    self.error = True
                            else:
                                    nid = row[1].strip() # remove leading/trailing whitespace
                                    if nid in list(self.nlabels):
                                            nlabelDict = self.nlabels[ nid ]
                                            nlabel = row[2].strip()
                                            # if nlabel in nlabelDict:
                                                    # # Note possible error.
                                                    # sys.stderr.write(' !! Repeated node label entry ('\
                                                                    # + self.file + '): ' \
                                                                    # + '\n\t' + str(row) + '\n')
                                                    # self.error = True
                                            # Add (or replace) entry for the label.
                                            nlabelDict[ nlabel ] = float(row[3])
                                    else:
                                            # New primitive; create new dictionary for 
                                            # provided label (row[2]) and value (row[3])
                                            nid = row[1].strip()
                                            nlabel = row[2].strip()

                                            # Feb. 2013 - allow no weight to be provided.
                                            if len(row) > MIN_NODE_ENTRY_LENGTH:
                                                    self.nlabels[ nid ] = { nlabel : float(row[3]) }
                                            else:
                                                    self.nlabels[ nid ] = { nlabel : 1.0 }

                    elif entryType == 'E':
                            if len(row) < MIN_EDGE_ENTRY_LENGTH:
                                    sys.stderr.write(' !! Invalid edge entry length: ' +str(len(row))+\
                                                    '\n\t' + str(row) + '\n')
                                    self.error = True
                            else:
                                    primPair = ( row[1].strip(), row[2].strip() )
                                    #self to self edge = error
                                    if primPair[0] == primPair[1]:
                                            sys.stderr.write('  !! Invalid self-edge (' +
                                                            self.file + '):\n\t' + str(row) + '\n')
                                            self.error = True
                                            nid = primPair[0]
                                            if nid in list(self.nlabels):
                                                    nlabelDict = self.nlabels[ nid ]
                                                    nlabel = row[3].strip()
                                                    # if nlabel in nlabelDict:
                                                            # # Note possible error.
                                                            # sys.stderr.write(' !! Repeated node label entry ('\
                                                                    # + self.file + '): ' \
                                                                    # + '\n\t' + str(row) + '\n')
                                            # Add (or replace) entry for the label.
                                            nlabelDict[ nlabel ] = float(row[4])

                                    #an edge already existing, add a new label
                                    elif primPair in list(self.elabels):
                                            elabelDict = self.elabels[ primPair ]
                                            elabel = row[3].strip()
                                            # if elabel in elabelDict:
                                                    # # Note possible error.
                                                    # sys.stderr.write(' !! Repeated edge label entry (' \
                                                                    # + self.file + '):\n\t' + str(row) + '\n')
                                                    # self.error = True
                                            if elabel == '*':
                                                    # if using old fashion segmentation label, convert it by finding the (only) node label
                                                    if primPair[0] in self.nlabels and primPair[1] in self.nlabels and \
                                                    self.nlabels[ primPair[0]] == self.nlabels[ primPair[1]]:
                                                            elabel =  list(self.nlabels[ primPair[0]])[0]
                                                            
                                                            validAsteriskEdges.add( primPair )

                                                    else:
                                                            sys.stderr.write(' !! * edge used with ambiguous node labels (' \
                                                                    + str(self.nlabels[ primPair[0]]) + ' vs. ' \
                                                                    + str(self.nlabels[ primtPair[1]]) + ') in ' \
                                                                    + self.file + '):\n\t' + ", ".join(row) + '\n')
                                                            
                                                            # RZ: Oct. 14 - cheap and dirty correction.
                                                            elabel = 'MergeError'
                                                            self.nlabels[ primPair[0] ] = { elabel : 1.0 }
                                                            self.nlabels[ primPair[1] ] = { elabel : 1.0 }