Subject: Re: [Ufl] [Branch ~ufl-core/ufl/main] Rev 892: Add function sort_elements for sorting elements backwards with nested sub

From: Marie Rognes <[email-masked]>
Date: Mon, 25 Jan 2010 15:19:36 +0100

[email-masked] wrote:
> ------------------------------------------------------------
> revno: 892
> committer: Anders Logg <[email-masked]>
> 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?

--
Marie

> --
> lp:ufl
> https://code.launchpad.net/~ufl-core/ufl/main
>
> You are subscribed to branch lp:ufl.
> To unsubscribe from this branch go to https://code.launchpad.net/~ufl-core/ufl/main/+edit-subscription.
>

---

From: Anders Logg <[email-masked]>
Date: Mon, 25 Jan 2010 15:48:42 +0100

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

--
Anders

---

From: "Garth N. Wells" <[email-masked]>
Date: Mon, 25 Jan 2010 15:09:06 +0000

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

Garth

> --
> Anders
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Mailing list: https://launchpad.net/~ufl
> Post to     : [email-masked]
> Unsubscribe : https://launchpad.net/~ufl
> More help   : https://help.launchpad.net/ListHelp

---

From: Anders Logg <[email-masked]>
Date: Mon, 25 Jan 2010 16:13:14 +0100

> Python modules. It can wait until until the UFL/FFC change are complete

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)

--
Anders

---

From: "Garth N. Wells" <[email-masked]>
Date: Mon, 25 Jan 2010 15:15:07 +0000

>> Python modules. It can wait until until the UFL/FFC change are complete

If you are quick enough to have UFL and FFC ready tomorrow, then writing
a graph library should only take a few minutes ;).

Garth

---

From: Anders Logg <[email-masked]>
Date: Mon, 25 Jan 2010 16:22:24 +0100

> a graph library should only take a few minutes ;).

I was rather hoping to get some assistance with writing the graph
library so we can finish up tomorrow. You seem to have a lot of free
time these days. ;-)

--
Anders

---

From: Harish Narayanan <[email-masked]>
Date: Mon, 25 Jan 2010 16:21:27 +0000

> I don't know but it's in Ubuntu... :-)

_Everything_ is super-standard on my dirty old BSD.

Harish

---

From: Johan Hake <[email-masked]>
Date: Mon, 25 Jan 2010 08:33:31 -0800

On Monday 25 January 2010 07:13:14 Anders Logg wrote:
> > >>>  Add function sort_elements for sorting elements backwards with
> > >>> nested sub elements first. Using pygraph library for sorting directed
> > >>> acyclic graph. modified:

I am not sure what you want to accomplish but I suppose:

   collection = []

   for element in elements:
       for sub_element in element.sub_elements():
           collection.append((element, sub_element))

   collection.sort()

would not do it? Then you would get a list with the "lowest" elements first 
followed with the lowest sub_elements.

Johan

---

From: Johan Hake <[email-masked]>
Date: Mon, 25 Jan 2010 15:59:40 -0800

>   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

---

From: Anders Logg <[email-masked]>
Date: Tue, 26 Jan 2010 09:36:30 +0100

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

---

From: Johan Hake <[email-masked]>
Date: Tue, 26 Jan 2010 08:00:35 -0800

On Tuesday 26 January 2010 00:36:30 Anders Logg wrote:
> > > > >>> nested sub elements first. Using pygraph library for sorting
> > > > >>> directed acyclic graph. modified:
> > > > > It was the simplest way I could find to store a list of elements
> > > > > based on their dependencies to sub elements.
> > > > >
> > > > Python modules. It can wait until until the UFL/FFC change are
> > > > complete though.
> > >
> > > You mean like tomorrow?
> > >
> >     print "Pygraph sorted list:",
> > pygraph.algorithms.sorting.topological_sorting(g) print "Some sorted
> > list:", topological_sorting(nodes, edges)
> 

Cool!

Johan