graphutil.py

一个通用的隐性马尔可夫C代码库 开发环境:C语言 简要说明:这是一个通用的隐性马尔可夫C代码库

################################################################################
#
#       This file is part of Gato (Graph Animation Toolbox) 
#       version _VERSION_ from _BUILDDATE_. You can find more information at 
#       http://www.zpr.uni-koeln.de/~gato
#
#	file:   Graph.py
#	author: Alexander Schliep ([e-mail])
#
#       Copyright (C) 1998-2002, Alexander Schliep, Winfried Hochstaettler and 
#       ZAIK/ZPR, Universitaet zu Koeln
#                                   
#       Contact: [e-mail], [e-mail]             
#
#       Information: http://gato.sf.net
#
#       This library is free software; you can redistribute it and/or
#       modify it under the terms of the GNU Library General Public
#       License as published by the Free Software Foundation; either
#       version 2 of the License, or (at your option) any later version.
#
#       This library is distributed in the hope that it will be useful,
#       but WITHOUT ANY WARRANTY; without even the implied warranty of
#       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#       Library General Public License for more details.
#
#       You should have received a copy of the GNU Library General Public
#       License along with this library; if not, write to the Free
#       Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#
#
#
#       This file is version $Revision: 1.1 $ 
#                       from $Date: 2003/09/24 12:06:37 $
#             last change by $Author: cic99 $.
#
################################################################################

import types
import StringIO
from string import split
from GatoGlobals import *
from Graph import Graph
from DataStructures import Point2D, VertexLabeling, EdgeLabeling, EdgeWeight, VertexWeight, Queue
import logging
log = logging.getLogger("GraphUtil.py")

################################################################################
#
# Syntactic Sugar
#
################################################################################
def Vertices(G):
    """ Returns the vertices of G. Hide method call """
    return G.vertices

def Edges(G):
    """ Returns the edges of G. Hide method call """
    return G.Edges()


################################################################################
#
# Basic algorithms
#
################################################################################

def BFS(G,root,direction='forward'):
    """ Calculate BFS distances and predecessor without showing animations. 
        If G is directed, direction does matter:

        - 'forward'  BFS will use outgoing edges
        - 'backward' BFS will use incoming edges

	It uses gInfinity (from GatoGlobals.py) as infinite distance.
        returns (dist,pred) """

    Q = Queue()
    d = {}
    pred = {}

    for v in G.vertices:
	d[v] = gInfinity
    d[root] = 0
    pred[root] = None

    Q.Append(root)

    while Q.IsNotEmpty():
        v = Q.Top()
	if G.QDirected() == 1 and direction == 'backward':
	    nbh = G.InNeighbors(v)
	else:
	    nbh = G.Neighborhood(v)
	for w in nbh:
	    if d[w] == gInfinity:
		d[w] = d[v] + 1
		Q.Append(w)

    return (d,pred)


def ConnectedComponents(G):
    """ Compute the connected components of the undirected graph G.
        Returns a list of lists of vertices. """


    result = []
    visited = {}
    for v in G.vertices:
	visited[v] = None

    for root in G.vertices:
        if visited[root] is not None:
            continue
        else: # Found a new component
            component = [root]
            visited[root] = 1
            
            Q = Queue()
            Q.Append(root)

            while Q.IsNotEmpty():
                v = Q.Top()
                nbh = G.Neighborhood(v)
                for w in nbh:
                    if visited[w] == None:
                        visited[w] = 1
                        Q.Append(w)
                        component.append(w)

            result.append(component)
            
    return result



################################################################################
#
# GraphInformer
#
################################################################################


class GraphInformer:
    """ Provides information about edges and vertices of a graph.
        Used as argument for GraphDisplay.RegisterGraphInformer() """

    def __init__(self,G):
	self.G = G
        self.info = ""

    def DefaultInfo(self):
        """ Provide an default text which is shown when no edge/vertex
	    info is displayed """  
        return self.info
	
    def VertexInfo(self,v):
        """ Provide an info text for vertex v """  
        return "Vertex %d at position (%d,%d)" % (v, 
                                                  self.G.embedding[v].x, 
                                                  self.G.embedding[v].y)
	
    def EdgeInfo(self,tail,head):
        """ Provide an info text for edge (tail,head)  """        
        return "Edge (%d,%d)" % (tail, head) 

    def SetDefaultInfo(self, info=""):
        self.info = info


