ufl team mailing list archive

[Johan Hake <johan.hake@xxxxxxxxx>]

On Monday 25 January 2010 07:13:14 Anders Logg wrote:
> On Mon, Jan 25, 2010 at 03:09:06PM +0000, Garth N. Wells wrote:
> > Anders Logg wrote:
> > > On Mon, Jan 25, 2010 at 03:19:36PM +0100, Marie Rognes wrote:
> > >> noreply@xxxxxxxxxxxxx wrote:
> > >>> ------------------------------------------------------------
> > >>> revno: 892
> > >>> committer: Anders Logg <logg@xxxxxxxxx>
> > >>> branch nick: ufl-main
> > >>> timestamp: Mon 2010-01-25 13:26:37 +0100
> > >>> message:
> > >>>  Add function sort_elements for sorting elements backwards with
> > >>> nested sub elements first. Using pygraph library for sorting directed
> > >>> acyclic graph. modified:
> > >>>  ufl/algorithms/__init__.py
> > >>>  ufl/algorithms/analysis.py
> > >>
> > >> Is pygraph super-standard?
> > >
> > > I don't know but it's in Ubuntu... :-)
> > >
> > > It was the simplest way I could find to store a list of elements based
> > > on their dependencies to sub elements.
> > >
> > > If it's a problem, we could implement the sorting ourselves.
> >
> > If it's simple, I would suggest implementing it ourselves to avoid a
> > dependency since UFL didn't have any dependencies beyond the standard
> > Python modules. It can wait until until the UFL/FFC change are complete
> > though.
> 
> You mean like tomorrow?
> 
> If anyone has a simple piece of code to do the following, let me know:
> 
>   # Create directed graph
>   g = digraph()
> 
>   # Add nodes (elements)
>   for element in elements:
>       g.add_node(element)
> 
>   # Add edges (dependencies)
>   for element in elements:
>       for sub_element in element.sub_elements():
>           g.add_edge(element, sub_element)
> 
>   # Sort graph
>   sorted_elements = topological_sorting(g)

Try this:

   from topologicsorting import topologic_sorting

   # Add nodes (elements)
   nodes = []
   for element in elements:
       nodes.append(element)
 
   # Add edges (dependencies)
   edges = dict((node, []) for node in nodes)
   for element in elements:
       for sub_element in element.sub_elements():
           edges[element].append(sub_element)
 
   # Sort graph
   sorted_elements = topological_sorting(nodes, edges)

Not exactly like the one you get from pygraph but close!

Johan

> --
> Anders
> 

def topological_sorting(nodes, edges):
    """ return a topological sorted list of the nodes

    Implemented algorithm from Wikipedia :P

    <http://en.wikipedia.org/wiki/Topological_sorting>

    No error for cyclic edges...
    """
    # Build initial structure:
    # S should only contain nodes with no edge pointing to it

    L = []
    S = nodes[:]
    for node in nodes:
        for es in edges.itervalues():
            if node in es and node in S:
                S.remove(node)
                continue
    
    while S:
        node = S.pop(0)
        L.append(node)
        node_edges = edges[node]
        while node_edges:
            m = node_edges.pop(0)
            found = False
            for es in edges.itervalues():
                found = m in es
                if found:
                    break
            if not found:
                S.insert(0,m)
    return L

if __name__ == "__main__":
    import pygraph 

    g = pygraph.digraph()

    nodes = [7, 5, 3, 11, 8, 2, 9, 10]
    edges = {7:[8,11], 5:[11], 3:[8,10], 11:[2,9,10], 8:[9], 2:[], 9:[], 10:[]}

    for node in nodes:
        g.add_node(node)

    for node in nodes:
        for edge in edges[node]:
            g.add_edge(node, edge)

    print "Pygraph object:", g
    print "Pygraph sorted list:", pygraph.algorithms.sorting.topological_sorting(g)
    print "Some sorted list:", topological_sorting(nodes, edges)