ufl team mailing list archive

[Johan Hake <johan.hake@xxxxxxxxx>]

On Tuesday 26 January 2010 00:36:30 Anders Logg wrote:
> 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.

Cool!

Johan