class WeightedGraphInformer(GraphInformer):
    """ Provides information about weighted edges and vertices of a graph.
        Used as argument for GraphDisplay.RegisterGraphInformer() """

    def __init__(self,G,weightDesc="weight"):
	""" G is the graph we want to supply information about and weightDesc
	    a textual interpretation of the weight """
	GraphInformer.__init__(self,G)
	self.weightDesc = weightDesc
    
    def EdgeInfo(self,tail,head):
        """ Provide an info text for weighted edge (tail,head)  """  
        # How to handle undirected graph
        if self.G.QDirected() == 0:
            try:
                w = self.G.edgeWeights[0][(tail, head)]
            except KeyError:
                w = self.G.edgeWeights[0][(head, tail)]
        else:
            w = self.G.edgeWeights[0][(tail, head)]
	if self.G.edgeWeights[0].QInteger():
	    return "Edge (%d,%d) %s: %d" % (tail, head, self.weightDesc, w) 
	else:
	    return "Edge (%d,%d) %s: %f" % (tail, head, self.weightDesc, w) 


class MSTGraphInformer(WeightedGraphInformer):
    def __init__(self,G,T):
	WeightedGraphInformer.__init__(self,G)
	self.T = T

    def DefaultInfo(self):
        """ Provide an default text which is shown when no edge/vertex
	    info is displayed """  
	return "Tree has %d vertices and weight %5.2f" % (self.T.Order(),self.T.Weight())

		
class FlowGraphInformer(GraphInformer):
    def __init__(self,G,flow):
	GraphInformer.__init__(self,G)
	self.flow   = flow
        self.cap    = flow.cap
        self.res    = flow.res
        self.excess = flow.excess

    def EdgeInfo(self,v,w):
        return "Edge (%d,%d) - flow: %d of %d" % (v,w, self.flow[(v,w)], self.cap[(v,w)])

    def VertexInfo(self,v):
        tmp = self.excess[v]
        if tmp == gInfinity:
            str1 = "Infinity"
        elif tmp == -gInfinity:
            str1 = "-Infinity"
        else:
            str1 = "%d"%tmp

        return "Vertex %d - excess: %s" % (v, str1)

class ResidualGraphInformer(FlowGraphInformer):

    def EdgeInfo(self,v,w):
        return "Edge (%d,%d) - residual capacity: %d" % (v, w, self.res[(v,w)])

################################################################################
#
# FILE I/O
#
################################################################################

def OpenCATBoxGraph(_file):
    """ Reads in a graph from file fileName. File-format is supposed
        to be from old CATBOX++ (*.cat) """
    G = Graph()
    E = VertexLabeling()
    W = EdgeWeight(G)
    L = VertexLabeling()

    # get file from name or file object
    graphFile=None
    if type(_file) in types.StringTypes:
        graphFile = open(_file, 'r')
    elif type(_file)==types.FileType or issubclass(_file.__class__,StringIO.StringIO):
        graphFile=_file
    else:
        raise Exception("got wrong argument")

    lineNr = 1

    firstVertexLineNr = -1    
    lastVertexLineNr  = -1
    firstEdgeLineNr   = -1
    lastEdgeLineNr    = -1
    intWeights        = 0

    while 1:
	
	line = graphFile.readline()
	
	if not line:
	    break

	if lineNr == 2: # Read directed and euclidian
	    splitLine = split(line[:-1],';')	    
	    G.directed = eval(split(splitLine[0],':')[1])
	    G.simple = eval(split(splitLine[1],':')[1])
	    G.euclidian = eval(split(splitLine[2],':')[1])
	    intWeights = eval(split(splitLine[3],':')[1])
	    nrOfEdgeWeights = eval(split(splitLine[4],':')[1])
	    nrOfVertexWeights = eval(split(splitLine[5],':')[1])
	    for i in xrange(nrOfEdgeWeights):
		G.edgeWeights[i] = EdgeWeight(G)
	    for i in xrange(nrOfVertexWeights):
		G.vertexWeights[i] = VertexWeight(G)


	if lineNr == 5: # Read nr of vertices
	    nrOfVertices = eval(split(line[:-2],':')[1]) # Strip of "\n" and ; 
	    firstVertexLineNr = lineNr + 1
	    lastVertexLineNr  = lineNr + nrOfVertices
	
	if  firstVertexLineNr <= lineNr and lineNr <= lastVertexLineNr: 
	    splitLine = split(line[:-1],';')
	    v = G.AddVertex()

	    label =split(splitLine[1],':')[1]
	    G.labeling[v] = split(splitLine[1],':')[1]
	    #y = eval(split(splitLine[2],':')[1])

	    for i in xrange(nrOfVertexWeights):
			w = eval(split(splitLine[2+i],':')[1])
	   		G.vertexWeights[i][v] = w

	    #E[v] = Point2D(x,y)
	    
	if lineNr == lastVertexLineNr + 1: # Read Nr of edges
	    nrOfEdges = eval(split(line[:-2],':')[1]) # Strip of "\n" and ; 
	    firstEdgeLineNr = lineNr + 1
       	    lastEdgeLineNr  = lineNr + nrOfEdges

	if firstEdgeLineNr <= lineNr and lineNr <= lastEdgeLineNr: 
	    splitLine = split(line[:-1],';')
	    h = eval(split(splitLine[0],':')[1])
	    t = eval(split(splitLine[1],':')[1])
	    G.AddEdge(t,h)
	    for i in xrange(nrOfEdgeWeights):
		G.edgeWeights[i][(t,h)] = eval(split(splitLine[3+i],':')[1])
 
	lineNr = lineNr + 1

    graphFile.close()

    if intWeights:
	G.Integerize('all')
	for i in xrange(nrOfVertexWeights):
	    G.vertexWeights[i].Integerize()

    return G

