lg.py

		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(list(segmentPrimitiveMap))
		for (parent, child) in segmentEdges:
			if not child in list(nodeParentMap):
				nodeParentMap[ child ] = [ parent ]
				rootNodes.remove( child )
			else:
				nodeParentMap[ child ] += [ parent ]

			if not parent in list(nodeChildMap):
				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 list(nodeChildMap):
				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(list(self.nlabels))
		lg2Nodes = set(list(lg2.nlabels))
		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.
		# NOTE: all edges to/from "absent" nodes are unlabeled.
		for missingNode in self.absentNodes:
			self.nlabels[ missingNode ] = { 'ABSENT': 1.0 }

	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 list(self.nlabels):
			for node2 in list(self.nlabels):
				if not node1 == node2:
					if not (node1, node2) in list(self.elabels):
						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 list(self.elabels):
			if set( list(self.elabels[ edge ]) ) == \
					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 list(self.hiddenEdges):
			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
		# 'hard' decisions (i.e. label ('_',1.0))
		self.matchAbsent(lg2)
		#self.labelMissingEdges()

		# Merge node and edgelabels.
		mergeMaps(self.nlabels, self.gweight, lg2.nlabels, lg2.gweight, \
				ncombfn)
		mergeMaps(self.elabels, self.gweight, lg2.elabels, lg2.gweight,\
				ecombfn)

				
	# RETURNS None: modifies in-place.
	def addWeightedLabelValues(self,lg2):
		"""Merge two graphs, adding the values for each node/edge label."""
		def addValues( v1, w1, v2, w2 ):
			return w1 * v1 + w2 * v2
		self.merge(lg2, addValues, addValues)
	
	# RETURNS None: modifies in-place.
	# HM: Added for IJDAR CROHME draft; invoke to filter a graph.
	# (currenly not used by default).
	def keepOnlyCorrectLab(self, gt):
		"""Keep only correct labels compared with the gt. Use the
		label ERROR_N and ERROR_E for node and edges errors. Use the 
		compareTools to compare the labels with ground truth."""
		
		allNodes = set(list(gt.nlabels)).union(list(self.nlabels))
		self.matchAbsent(gt)

		for nid in allNodes:
			(cost,_) = self.cmpNodes(list(self.nlabels[nid]),list(gt.nlabels[nid]))
			#if there is some error
			if cost > 0:
				self.nlabels[ nid ] = {'ERROR_N' : 1.0}
			else:
				self.nlabels[ nid ] = gt.nlabels[nid]

		for (graph,oGraph) in [ (self,gt), (gt,self) ]:
			for npair in list(graph.elabels):
				cost = 0;
				if not npair in oGraph.elabels:
					(cost,errL) = self.cmpEdges(list(graph.elabels[npair]),['_'])
				else:
					(cost,errL) = self.cmpEdges(list(graph.elabels[npair]),list(oGraph.elabels[npair]))
				if cost > 0:
					self.elabels[ npair ] = {'ERROR_E' : 1.0}
				else:
					if npair in gt.elabels:
						self.elabels[ npair ] = gt.elabels[npair]
					else:
						self.elabels[ npair ] =  {'_' : 1.0}

	# RETURNS None: modifies in-place.
	def selectMaxLabels(self):
		"""Filter for labels with maximum confidence. NOTE: this will
		keep all maximum value labels found in each map, e.g. if two
		classifications have the same likelihood for a node."""
		for object in list(self.nlabels):
			max = -1.0
			maxPairs = {}
			for (label, value) in self.nlabels[object].items():
				if value > max:
					max = value
					maxPairs = { label : value }
				elif value == max:
					maxPairs[label] = value

			self.nlabels[ object ] = maxPairs

		for edge in list(self.elabels):
			max = -1.0
			maxPairs = {}
			for (label, value) in self.elabels[edge].items():
				if value > max:
					max = value
					maxPairs = { label : value }
				elif value == max:
					maxPairs[label] = value

			self.elabels[ edge ] = maxPairs
	
	# RETURNS NONE: modifies in-place.
	def invertValues(self):
		"""Substract all node and edge label values from 1.0, to 
		invert the values. Attempting to invert a value outside [0,1] will
		set the error flag on the object."""
		for node in list(self.nlabels):
			for label in self.nlabels[ node ]:
				currentValue = self.nlabels[ node ][ label ] 
				if currentValue < 0.0 or currentValue > 1.0:
					sys.stderr.write('\n  !! Attempted to invert node: ' \
							+ node + ' label \"' \
							+ label + '\" with value ' + str(currentValue) + '\n')
					self.error = True
				else:
					self.nlabels[ node ][ label ] = 1.0 - currentValue

		for edge in list(self.elabels):
			for label in self.elabels[ edge ]:
				currentValue = self.elabels[ edge ][ label ]
				if currentValue < 0.0 or currentValue > 1.0:
					sys.stderr.write('\n  !! Attempted to invert edge: ' + \
							str(edge) + ' label \"' \
							+ label + '\" with value ' + str(currentValue) + '\n')
					self.error = True
				else:
					self.elabels[ edge ][ label ] = 1.0 - currentValue

	def subStructIterator(self, nodeNumbers):
		""" Return an iterator which gives all substructures with n nodes
		n belonging to the list depths"""
		if(isinstance(nodeNumbers, int)):
			nodeNumbers = [nodeNumbers]
		subStruct = []
		
		# Init the substruct with isolated nodes
		for n in list(self.nlabels):
			subStruct.append(set([n]))
			if 1 in nodeNumbers:
				yield smallGraph.SmallGraph([(n, "".join(list(self.nlabels[n])))], [])
		
		for d in range(2,max(nodeNumbers)+1):
			#add one node to each substructure
			newSubsS = set([])
			newSubsL = []
			for sub in subStruct:
				le = getEdgesToNeighbours(sub,list(self.elabels))
				for (f,to) in le:
					new = sub.union([to])
					lnew = list(new)
					lnew.sort()
					snew = ",".join(lnew)
					
					if(not snew in newSubsS):
						newSubsS.add(snew)
						newSubsL.append(new)
						if d in nodeNumbers:
							yield self.getSubSmallGraph(new)
			
			# ??? BUG ???
			subStruct = newSubsL
			
	def getSubSmallGraph(self, nodelist):
		"""Return the small graph with the primitives in nodelist and all edges 
		between them. The used label is the merged list of labels from nodes/edges"""
		sg = smallGraph.SmallGraph()
		for n in nodelist:
			sg.nodes[n] = list(self.nlabels[n])
		for e in getEdgesBetweenThem(nodelist,list(self.elabels)):
			sg.edges[e] = list(self.elabels[e])
		return sg
		
	# Compare the substructure
	def compareSubStruct(self, olg, depths):
		"""Return the list of couple of substructure which disagree
		the substructure from self are used as references"""
		allerrors = []
		for struc in olg.subStructIterator(depths):
				sg1 = self.getSubSmallGraph(list(struc.nodes))
				if(not (struc == sg1)):		
					allerrors.append((struc,sg1))
		return allerrors
	
	def compareSegmentsStruct(self, lgGT,depths):
		"""Compute the number of differing segments, and record disagreements
		in a list. 
		The primitives in each subgraph should be of the same number and names
		(identifiers). Nodes are merged that have identical (label,value) pairs
		on nodes and all identical incoming and outgoing edges.  If used for
		classification evaluation, the ground-truth should be lgGT.  The first
		key value of the matrix is the lgGT obj structure, which gives the
		structure of the corresponding primitives which is the key to get the
		error structure in self.""" 
		(sp1, ps1, _, sre1) = self.segmentGraph()
		(spGT, psGT, _, sreGT) = lgGT.segmentGraph()

		segDiffs = set()
		correctSegments = set()
		for primitive in list(psGT):
			# 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.

			# RZ: Assuming one level of structure here; modifying for
			#     new data structures accomodating multiple structural levels.
			obj1Id = ps1[primitive][ list(ps1[primitive])[0] ]
			obj2Id = psGT[primitive][ list(psGT[primitive])[0] ]

			if not 'ABSENT' in self.nlabels[primitive] and \
					not 'ABSENT' in lgGT.nlabels[primitive]:
				# Obtain sets of primitives sharing a segment for the current
				# primitive for both graphs.
				# Each of sp1/spGT are a map of ( {prim_set}, label ) pairs.

				segPrimSet1 = sp1[ obj1Id ][0]
				segPrimSet2 = spGT[ obj2Id ][0]
				
				# Only create an entry where there are disagreements.
				if segPrimSet1 != segPrimSet2:
					segDiffs.add( ( obj2Id, obj1Id) )
				else:
					correctSegments.add( obj2Id )
			
			# DEBUG: don't record differences for a single node.
			elif len(list(self.nlabels)) > 1:
				# If node was missing in this graph or the other, treat 
				# this graph as having a missing segment
				# do not count the segment in graph with 1 primitive
				segDiffs.add(( obj2Id, obj1Id ) )

		# now check if the labels are identical
		for seg in correctSegments:
			# Get label for the first primtives (all primitives have identical
			# labels in a segment).
			# DEBUG: use only the set of labels, not confidence values.
			firstPrim = list(spGT[seg][0])[0]
			(cost, diff) = self.cmpNodes(list(self.nlabels[ firstPrim ]),list(lgGT.nlabels[ firstPrim ]))

			segId1 = ps1[firstPrim][ list(ps1[ firstPrim ])[0] ]
			segId2 = psGT[firstPrim][ list(psGT[ firstPrim ])[0] ]
			
			if (0,[]) != (cost, diff):
				segDiffs.add(( segId2, segId1) )
		allSegWithErr = set([p for (p,_) in segDiffs])
		
		# start to build the LG at the object level
		# add nodes for object with the labels from the first prim
		lgObj = Lg()
		for (sid,lprim) in spGT.items():
			lgObj.nlabels[sid] = lgGT.nlabels[list(lprim[0])[0]]

		# 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.
		# Add also the edges in the smallGraph
		segEdgeErr = set()
		for thisPair in list(sreGT):
			# TODO : check if it is sp1[thisPair[0]] instead of sp1[thisPair[0]][0]
			thisParentIds = set(spGT[ thisPair[0] ][0])
			thisChildIds = set(spGT[thisPair[1] ][0])
			lgObj.elabels[thisPair] = lgGT.elabels[ (list(thisParentIds)[0], list(thisChildIds)[0])]
			
			# A 'correct' edge has the same label between all primitives
			# in the two segments.
			# NOTE: we are not checking the consitency of label in each graph
			#  ie if all labels from thisParentIds to thisChildIds in self are 
			# the same 
			for parentId in thisParentIds:
				for childId in thisChildIds:
					# DEBUG: compare only label sets, not values.
					if not (parentId, childId) in list(self.elabels) or \
					   (0,[]) != self.cmpEdges(list(self.elabels[ (parentId, childId) ]), list(lgGT.elabels[ (parentId, childId) ])):
						segEdgeErr.add(thisPair)
						continue
		
		listOfAllError = []
		for smg in lgObj.subStructIterator(depths):
			#if one segment is in the segment error set
			showIt = False
			if len(set(list(smg.nodes)).intersection(allSegWithErr)) > 0:
				showIt = True
			for pair in list(smg.edges):
				if pair in segEdgeErr:
					showIt = True
					continue
			if showIt:
				#build the smg for the prim from lgGT
				allPrim = []
				for s in list(smg.nodes):
					allPrim.extend(spGT[s][0])
				
				smgPrim1 = self.getSubSmallGraph(allPrim)
				smgPrimGT = lgGT.getSubSmallGraph(allPrim)
				listOfAllError.append((smg,smgPrimGT,smgPrim1))
		
		return listOfAllError 

