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 smallGraph
import compareTools
import os

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.absentNodes = set([])
		self.absentEdges = set([])
		self.hiddenEdges = {}
		self.cmpNodes = compareTools.cmpNodes
		self.cmpEdges = compareTools.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 nodeLabels.keys():
				if not isinstance(nid, str):
					nid = str(nid)

				newdict = {}
				for label in nodeLabels[nid].keys():
					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 edgeLabels.keys():
				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 edgeLabels[eid].keys():
					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 self.nlabels.keys():
							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 self.nlabels.keys():
								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 self.elabels.keys():
							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]].keys())[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 }
									self.error = True

									invalidAsteriskNodes.add( primPair[0] )