########################################
# The contents of this file are subject to the MLX PUBLIC LICENSE version
# 1.0 (the "License"); you may not use this file except in
# compliance with the License.
# 
# Software distributed under the License is distributed on an "AS IS"
# basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
# the License for the specific language governing rights and limitations
# under the License.
# 
# The Original Source Code is "compClust", released 2003 September 03.
# 
# The Original Source Code was developed by the California Institute of
# Technology (Caltech).  Portions created by Caltech are Copyright (C)
# 2002-2003 California Institute of Technology. All Rights Reserved.
########################################
#
#       Author: Lucas J. Scharenbroich
# 
# Original Implementation:  July 10 by Lucas Scharenbroich
#
##########################################################################

"""
"""

from Graph import Graph
from Node import SimpleNode

class UGraph(Graph):
    def __init__(self, g=None):
        Graph.__init__(self)

        # Create an undirected graph from a directed one
        
        if isinstance(g, Graph):
            for key in g.edges.keys():
                self.addNode(SimpleNode(key))
                
            for key, edges in g.edges.items():
                for e in edges:
                    if not self.edgeExists(key, e):
                        self.addEdge(key, e)

    def size(self):
        return Graph.size(self) / 2
    
    def addEdge(self, key1, key2, weight = 1):
        Graph.addEdge(self, key1, key2, weight)
        Graph.addEdge(self, key2, key1, weight)

    def removeEdge(self, key1, key2):
        Graph.removeEdge(self, key1, key2)
        Graph.removeEdge(self, key2, key1)
    
    def isAcyclic(self):

        n = self.order()
        m = self.size()

        if m >= n:
            return 0

        components = 0
        marked     = {}

        for key in self.edges.keys():
            if marked.has_key(key):
                continue

            newmarks = {}
            self._doDFS(key, [], [], newmarks);        
            marked.update(newmarks)
            
            components += 1

        return n == m + components
    
        n = self.order()
        m = self.size()


    def isConnected(self):
        count, tmp = self.BFS(self._getRandKey())
        return count == self.order()