lg.py

			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 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
		# '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.
	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 self.nlabels.keys():
			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 self.elabels.keys():
			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 self.nlabels.keys():
			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 self.elabels.keys():
			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 self.nlabels.keys():
			subStruct.append(set([n]))
			if 1 in nodeNumbers:
				yield smallGraph.SmallGraph([(n, "".join(self.nlabels[n].keys()))], [])
		
		for d in range(2,max(nodeNumbers)+1):
			#add one node to each substructure
			newSubsS = set([])
			newSubsL = []
			for sub in subStruct:
				le = getEdgesToNeighbours(sub,self.elabels.keys())
				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] = self.nlabels[n].keys()
		for e in getEdgesBetweenThem(nodelist,self.elabels.keys()):
			sg.edges[e] = self.elabels[e].keys()
		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(struc.nodes.keys())
				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()

		allNodes = set(psGT.keys())
		#FIX : check that primitives identical. This this not the case in spare representation 
		assert allNodes == set(psGT.keys())
	
		segDiffs = set()
		correctSegments = set()
		for primitive in psGT.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.

			# RZ: Assuming one level of structure here; modifying for
			#     new data structures accomodating multiple structural levels.
			obj1Id = ps1[primitive][ ps1[primitive].keys()[0] ]
			obj2Id = psGT[primitive][ psGT[primitive].keys()[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(self.nlabels.keys()) > 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(self.nlabels[ firstPrim ].keys(),lgGT.nlabels[ firstPrim ].keys())

			segId1 = ps1[firstPrim][ ps1[ firstPrim ].keys()[0] ]
			segId2 = psGT[firstPrim][ psGT[ firstPrim ].keys()[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.iteritems():
			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 sreGT.keys():
			# 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 self.elabels.keys() or \
					   (0,[]) != self.cmpEdges(self.elabels[ (parentId, childId) ].keys(), lgGT.elabels[ (parentId, childId) ].keys()):
						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(smg.nodes.keys()).intersection(allSegWithErr)) > 0:
				showIt = True
			for pair in smg.edges.keys():
				if pair in segEdgeErr:
					showIt = True
					continue
			if showIt:
				#build the smg for the prim from lgGT
				allPrim = []
				for s in smg.nodes.keys():
					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 llist1.keys() and \
				label in llist2.keys():
			llist1[ label ] = \
				combfn( llist1[label], weight1,\
						llist2[label], weight2 )
		elif label in llist2.keys():
			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 = map1.keys()
	objects2 = map2.keys()
	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