ufl team mailing list archive

[Anders Logg <logg@xxxxxxxxx>]

On Mon, Jan 25, 2010 at 03:59:40PM -0800, Johan Hake wrote:
> 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
>

>
> 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)

Thanks! Seems to work fine. I've replaced pygraph with your
implementation now.

--
Anders

Attachment: signature.asc
Description: Digital signature