lg.py

					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()))], [])
		#print(subStruct)
		for d in range(2,max(nodeNumbers)+1):
					#add one node to each substructure
			newSubsS = set([])
			newSubsL = []
			for sub in subStruct:
				#print ("  with " + str(sub))
				le = getEdgesToNeighbours(sub,self.elabels.keys())
				for (f,to) in le:
					#print ("    Add? " + str(to))
					new = sub.union([to])
					lnew = list(new)
					lnew.sort()
					snew = ",".join(lnew)
					#print ("    Test:" + snew + " in " + str(newSubsS))
					if(not snew in newSubsS):
						newSubsS.add(snew)
						newSubsL.append(new)
						if d in nodeNumbers:
#							struc = getEdgesBetweenThem(new, self.elabels.keys())
#							sg1 = smallGraph.SmallGraph()
#							for n in new:
#								sg1.nodes[n] = "".join(self.nlabels[n].keys())
#							for (a,b) in struc:
#								sg1.edges[(a,b)] = "".join(self.elabels[(a,b)].keys())
							yield self.getSubSmallGraph(new)
						#print ("   Added: " + str(new))
			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] = "".join(self.nlabels[n].keys())
		for e in getEdgesBetweenThem(nodelist,self.elabels.keys()):
			sg.edges[e] = "".join(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, lg2,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 lg2.
		The first key value of the matrix is the lg2 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()
		(sp2, ps2, _, sre2) = lg2.segmentGraph()
		#byValue = lambda pair: pair[1]  # define key for sort comparisons.

		allNodes = set(ps2.keys())
		#FIX : this this not the case in spare representation 
		assert allNodes == set(ps2.keys())
	
		segDiffs = set()
		correctSegments = set()
		for primitive in ps2.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]:
				# Obtain sets of primitives sharing a segment for the current
				# primitive for both graphs.
				# Each of sp1/sp2 are a map of ( {prim_set}, label ) pairs.
				segPrimSet1 = sp1[ ps1[primitive] ][0]
				segPrimSet2 = sp2[ ps2[primitive] ][0]
				
				# Only create an entry where there are disagreements.
				if segPrimSet1 != segPrimSet2:
					segDiffs.add( ( ps2[primitive], ps1[primitive]) )
				else:
					correctSegments.add(ps2[primitive])
			# 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 miss segment
				# do not count the segment in graph with 1 primitive
				segDiffs.add(( ps2[primitive], ps1[primitive]) )

		# 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(sp2[seg][0])[0]
			if set(self.nlabels[ firstPrim ].keys()) != set(lg2.nlabels[ firstPrim ].keys()):
				segDiffs.add(( ps2[primitive], ps1[primitive]) )
		allSegWithErr = set([p for (p,_) in segDiffs])
		# start to build the LG at the object level
		# add nodes for objet with the labels from the first prim
		lgObj = Lg()
		for (sid,lprim) in sp2.iteritems():
			lgObj.nlabels[sid] = self.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 sre2.keys():
			# TODO : check if it sp1[thisPair[0]] instead sp1[thisPair[0]][0]
			thisParentIds = set(sp2[ thisPair[0] ][0])
			thisChildIds = set(sp2[thisPair[1] ][0])
			lgObj.elabels[thisPair] = lg2.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 \
					   not set(self.elabels[ (parentId, childId) ].keys())  == \
							set(lg2.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 lg2
				allPrim = []
				for s in smg.nodes.keys():
					allPrim.extend(sp2[s][0])
				#print allPrim
				smgPrim1 = self.getSubSmallGraph(allPrim)
				#build the smg for the prim from lg2 
				smgPrim2 = lg2.getSubSmallGraph(allPrim)
				listOfAllError.append((smg,smgPrim2,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