lg.py

################################################################
# lg.py - Bipartitite Graph Class
#
# Author: R. Zanibbi, June 2012
# Copyright (c) 2012, Richard Zanibbi and Harold Mouchere
################################################################
import csv
import sys
import math
import copy
import smallGraph
import compareTools

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 = {}
		
		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: ' \
								'\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: ' \
								'\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 it uses the 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]
								else:
									sys.stderr.write(' !! * used but ambiguous label in nodes (' \
										+ self.file + '):\n\t' + str(row) + '\n')
									self.error = True
			
			# Add (or replace) entry for the label.
							# Feb. 2013 - allow no weight.
							if len(row) > MIN_EDGE_ENTRY_LENGTH:
								elabelDict[ elabel ] = float(row[4])
							else:
								elabelDict[ elabel ] = 1.0
						else:
							# Add new edge label entry for the new edge label
							# as a dictionary.
							primPair = ( row[1].strip(), row[2].strip() )
							elabel = row[3].strip()
							if elabel == '*':# if it uses the 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]
								else:
									sys.stderr.write(' !! * used but ambiguous label in nodes (' \
										+ self.file + '):\n\t' + str(row) + '\n')
									self.error = True
							self.elabels[ primPair ] = { elabel : float(row[4]) }
				elif entryType == 'O':
					if len(row) < MIN_OBJECT_ENTRY_LENGTH:
						sys.stderr.write(' !! Invalid object entry length: ' \
								'\n\t' + str(row) + '\n')
						self.error = True
					else:
						rawnodeList = row[4:] # get all other item as node id
						oid =  row[1].strip()
						nlabel =  row[2].strip()
						nValue =  float(row[3].strip())
						nodeList = []
						# add all nodes
						for n in rawnodeList:
							nid = n.strip()
							nodeList.append(nid)
							if nid in self.nlabels.keys():
								nlabelDict = self.nlabels[ nid ]
								if nlabel in nlabelDict:
									# Note possible error.
									sys.stderr.write(' !! Repeated node label entry '+str(nid)+'('\
											+ self.file + '): ' \
											+ '\n\t' + str(row) + '\n')
									self.error = True
								# Add (or replace) entry for the label.
								nlabelDict[ nlabel ] = nValue
							else:
								# New primitive; create new dictionary for 
								# provided label and value 	
								# Feb. 2013 - allow no weight to be provided.
								self.nlabels[ nid ] = { nlabel : nValue }
						#save the nodes of this object
						objectDict[oid] = nodeList
						#add all edges
						for nid1 in nodeList:
							#nid1 = n1.strip()
							for nid2 in nodeList:
								#nid2 = n2.strip()
								if nid1 != nid2:
									primPair = ( nid1, nid2 )
									elabel = nlabel#'*' #segmentation
									if primPair in self.elabels.keys():
										elabelDict = self.elabels[ primPair ]
										if elabel in elabelDict:
											# Note possible error.
											sys.stderr.write(' !! Repeated edge label entry (' \
													+ self.file + '):\n\t' + str(row) + '\n')
											self.error = True
										else:
											# Add (or replace) entry for the label.
											elabelDict[ elabel ] = nValue
									else:
										# Add new edge label entry for the new edge label
										# as a dictionary.
										self.elabels[ primPair ] = { elabel : nValue }

				elif entryType == 'EO':
					if len(row) < MIN_OBJECT_EDGE_ENTRY_LENGTH:
						sys.stderr.write(' !! Invalid object entry length: ' \
								'\n\t' + str(row) + '\n')
						self.error = True
					else:
						oid1 = row[1].strip()
						oid2 = row[2].strip()
						elabel = row[3].strip()
						eValue = float(row[4].strip())
						if not oid1 in objectDict:
							sys.stderr.write(' !! Invalid object id: ' + oid1+\
								'\n\t' + str(row) + '\n')
							self.error = True
						if not oid2 in objectDict:
							sys.stderr.write(' !! Invalid object id: ' + oid2+\
								'\n\t' + str(row) + '\n')
							self.error = True
						if not self.error:
							nodeList1 = objectDict[oid1] # get all other item as node id
							nodeList2 = objectDict[oid2] # get all other item as node id

							for nid1 in nodeList1:
								for nid2 in nodeList2:
									if nid1 != nid2:
										primPair = ( nid1, nid2 )
										if primPair in self.elabels.keys():
											elabelDict = self.elabels[ primPair ]
											if elabel in elabelDict:
												# Note possible error.
												sys.stderr.write(' !! Repeated edge label entry (' \
														+ self.file + '):\n\t' + str(row) + '\n')
												self.error = True
											else:
												# Add (or replace) entry for the label.
												elabelDict[ elabel ] = eValue
										else:
											# Add new edge label entry for the new edge label
											# as dictionary.
											self.elabels[ primPair ] = { elabel : eValue }
									else:			
										sys.stderr.write('  !! Invalid self-edge (' +
										self.file + '):\n\t' + str(row) + '\n')
										self.error = True
				# DEBUG: complaints about empty lines here...
				elif len(entryType.strip()) > 0 and entryType.strip()[0] == '#':
					# Ignore lines with comments.
					pass
				else:
					sys.stderr.write('  !! Invalid graph entry type (expect N/E/O/EO): ' \
							+ str(row) + '\n')
					self.error = True
	
		# Add any implicit nodes in edges explicitly to the hash table
		# containing nodes. The 'nolabel' label is '_'.
		anonNode = False
		anodeList = []
		for elabel in self.elabels.keys():
			nid1 = elabel[0]
			nid2 = elabel[1]

			if not nid1 in self.nlabels.keys():
				self.nlabels[ nid1 ] = { '_' : 1.0 }
				anodeList = anodeList + [ nid1 ]
				anonNode = True
			if not nid2 in self.nlabels.keys():
				self.nlabels[ nid2 ] = { '_' : 1.0 }
				anodeList = anodeList + [ nid2 ]
				anonNode = True
		if anonNode:
			sys.stderr.write('  ** Anonymous labels created for:\n\t' \
				+ str(anodeList) + '\n')

	##################################
	# String, CSV output
	##################################
	def __str__(self):
		nlabelcount = 0
		elabelcount = 0
		for nid in self.nlabels.keys():
			nlabelcount = nlabelcount + len(self.nlabels[nid].keys())
		for eid in self.elabels.keys():
			elabelcount = elabelcount + len(self.elabels[eid].keys())

		return 'Nodes: ' + str(len(self.nlabels.keys())) \
				+ ' (labels: ' + str(nlabelcount) \
				+ ')   Edges: ' + str(len(self.elabels.keys())) \
				+ ' (labels: ' + str(elabelcount) \
				+ ')   Error: ' + str(self.error)

	def csv(self):
		"""Construct CSV data file representation as a string."""
		# NOTE: currently the graph value is not being stored...
		nlist = []
		elist = []
		for nkey in self.nlabels.keys():
			nodeLabels = self.nlabels[nkey]
			for nlabel in nodeLabels.keys():
				nstring = 'N,' + nkey + ',' + nlabel + ',' + \
						str(nodeLabels[nlabel]) + '\n'
				nlist = nlist + [ nstring ]

		for npair in self.elabels.keys():
			edgeLabels = self.elabels[npair]
			for elabel in edgeLabels.keys():
				estring = 'E,' + npair[0] + ',' + npair[1] + ',' + elabel + ',' + \
						str(edgeLabels[ elabel ]) + '\n'
				elist = elist + [ estring ]

		# Sort the node and edge strings lexicographically.
		# NOTE: this means that '10' precedes '2' in the sorted ordering
		nlist.sort()
		elist.sort() 
		sstring = ''
		for nstring in nlist:
			sstring = sstring + nstring
		sstring += "\n"
		for estring in elist:
			sstring = sstring + estring
		
		return sstring

	##################################
	# Construct segment-based graph
	# for current graph state
	##################################
	def segmentGraph(self):
		"""Return dictionaries from segments to strokes, strokes to segments,
		segments without parents, and edges labeled as segment ('*')."""
		primitiveSegmentMap = {}
		segmentPrimitiveMap = {}
		#noparentSegments = []
		segmentEdges = {}  # Edges between detected objects (segments)

		self.hideUnlabeledEdges()

		# Note: a segmentation edge in either direction merges a primitive pair.
		primSets = {}
		for node,labs in self.nlabels.items():
			primSets[node] = {}
			for l in labs:
				primSets[node][l] = set([node])
		for (n1, n2) in self.elabels.keys():
			commonLabels = set(self.nlabels[n1].keys()).intersection(self.nlabels[n2].keys(),self.elabels[(n1,n2)].keys())
			for l in commonLabels:
				primSets[n1][l].add(n2)
				primSets[n2][l].add(n1)
		# NOTE: Segments can have multiple label
		# warning: a primitive can belong to several different
		# segments with different sets of primitives and different label.
		# but there is only one segment with the same label attached to each primitive
		# (not possible to represent several segmentation hypothesis of the same symbol)
		i = 0
		segmentList = []
		rootSegments = set([])
		#for each label associated with each prim, there is a potential seg
		for primitive,segments in primSets.items():
			for lab in segments.keys():
				alreadySegmented = False
				for j in range(len(segmentList)):
					if segments[lab] == segmentList[j]["prim"]:
						if not primitive in primitiveSegmentMap:
							primitiveSegmentMap[ primitive ] = {}
						primitiveSegmentMap[ primitive ][lab] = 'seg' + str(j)
						alreadySegmented = True
						if lab not in segmentList[j]["label"]:
							segmentPrimitiveMap[  'seg' + str(j) ][1].append(lab)
							segmentList[j]["label"].add(lab)
						break

				if not alreadySegmented:
					# Add the new segment.
					newSegment = 'seg' + str(i)
					segmentList = segmentList + [ {"label":{lab},"prim":primSets[primitive][lab]} ]
					segmentPrimitiveMap[ newSegment ] = (segments[lab],[lab])
					if not primitive in primitiveSegmentMap:
							primitiveSegmentMap[ primitive ] = {}
					primitiveSegmentMap[ primitive ][lab] = newSegment
					rootSegments.add(newSegment)
					i += 1

		# Identify 'root' objects/segments (i.e. with no incoming edges),
		# and edges between objects. **We skip segmentation edges.
		
		for (n1, n2),elabs in self.elabels.items():
			segment1 = primitiveSegmentMap[n1]
			segment2 = primitiveSegmentMap[n2]
			#for all possible pair of segments with these two primitives, look for the effective relation labels
			possibleRelationLabels = set(elabs.keys()).difference(self.nlabels[n1].keys(),self.nlabels[n2].keys())
			if len(possibleRelationLabels) != 0:
				#for all pair of labels
				for l1,pset1 in segment1.items():
					for l2, pset2 in segment2.items():
						#if not in the same seg
						if pset1 != pset2:
							#look for the label which is common for all primitive pair in the two segments
							theRelationLab = possibleRelationLabels
							for p1 in primSets[n1][l1]:
								for p2 in primSets[n2][l2]:
									if(p1,p2) in self.elabels:
										theRelationLab &= set(self.elabels[(p1,p2)].keys())
									else:
										theRelationLab = set([]) # it should be a clique !
									if len(theRelationLab) == 0:
										break
								if len(theRelationLab) == 0:
									break
							# there is a common relation if theRelationLab is not empty
							if len(theRelationLab) != 0:
								#we can remove seg2 from the roots
								if pset2 in rootSegments:
									rootSegments.remove(pset2)
								#print (str((n1, n2))+ " => " + str(( pset1,  pset2)) + "  = " + str(theRelationLab))
								for label in theRelationLab:
									if ( pset1,  pset2) in segmentEdges:
										if label in segmentEdges[ ( pset1,  pset2) ]:
											# Sum weights for repeated labels
											segmentEdges[ ( pset1,  pset2)][label] += \
													self.elabels[(n1,n2)][label]
										else:
											# Add unaltered weights for new edge labels
											segmentEdges[ ( pset1,  pset2) ][label] = \
													self.elabels[(n1,n2)][label]
									else:
										segmentEdges[ ( pset1, pset2) ] = {}
										segmentEdges[ ( pset1, pset2) ][label] = \
												self.elabels[(n1,n2)][label]

		self.restoreUnlabeledEdges()

		return (segmentPrimitiveMap, primitiveSegmentMap, list(rootSegments), \
				segmentEdges)


	##################################
	# Metrics and Graph Differences
	##################################
	def compareSegments(self, lg2):
		"""Compute the number of differing segments, and record disagreements.
		The primitives in each graph should be of the same number and names
		(identifiers). Nodes are merged that have identical (label,value)
		pairs on nodes and all incoming and outgoing edges."""
		(sp1, ps1, _, sre1) = self.segmentGraph()
		(sp2, ps2, _, sre2) = lg2.segmentGraph()
		#byValue = lambda pair: pair[1]  # define key for sort comparisons.

		allNodes = set(ps1.keys())
		#FIX : this this not the case in spare representation 
		assert allNodes == set(ps2.keys())
	
		edgeDiffCount = 0
		segDiffs = {}
		correctSegments = set([])
		correctSegmentsAndClass = set([])
		# list and count the edges errors which are due to segmentation errors
		# use cmpNodes to compare the labels of symbols
		# idea : build the sub graph with the current primitive as center and only 
		for primitive in ps1.keys():
			# Make sure to skip primitives that were missing ('ABSENT'),
			# as in that case the graphs disagree on all non-identical node
			# pairs for this primitive, and captured in self.absentEdges.
			# if not 'ABSENT' in self.nlabels[primitive] and \
					# not 'ABSENT' in lg2.nlabels[primitive]:
				#the 2 sub graphs
				edgeFromP1 = {}
				edgeFromP2 = {}
				for (lab1,seg1) in ps1[primitive].items():
					for p in sp1[seg1][0]:
						if p != primitive:
							if p in edgeFromP1:
								edgeFromP1[p].append(lab1)
							else:
								edgeFromP1[p] = [lab1]
	
				for (lab2,seg2) in ps2[primitive].items():
					for p in sp2[seg2][0]:
						if p != primitive:
							if p in edgeFromP2:
								edgeFromP2[p].append(lab2)
							else:
								edgeFromP2[p] = [lab2]

				# Compute differences in edges labels with cmpNodes (as they are symbol labels)
				diff1 = set([])
				diff2 = set([])
				# first add differences for shared primitives
				commonPrim = set(edgeFromP1.keys()).intersection(edgeFromP2.keys())
				for p in commonPrim:
					(cost,diff) = self.cmpNodes(edgeFromP1[p], edgeFromP2[p])
					edgeDiffCount = edgeDiffCount + cost
					if cost > 0: #by someway, they disagree, thus add in both sets
						diff1.add(p)
						diff2.add(p)
				#then add differences for primitives which are not is the other set
				for p in (set(edgeFromP1.keys()) - commonPrim):
					(cost,diff) = self.cmpNodes(edgeFromP1[p], [])
					edgeDiffCount = edgeDiffCount + cost
					diff1.add(p)
					
				for p in (set(edgeFromP2.keys()) - commonPrim):
					(cost,diff) = self.cmpNodes(edgeFromP2[p], [])
					edgeDiffCount = edgeDiffCount + cost
					diff2.add(p)
					

				# Only create an entry where there are disagreements.
				if len(diff1)+len(diff2) > 0:
					segDiffs[primitive] = ( diff1, diff2 )
				
				# look for correct segments, ie primitive sets which are the same in both graphs
				#NOTE: even if this algorithm is not symmetric, the result is symmetric
				# print ("ps1="+str(ps1))
				# print ("ps2="+str(ps2))
				for (lab1,seg1) in ps1[primitive].items():
					#print ("pour "+ str((lab1,seg1)))
					if(seg1, lab1) not in correctSegmentsAndClass: # already found, no need to search
						for (lab2,seg2) in ps2[primitive].items():
							# print ("  > pour "+ str((lab2,seg2)))
							# print ("  >   " + str(sp1[seg1][0]) + "vs"+str(sp2[seg2][0]))
							if sp1[seg1][0] == sp2[seg2][0]:
								# print ("OK"+str((seg1, lab1)))
								correctSegments.add(seg1)
								(cost,_) = self.cmpNodes([lab1],[lab2]) # do not use spX[segX][1] because we can want to count each correct label as 1 even if there is an error in some labels in the same set
								if (cost == 0):
									correctSegmentsAndClass.add((seg1, lab1))

			# DEBUG: don't record differences for a single node.
			# elif 'ABSENT' in self.nlabels[primitive] \
					# and len(self.nlabels.keys()) > 1:
				# If node was missing in this graph, treat this graph as having
				# the opposite segmentation relationship of that in the other 
				# graph - in other words, total error, with all pairs incorrect.
				# DEBUG: We are trying to define the opposite of the edges
				# in the other graph in the case of an absent node.
				# allOtherNodes = allNodes.difference(set([primitive]))
				# ographSegPrimSet = set((sp2[ ps2[primitive] ])[0]).difference(set([primitive]))
				# ediff = allOtherNodes.difference(ographSegPrimSet)
				# edgeDiffCount = edgeDiffCount + len(ediff) + \
						# len(ographSegPrimSet)
				# segDiffs[primitive] = ( ediff, ographSegPrimSet )
				
				#version CROHME
				# ographSegPrimSet = set((sp2[ ps2[primitive] ])[0]).difference(set([primitive]))
				# ediff = set([primitive])
				# edgeDiffCount = edgeDiffCount + len(ographSegPrimSet)
				# segDiffs[primitive] = ( ediff, ographSegPrimSet )

			# DEBUG: don't record differences for a single node.
			# elif len(self.nlabels.keys()) > 1:
				# Similar, for case where node is missing in lg2.
				# allOtherNodes = allNodes.difference(set([primitive]))
				# graphSegPrimSet = set((sp1[ ps1[primitive] ])[0]).difference(set([primitive]))
				# ediff = allOtherNodes.difference(graphSegPrimSet)
				# segDiffs[primitive] = ( graphSegPrimSet, ediff )
				# edgeDiffCount = edgeDiffCount + len(ediff) + \
						# len(graphSegPrimSet)

				# version CROHME
				# graphSegPrimSet = set((sp1[ ps1[primitive] ])[0]).difference(set([primitive]))
				# ediff = set([primitive])
				# segDiffs[primitive] = ( graphSegPrimSet, ediff )
				# edgeDiffCount = edgeDiffCount + len(graphSegPrimSet)

		# Compute metrics 
		#print (str(sp2))

		metrics = [ ("SegError", len(sp2.keys()) - len(correctSegments) ) ]
		metrics = metrics + [ ("CorrectSegments", len(correctSegments) ) ]
		metrics = metrics + [ ("CorrectSegmentsAndClass", len(correctSegmentsAndClass)) ]
		nbSegmClass = 0
		for (_,labs) in sp2.items():
			nbSegmClass += len(labs[1])
		metrics = metrics + [ ("ClassError", nbSegmClass - len(correctSegmentsAndClass)) ] 
		metrics = metrics + [ ("nSeg", len(sp2.keys()) - len(lg2.absentNodes)) ] 
		metrics = metrics + [ ("detectedSeg", len(sp1.keys())) ]

		# Metrics for edges over segments (number and detected...)
		#metrics = metrics + [ ("nSegRelEdges", len(sre2.keys()) - len(lg2.absentEdges)) ]
		metrics = metrics + [ ("dSegRelEdges", len(sre1.keys())) ]

		# Compute the specific 'segment-level' graph edges that disagree, at the
		# level of primitive-pairs. This means that invalid segmentations may
		# still have valid layouts in some cases.
		primRelErrors = 0
		segRelErrors = 0
		primRelEdgeDiffs = {}
		#segRelMatched = set([])
		
		for thisPair in sre1.keys():
			thisParentIds = set(sp1[ thisPair[0] ][0])
			thisChildIds = set(sp1[thisPair[1] ][0])

			# A 'correct' edge has the same label between all primitives
			# in the two segments.
			error = False
			for parentId in thisParentIds:
				for childId in thisChildIds:
					# DEBUG: compare only label sets, not values.
					if not (parentId, childId) in lg2.elabels.keys() or \
						    not ((0,[]) == self.cmpEdges(self.elabels[ (parentId, childId) ].keys(),lg2.elabels[ (parentId, childId) ].keys())):
