lg.py

                    errorVal +=  math.sqrt(float(segEdgeMismatch) / numEdges) + \
                                     math.sqrt(float(elabelMismatch) / numEdges)
            if numNodes > 0:
                    errorVal += float(nlabelMismatch) / numNodes
            errorVal = errorVal / 3.0
            eerror  = ("D_E(%)", errorVal)

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

            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([(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()
            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