def SaveCATBoxGraph(G, _file):
    """ Save graph to file fileName in file-format from old CATBOX++ (*.cat) """

    # get file from name or file object
    file=None
    if type(_file) in types.StringTypes:
        file = open(_file, 'w')
    elif type(_file)==types.FileType or issubclass(_file.__class__,StringIO.StringIO):
        file=_file
    else:
        raise Exception("got wrong argument")
  
    nrOfVertexWeights = len(G.vertexWeights.keys())
    nrOfEdgeWeights = len(G.edgeWeights.keys())
    integerEdgeWeights = G.edgeWeights[0].QInteger()

    file.write("graph:\n")
    file.write("dir:%d; simp:%d; eucl:%d; int:%d; ew:%d; vw:%d;\n" %
	       (G.QDirected(), G.simple, G.QEuclidian(), integerEdgeWeights,
	       nrOfEdgeWeights, nrOfVertexWeights))
    file.write("scroller:\n")
    file.write("vdim:1000; hdim:1000; vlinc:10; hlinc:10; vpinc:50; hpinc:50;\n")
    file.write("vertices:" + `G.Order()` + ";\n")
    
    # Force continous numbering of vertices
    count = 1
    save = {}
    for v in G.vertices:
	save[v] = count
	count = count + 1
	file.write("n:%d; l:%s; " % (save[v], G.labeling[v]))
	for i in xrange(nrOfVertexWeights):
	    if integerEdgeWeights: # XXX
		file.write(" w:%d;" % int(round(G.vertexWeights[i][v])))
	    else:
		file.write(" w:%d;" % G.vertexWeights[i][v])	    
	file.write("\n")

    file.write("edges:" + `G.Size()` + ";\n")
    for tail in G.vertices:
	for head in G.OutNeighbors(tail):
	    file.write("h:%d; t:%d; e:2;" % (save[head], save[tail]))

	    for i in xrange(nrOfEdgeWeights):
		if integerEdgeWeights:
		    file.write(" w:%d;" % int(round(G.edgeWeights[i][(tail,head)])))
		else:
		    file.write(" w:%f;" % G.edgeWeights[i][(tail,head)])
		    
	    file.write("\n")

#### GML

def ParseGML(file):
    
    retval = []

    while 1:
	
	line = file.readline() 
    
	if not line:
	    return retval

	token = filter(lambda x: x != '', split(line[:-1],"[\t ]*"))

	if len(token) == 1 and token[0] == ']':
	    return retval

	elif len(token) == 2:
	    
	    if token[1] == '[':
		retval.append((token[0], ParseGML(file)))
	    else:
		retval.append((token[0], token[1]))

	else:
            log.error("Serious format error line %s:" % line)


def PairListToDictionary(l):
    d = {}
    for i in xrange(len(l)):
	d[l[i][0]] = l[i][1]
    return d
	    


def OpenGMLGraph(fileName):
    """ Reads in a graph from file fileName. File-format is supposed
        to be GML (*.gml) """
    G = Graph()
    G.directed = 0
    E = VertexLabeling()
    W = EdgeWeight(G)
    L = VertexLabeling()
    VLabel = VertexLabeling()
    ELabel = EdgeLabeling()

    file = open(fileName, 'r')
    g = ParseGML(file)
    file.close()

    if g[0][0] != 'graph':
        log.error("Serious format error in %s. first key is not graph" % fileName)
	return
    else:
	l = g[0][1]
	for i in xrange(len(l)):
	    
	    key   = l[i][0]
	    value = l[i][1]
    
	    if key == 'node':
		
		d = PairListToDictionary(value)
		v = G.AddVertex()
		
		try:
		    VLabel[v] = eval(d['label'])
		    P = PairListToDictionary(d['graphics'])
		    E[v] = Point2D(eval(P['x']), eval(P['y']))
		    
		except:
		    d = None 
		    P = None

	    elif key == 'edge':

		d = PairListToDictionary(value)

		try:
		    s = eval(d['source'])
		    t = eval(d['target'])
		    G.AddEdge(s,t)
		    ELabel[(s,t)] = eval(d['label'])
		    W[(s,t)] = 0
		except:
		    d = None 
		  
	    elif key == 'directed':
		G.directed = 1 
 
    for v in G.vertices:
	L[v] = v
	
    G.embedding = E
    G.labeling  = L
    G.nrEdgeWeights = 1
    G.edgeWeights[0] = W
    G.vertexAnnotation = VLabel
    G.edgeAnnotation = ELabel

    return G