#! /usr/bin/env python
#                             -*- Mode: Python -*-
#
# Figure out strongly connected components from a graph.
#
# See http://en.wikipedia.org/wiki/Strongly_connected_component
#
# That has a sample graph which I will use as a test case.
#
import os


class GraphNode(object):

    def __init__(self, **kwargs):
        # expect "name" and "child_list"
        # will set transpose_finish if found
        super(GraphNode, self).__init__(kwargs)
        self.name = kwargs["name"]
        # child_list is a list of GraphNode names.
        self.child_list = kwargs["child_list"]
        self.transpose_finish = kwargs.get("transpose_finish", -1)
        self.discover = -1
        self.finish = -1

    def __str__(self):
        return ("GraphNode s. child_list %s. discover %d. finish %d. finishT: %d."  %
                (self.name, repr(self.child_list), self.discover, self.finish, self.transpose_finish ))

    def isWhite(self):
        return self.discover == -1 and self.finish == -1

    def isBlack(self):
        return self.finish != -1

    def isGrey(self):
        return self.discover != -1 and self.finish == -1
    

class Graph(object):

    def __init__(self, **kwargs):
        """nodes is a list of GraphNode objects.
        This constructor will create a dictionary (hashmap) of those
        nodes with the node name as a key."""
        super(Graph, self).__init__(kwargs)
        if kwargs.has_key("nodes"):
            self.nodes = dict([ (x.name, x) for x in kwargs["nodes"] ])
        else:
            self.nodes = {}
        self.time = 0

    def addNode(self, node):
        self.nodes[node.name] = node

    def transpose(self):
        """Return a Graph object which describes the transpose of this one."""
        retval = Graph(nodes=[GraphNode(name=x.name,
                                        child_list=[],
                                        transpose_finish=x.finish)
                              for x in self.nodes.itervalues()])

        for x in self.nodes:
            for y in self.nodes[x].child_list:
                retval.nodes[y].child_list.append(x)
            
        return retval

    def dfs(self):
        """Perform a DFS on the graph, setting the discover and finish values."""
        # Normally, white, grey, and black are used to mark the nodes.
        # discover == finish == -1 means the node is white.
        # discover != -1 and finish == -1 means the node is grey
        # discover != -1 and finish != -1 means the node is black.
        # (Actually, finish != -1 is sufficient to declare a node to be black.)
        #
        # More wierdness.  If none of the transposeFinish values are
        # different from the default, you essentially get all the nodes in
        # no particular order.
        #
        for aval in self.nodes.values():
            aval.discover = aval.finish = -1
        theList = [ x for x in self.nodes.values() ]
        theList.sort(None, lambda x: x.transpose_finish, True)
        self.time = 0
        return [ self.__visit(x, []) for x in theList if x.isWhite() ]

    def __visit(self, node, retlist):
        self.time += 1
        node.discover = self.time
        for x in node.child_list:
            if self.nodes[x].isWhite():
                self.__visit(self.nodes[x], retlist)
        self.time += 1
        node.finish = self.time
        retlist.append(node)
        return retlist

            
class SCC(object):
    """This is a Strongly Connected Component object."""
    
    IDENT = 1
    
    def __init__(self, nodeList, verbose):
        self.import_list = set() # this is a set of GraphNode ids
        self.nodes = set()        # this is a set of GraphNode objects
        self.ident = SCC.IDENT
        SCC.IDENT += 1

        for aNode in nodeList:
            self.addNode(aNode, verbose)

    def addNode(self, theNode, verbose):
        if verbose:
            print "Adding %s to SCC %d" % (theNode, self.ident)
        self.nodes.add(theNode)
        self.import_list.update(theNode.child_list)

    def __str__(self):
        temp = "SCC ident: %d" % self.ident
        for aNode in self.nodes:
            temp += (os.linesep + str(aNode))
        return temp + os.linesep

class StronglyConnectedComponentFinder(object):

    def __init__(self, theGraph, verbose=False):
        # verbose here is for debugging
        self.graph = theGraph
        self.graphT = None
        self.verbose = verbose
        self.SCCList = []
        self.SCCMap = {}

    def findSCC(self):
        if self.graphT:
            return
        self.graph.dfs()
        self.graphT = self.graph.transpose()
        theList = self.graphT.dfs()
        # theList is a list of lists of GraphNodes.  Python can be rather Lispy at times.
        for x in theList:
            newSCC = SCC(x, self.verbose)
            self.SCCList.append(newSCC)
            self.SCCMap[newSCC.ident] = newSCC
        

if __name__ == '__main__':
    print "Creating the Graph instance."
    aGraph = Graph(nodes=[ GraphNode(name="a", child_list=["b"]),
                           GraphNode(name="b", child_list=["e", "f", "c"]),
                           GraphNode(name="c", child_list=["d", "g"]),
                           GraphNode(name="d", child_list=["c", "h"]),
                           GraphNode(name="e", child_list=["a", "f"]),
                           GraphNode(name="f", child_list=["g"]),
                           GraphNode(name="g", child_list=["f"]),
                           GraphNode(name="h", child_list=["g", "d"]) ])
    
    print "Create StronglyConnectedComponentFinder object."
    finder = StronglyConnectedComponentFinder(aGraph, True)
    print "Calculate dfs of original graph, the transpose, and the DFS of the transpose."
    finder.findSCC()
    print "the list of SCCs is: "
    for scc in finder.SCCList:
        print scc
    print "Note that the nodes in this SCC list are from the *transposed* graph!"

[kikinovak@raymonde:~] $ hoorex lame
lame plex-home-theater avidemux ffmpeg kdenlive ebook2cw soundconverter Pd-extended mythtv

[root@raymonde:~] # hoorex lame
Traceback (most recent call last):
  File "/usr/bin/hoorex", line 427, in <module>
    main()
  File "/usr/bin/hoorex", line 32, in main
    default_config = load_user_config()
  File "/usr/bin/hoorex", line 372, in load_user_config
    with open(config_file, 'wb') as configfile:
IOError: [Errno 2] No such file or directory: '/root/.config/hoorex/defaults.cfg'

# hoorex -f -s SBO_PATH