################################################################
# Utility functions
################################################################
def mergeLabelLists(llist1, weight1, llist2, weight2, combfn):
	"""Combine values in two label lists according to the passed combfn
	function, and passed weights for each label list."""
	# Combine values for each label in lg2 already in self.
	allLabels = set(llist1.items())\
			.union(set(llist2.items()))
	# have to test whether labels exist
	# in one or both list.
	for (label, value) in allLabels:
		if label in list(llist1) and \
				label in list(llist2):
			llist1[ label ] = \
				combfn( llist1[label], weight1,\
						llist2[label], weight2 )
		elif label in list(llist2):
			llist1[ label ] = \
				weight2 * llist2[label]
		else:
			llist1[ label ] = \
				weight1 * llist1[label]


def mergeMaps(map1, weight1, map2, weight2, combfn):
	"""Combine values in two maps according to the passed combfn
	function, and passed weights for each map."""
	# Odds are good that there are built-in function for this
	# operation.
	objects1 = list(map1)
	objects2 = list(map2)
	allObjects = set(objects1).union(set(objects2))
	for object in allObjects:
		if object in objects1 and object in objects2:
			# Combine values for each label in lg2 already in self.
			mergeLabelLists(map1[object],weight1, map2[object], weight2, combfn )			
		# DEBUG: no relationship ('missing') edges should
		# be taken as certain (value 1.0 * weight) where not explicit.
		elif object in objects2:
			# Use copy to avoid aliasing problems.
			# Use appropriate weight to update value.
			map1[ object ] = copy.deepcopy( map2[ object ] )
			for (label, value) in map1[object].items():
				map1[object][label] = weight2 * value
			map1[object]['_'] = weight1 
		else:
			# Only in current map: weight value appropriately.
			for (label, value) in map1[object].items():
				map1[object][label] = weight1 * value
			map1[object]['_'] = weight2 


def getEdgesToNeighbours(nodes,edges):
	"""return all edges which are coming from one of the nodes to out of these nodes"""
	neigb = set([])
	for (n1,n2) in edges:
		if (n1 in nodes and not n2 in nodes):
			neigb.add((n1,n2))
	return neigb

def getEdgesBetweenThem(nodes,edges):
	"""return all edges which are coming from one of the nodes to out of these nodes"""
	edg = set([])
	for (n1,n2) in edges:
		if (n1 in nodes and n2 in nodes):
			edg.add((n1,n2))
	return edg