################################################################################
#
#       This file is part of Gato (Graph Animation Toolbox) 
#
#	file:   Graph.py
#	author: Alexander Schliep (alexander@schliep.org)
#
#       Copyright (C) 1998-2011, Alexander Schliep, Winfried Hochstaettler and
#       Copyright 1998-2001 ZAIK/ZPR, Universitaet zu Koeln
#
#       Contact: alexander@schliep.org, winfried.hochstaettler@fernuni-hagen.de
#
#       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: 434 $
#                       from $Date: 2011-05-05 12:35:25 -0400 (Thu, 05 May 2011) $
#             last change by $Author: schliep $
#
################################################################################
 
import types
import StringIO
from string import split
import string
from GatoGlobals import *
import Graph
from DataStructures import Point2D, VertexLabeling, EdgeLabeling, EdgeWeight, VertexWeight, Queue
import logging
log = logging.getLogger("Gato")
 
 
################################################################################
#
# 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] = root
 
    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
                pred[w] = v
                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
 
 
def FindBipartitePartitions(G):
    """ Finds the two partitions of a bipartite graph G and returns
        two vertex sets. If G is not bipartite, it returns two empty
        sets.
    """
    Q = Queue()
    V = set()
    W = set()
    dist = {}
 
    for v in G.vertices:
        if v not in dist:
            dist[v] = 0
            Q.Append(v)
            V.add(v)
 
            while Q.IsNotEmpty():
                v = Q.Top()
 
                for w in G.Neighborhood(v):
                    if w not in dist:
                        dist[w] = dist[v] + 1
                        Q.Append(w)
 
                        if dist[w] % 2 == 1:
                            W.add(w)
                        else:
                            V.add(w)
                    else:
                        if (dist[w] + dist[v]) % 2 == 0:
                            # Found an incompatible edge
                            return (set(), set())                            
    return (V, W)
 
 
 
    ################################################################################
    #
    # 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 """
        t = self.G.GetEmbedding(v)
        return "Vertex %d at position (%d,%d)" % (v, int(t.x), int(t.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.GetEdgeWeight(0,tail, head)
            except KeyError:
                w = self.G.GetEdgeWeight(0, head, tail)
        else:
            w = self.G.GetEdgeWeight(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.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()
            x = eval(split(splitLine[1],':')[1])
            y = eval(split(splitLine[2],':')[1])
            for i in xrange(nrOfVertexWeights):
                w = eval(split(splitLine[3+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,False)
            for i in xrange(nrOfEdgeWeights):
                G.edgeWeights[i][(t,h)] = eval(split(splitLine[3+i],':')[1])
 
        lineNr = lineNr + 1
 
    graphFile.close()
 
    for v in G.vertices:
        L[v] = v
 
    G.embedding = E
    G.labeling  = L
    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")
 
    # Being paranoid here: We force edge weights to be euclidean 
    if G.QEuclidian():
        G.Euclidify()
 
    # Force continous numbering of vertices
    count = 1
    save = {}
    for v in G.vertices:
        save[v] = count
        count = count + 1
        file.write("n:%d; x:%d; y:%d;" % (save[v], G.embedding[v].x, G.embedding[v].y))
        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.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
 
 
 
def OpenDotGraph(fileName):
    """ Reads in a graph from file fileName. File-format is supposed
        to be dot (*.dot) used in """
    G = Graph.Graph()
    G.directed = 1
    E = VertexLabeling()
    W = EdgeWeight(G)
    L = VertexLabeling()
    VLabel = VertexLabeling()
    ELabel = EdgeLabeling()
 
    import re
    file = open(fileName, 'r')
    lines = file.readlines()
    file.close()
 
    dot2graph = {}
 
    for l in lines[3:]:
        items = string.split(l)
        if len(items) < 2:
            break
        if items[1] != '->':
            v = G.AddVertex()
            dot_v = int(items[0])
            L[v] = "%d" % dot_v
            dot2graph[dot_v] = v
            m = re.search('label=("[^"]+")', l)
            VLabel[v] = m.group(1)[1:-1]
            m = re.search('pos="(\d+),(\d+)"', l)
            x = int(m.group(1))
            y = int(m.group(2))
            E[v] = Point2D(x,y)
        else:
            m = re.search('(\d+) -> (\d+)', l)
            v = dot2graph[int(m.group(1))]
            w = dot2graph[int(m.group(2))]
            m = re.search('label=("[^"]+")', l)
            #print l
            #print v,w,m.group(1)
            G.AddEdge(v,w)
            weight = float(m.group(1)[1:-1])
            W[(v,w)] = weight
            ELabel[(v,w)] = "%0.2f" % weight
 
    G.embedding = E
    G.labeling  = L
    G.nrEdgeWeights = 1
    G.edgeWeights[0] = W
    G.vertexAnnotation = VLabel
    G.edgeAnnotation = ELabel
    return G
 
 
def WeightMatrix(G=None, fromFileName=None, noEdgeWeight=999999.9):
    import numpy
    if fromFileName:
        G = OpenCATBoxGraph(fromFileName)
    directed = G.QDirected()
    A = numpy.ones((G.Order(),G.Order())) * noEdgeWeight
    for i in range(G.Order()):
        A[i,i] = 0
    for i,j in G.Edges():
        A[i-1,j-1] = G.GetEdgeWeight(0,i,j)
        if not directed:
            A[i-1,j-1] = G.GetEdgeWeight(0,i,j)
    return A