#					   not set(self.elabels[ (parentId, childId) ].keys())  == \
#							set(lg2.elabels[ (parentId, childId) ].keys()):
						error = True
						primRelErrors += 1
						primRelEdgeDiffs[ thisPair ] = [ ('Error',1.0) ]
						continue

			# RZ DEBUG: count primitive edge errors separately from segment (i.e whole objects/symbols)
			if error:
				segRelErrors += 1
			self.error |= error
		metrics = metrics + [ ("SegRelErrors", segRelErrors) ]
		metrics = metrics + [ ("PrimitiveRelErrors", primRelErrors) ]

		return (edgeDiffCount, segDiffs, correctSegments, metrics, primRelEdgeDiffs)

	def compare(self, lg2):
		"""Returns: 1. a list of (metric,value) pairs,
		2. a list of (n1,n2) node disagreements, 3. (e1,e2) pairs
		for edge disagreements, 4. dictionary from primitives to
		disagreeing segment graph edges for (self, lg2). Node and 
		edge labels are compared using label sets without values, and
		*not* labels sorted by value."""
		metrics  = []
		nodeconflicts = []
		edgeconflicts = []
		#byValue = lambda pair: pair[1]  # define key for sort comparisons.

		# FIX number of nodes as number in reference (lg2)
		# For evaluation relative to ground truth, this is more appropriate
		# than the (possibly expanded) number of targets after resolving
		# absent nodes in both directions. Does lead to risk of negative
		# accuracies (more errors than targets).
		# FIXED ( HM ) use the union of all nodes label instead of only lg2 ones
		#    it change the nlabelMismatch, nodeClassError and so D_C and all rates values
		# numNodes = len(lg2.nlabels.keys())
		allNodes = set(lg2.nlabels.keys()).union(self.nlabels.keys())
		numNodes = len(allNodes)
		(sp2, ps2, _, sre2) = lg2.segmentGraph()
		nSegRelEdges = len(sre2)

		# Handle case of empty graphs, and missing primitives.
		# SIDE EFFECT: 'ABSENT' nodes and edges added to each graph.
		self.matchAbsent(lg2)

		# METRICS
		# Node and edge labels are considered as sets.
		#numNodes = len(self.nlabels.keys())
		nlabelMismatch = 0
		numEdges = numNodes * (numNodes - 1)  # No self-edges.
		numLabels = numNodes + numEdges
		elabelMismatch = 0

		# Mismatched nodes.
		nodeClassError = set()
		for nid in allNodes: #self.nlabels.keys():
			(cost,errL) = self.cmpNodes(self.nlabels[nid].keys(),lg2.nlabels[nid].keys())
			#if there is some error
			if cost > 0:
				# add mismatch
				nlabelMismatch = nlabelMismatch + cost
				# add errors in error list
				for (l1,l2) in errL:
					nodeconflicts = nodeconflicts + [ (nid, [ (l1, 1.0) ], [(l2, 1.0)] ) ]
				# add node in error list
				nodeClassError = nodeClassError.union([nid])

		# Two-sided comparison of *label sets* (look from absent edges in both
		# graphs!) Must check whether edge exists; '_' represents a "NONE"
		# label (no edge).

		# Identify the set of nodes with disagreeing edges.
		# (RZ: Nov. 2012)
		nodeEdgeError = set()
		for (graph,oGraph) in [ (self,lg2), (lg2,self) ]:
			for npair in graph.elabels.keys():
				if not npair in oGraph.elabels \
						and (not graph.elabels[ npair ] == ['_']):
					(cost,errL) = self.cmpEdges(graph.elabels[ npair ].keys(),['_'])
					elabelMismatch = elabelMismatch + cost

					(a,b) = npair
					# Record nodes in invalid edge
					nodeEdgeError.update([a,b])

					# DEBUG: Need to indicate correctly *which* graph has the
					# missing edge; this graph (1st) or the other (listed 2nd).
					conflictList = []
					if graph == self:
						for (l1,l2) in errL:
							edgeconflicts.append((npair, [ (l1, 1.0) ], [(l2, 1.0)] ) )
					else:
						for (l1,l2) in errL:
							edgeconflicts.append((npair, [ (l2, 1.0) ], [(l1, 1.0)] ) )

					edgeconflicts.extend(conflictList)
					
		# Obtain number of primitives with an error of any sort.
		nodeError = nodeClassError.union(nodeEdgeError)

		# One-sided comparison for common edges. Compared by cmpEdges
		for npair in self.elabels.keys():
			if npair in lg2.elabels.keys():
				(cost,errL) = self.cmpEdges(self.elabels[npair].keys(),lg2.elabels[npair].keys())
				if cost > 0:
					elabelMismatch = elabelMismatch + cost
					(a,b) = npair
					# Record nodes in invalid edge
					nodeEdgeError.update([a,b])
					for (l1,l2) in errL:
						edgeconflicts.append((npair, [ (l1, 1.0) ], [(l2, 1.0)] ) )

		# Now compute segmentation differences.
		(segMismatch, segDiffs, correctSegs, scMetrics, segRelDiffs) \
				= self.compareSegments(lg2)

		# UNDIRECTED/NODE PAIR METRICS
		# Compute number of invalid nodePairs
		badPairs = {}
		for ((n1, n2), _, _) in edgeconflicts:
			if not (n2, n1) in badPairs:
				badPairs[(n1, n2)] = True
		incorrectPairs = len(badPairs)

		# Compute number of mis-segmented node pairs.
		badSegPairs = set([])
		for node in segDiffs.keys():
			for other in segDiffs[node][0]:
				if node != other and (other, node) not in badSegPairs:
					badSegPairs.add((node, other))
			for other in segDiffs[node][1]:
				if  node != other and (other, node)not in badSegPairs:
					badSegPairs.add((node, other))
		segPairErrors = len(badSegPairs)

		# Compute performance metrics; avoid divisions by 0.
		cerror = ("D_C", nlabelMismatch) 
		cnerror = ("D_C(%)",0.0)
		if numNodes > 0:
			cnerror = ("D_C(%)", float(nlabelMismatch) / numNodes)
		rerror = ("D_L", elabelMismatch) 
		rnerror = ("D_L(%)", 0.0)
		snerror = ("D_S(%)", 0.0)
		if numEdges > 0:
			rnerror = ("D_L(%)", float(elabelMismatch) / numEdges)
			snerror = ("D_S(%)", float(segMismatch) / numEdges)
		serror = ("D_S", segMismatch) 
		aerror = ("D_B", nlabelMismatch + elabelMismatch) 

		anerror = ("D_Bn(%)",0.0)
		if numLabels > 0:
			anerror = ("D_Bn(%)", float(nlabelMismatch + elabelMismatch)/numLabels)

		
		# DEBUG:
		# Delta E BASE CASE: for a single node, which is absent in the other
		# file, set label and segment edge mismatches to 1 (in order
		# to obtain 1.0 as the error metric, i.e. total error).
		if len(self.nlabels.keys()) == 1 and \
				(len(self.absentNodes) > 0 or \
				len(lg2.absentNodes) > 0):
			elabelMismatch = 1
			segMismatch = 1
		
		errorVal = 0.0
		if numEdges > 0:
			errorVal +=  math.sqrt(float(segMismatch) / numEdges) + \
					 math.sqrt(float(elabelMismatch) / numEdges)
		if numNodes > 0:
			errorVal += float(nlabelMismatch) / numNodes
		errorVal = errorVal / 3.0
		eerror  = ("D_E(%)", errorVal)
	
	#eerror = ("D_E(%)", \
	#				(float(nlabelMismatch) /  numNodes +
	#				 math.sqrt(float(segMismatch) / numEdges) +
	#				 math.sqrt(float(elabelMismatch) / numEdges)) / 3.0)

		# Compile metrics
		metrics = metrics + [ cerror,  serror, rerror, anerror,\
				eerror, cnerror, snerror, rnerror, aerror, \
				("nNodes",numNodes), ("nEdges", numEdges), \
				("nSegRelEdges", nSegRelEdges), \
				("dPairs",incorrectPairs),("segPairErrors",segPairErrors),
				("nodeCorrect", numNodes - len(nodeError))]
		metrics = metrics + scMetrics

		return (metrics, nodeconflicts, edgeconflicts, segDiffs, correctSegs,\
				segRelDiffs)
		
	##################################
	# Manipulation/'Mutation'
	##################################
	def separateTreeEdges(self):
		"""Return a list of root nodes, and two lists of edges corresponding to 
		tree/forest edges, and the remaining edges."""

		# First, obtain segments; perform extraction on edges over segments.
		(segmentPrimitiveMap, primitiveSegmentMap, noparentSegments, \
				segmentEdges) = self.segmentGraph()

		# Collect parents and children for each node; identify root nodes.
		# (NOTE: root nodes provided already as noparentSegments)
		nodeParentMap = {}
		nodeChildMap = {}
		rootNodes = set(segmentPrimitiveMap.keys())
		for (parent, child) in segmentEdges:
			if not child in nodeParentMap.keys():
				nodeParentMap[ child ] = [ parent ]
				rootNodes.remove( child )
			else:
				nodeParentMap[ child ] += [ parent ]

			if not parent in nodeChildMap.keys():
				nodeChildMap[ parent ] = [ child ]
			else:
				nodeChildMap[ parent ] += [ child ]

		# Separate non-tree edges, traversing from the root.
		fringe = list(rootNodes)

		# Filter non-tree edges.
		nonTreeEdges = set([])
		while len(fringe) > 0:
			nextNode = fringe.pop(0)

			# Skip leaf nodes.
			if nextNode in nodeChildMap.keys():
				# DEBUG: need to copy the list of children, to avoid
				# missing child nodes as d.structures are updated.
				children = copy.deepcopy(nodeChildMap[ nextNode ])
				for child in children:
					numChildParents = len( nodeParentMap[ child ] )

					# Filter edges to children that have more than
					# one parent (i.e. other than nextNode)
					if numChildParents == 1:
						# Child in the tree found, put on fringe.
						fringe += [ child ]
					else:
						# Shift edge to non-tree status.
						nonTreeEdges.add((nextNode, child))

						nodeChildMap[ nextNode ].remove(child)
						nodeParentMap[ child ].remove(nextNode)

		# Generate the tree edges from remaining child relationships.
		treeEdges = []
		for node in nodeChildMap:
			for child in nodeChildMap[ node ]:
				treeEdges += [ (node, child) ]

		return (list(rootNodes), treeEdges, list(nonTreeEdges))
					
	def removeAbsent(self):
		"""Remove any absent edges from both graphs, and empty the fields
		recording empty objects."""
		for absEdge in self.absentEdges:
			del self.elabels[ absEdge ]

		for absNode in self.absentNodes:
			del self.nlabels[ absNode ]
		
		self.absentNodes = set([])
		self.absentEdges = set([])

	def addAbsent(self, lg2):
		"""Identify edges in other graph but not the current one."""
		selfNodes = set(self.nlabels.keys())
		lg2Nodes = set(lg2.nlabels.keys())
		self.absentNodes = lg2Nodes.difference(selfNodes)

		# WARN about absent nodes/edges; indicate that there is an error.
		if len(self.absentNodes) > 0:
			sys.stderr.write('  !! Inserting ABSENT nodes for:\n      ' \
					+ self.file + ' vs.\n      ' + lg2.file + '\n      ' \
				+ str(sorted(list(self.absentNodes))) + '\n')
			self.error = True

		# Add "absent" nodes.
		for missingNode in self.absentNodes:
			self.nlabels[ missingNode ] = { 'ABSENT': 1.0 }

		# Add edges for absent elements, to every node in 
		# the now-expanded node set.
		# for missingNode in self.absentNodes:
			# for node in self.nlabels.keys():
				# # Do not create self-edges.
				# if not missingNode == node:
					# self.elabels[ ( missingNode, node) ] = { 'ABSENT' : 1.0 }
					# self.absentEdges.add( (missingNode, node) )

	def matchAbsent(self, lg2):
		"""Add all missing primitives and edges between this graph and
		the passed graph. **Modifies both the object and argument graph lg2."""
		self.removeAbsent()
		self.addAbsent(lg2)

		lg2.removeAbsent()
		lg2.addAbsent(self)


	##################################
	# Routines for missing/unlabeled 
	# edges.
	##################################
	# Returns NONE: modifies in-place.
	def labelMissingEdges(self):
		for node1 in self.nlabels.keys():
			for node2 in self.nlabels.keys():
				if not node1 == node2:
					if not (node1, node2) in self.elabels.keys():
						self.elabels[(node1, node2)] = {'_' : 1.0 }

	# Returns NONE: modifies in-place.
	def hideUnlabeledEdges(self):
		"""Move all missing/unlabeled edges to the hiddenEdges field."""
		# Move all edges labeled '_' to the hiddenEdges field.
		for edge in self.elabels.keys():
			if set( self.elabels[ edge ].keys() ) == \
					set( [ '_' ] ):
				self.hiddenEdges[ edge ] = self.elabels[ edge ]
				del self.elabels[ edge ]

	def restoreUnlabeledEdges(self):
		"""Move all edges in the hiddenEdges field back to the set of
		edges for the graph."""
		for edge in self.hiddenEdges.keys():
			self.elabels[ edge ] = self.hiddenEdges[ edge ]
			del self.hiddenEdges[ edge ]

	##################################
	# Merging graphs
	##################################
	# RETURNS None (modifies 'self' in-place.)
	def merge(self, lg2, ncombfn, ecombfn):
		"""New node/edge labels are added from lg2 with common primitives. The
	   value for common node/edge labels updated using ncombfn and
	   ecombfn respectiveley: each function is applied to current values to
	   obtain the new value (i.e. v1' = fn(v1,v2))."""

		# Deal with non-common primitives/nodes.
		# DEBUG: make sure that all absent edges are treated as