Re: how to find all completely connected sub-graphs?
Hi Hyunchul, On Tue, 03 Mar 2009 15:35:11 +0900, Hyunchul Kim wrote: >Hi, all, > >How can I find all "completely connected subgraphs" in a graph when node >and edge data are available? > >"completely connected subgraph" is a group, all members of which are >connected to each other. Since you're asking here I suspect you want (to develop) a python solution, but I have seen only solutions for a few special cases. This is the well-known graph theoretic "maximal cliques" problem (dual to the maximal independent sets problem) which is NP-complete so heuristics are in order for large examples. The most commonly used algorithm was (and perhaps still is, though I haven't kept up with this area) Bierstone's Algorithm, which I believe was unpublished so available only in discussion papers and the like. I compared it and two other common (at the time) algorithms, implemented in FORTRAN (as it was then), for a MSc project a U. Waterloo in 1970, and probably still have a copy somewhere... It may well also be in the update (ACM membership or site access trough a univeristy library or similar is required to get the full text of most of these): Corrections to Bierstone's Algorithm for Generating Cliques http://portal.acm.org/citation.cfm?id=321694.321698 and: Algorithm 457: finding all cliques of an undirected graph http://portal.acm.org/citation.cfm?doid=362342.362367 The classic reference for such clustering techniques is: An Analysis of Some Graph Theoretical Cluster Techniques http://portal.acm.org/citation.cfm?id=321608&dl=GUIDE&coll=GUIDE&CFID=25034057&CFTOKEN=54219245 If you want to find all cliques of a fixed size, then there are more efficient algorithms, and there's a very recent paper on these: Virginia Vassilevska, Efficient algorithms for clique problems, Information Processing Letters, v.109 n.4, p.254-257, January, 2009 http://portal.acm.org/citation.cfm?id=1480733&dl=GUIDE&coll=GUIDE&CFID=25034057&CFTOKEN=54219245 I hope these leads help! wwwayne >Thanks, > >Hyunchul > -- http://mail.python.org/mailman/listinfo/python-list
Re: Tutorials on Jinja
On Thu, 25 Jun 2009 07:17:42 -0700 (PDT), Saurabh wrote: >On Jun 25, 2:04 am, Wayne Brehaut wrote: >> On Wed, 24 Jun 2009 11:46:55 -0700 (PDT), Saurabh >> >> wrote: >> >Hi All, >> >> >I am trying to move my application on a MVC architecture and plan to >> >use Jinja for the same. Can anyone provide me with few quick links >> >that might help me to get started with Jinja? >> >> Perhaps the most useful link is: >> >> http://www.google.com/ >> >> from which you can easily find many more with a very basic search, >> including: >> >> http://jinja.pocoo.org/ >> >> Hope that helps? >> wwwayne >> >> >> >> >Thanks, >> >Saby >> >> > >Thanks (Sir!). I was hoping to get some good tutorial on >implementation (which I wasn't able to find with a basic search - >http://dev.pocoo.org/projects/lodgeit/ is what I was referring to >earlier) as this is my first assignment on any template engine (never >used Cheetah, MakO, Tempita). >I would appreciate people responding with something helpful. If you >find a question pretty naive, kindly ignore the question rather than >passing comments on it. Doesn't helps anyone's time. Not phrasing questions in a helpful way initially also doesn't lead to good use of anyone's time, and I suggest another link: http://catb.org/esr/faqs/smart-questions.html Your original question asked for a "few quick links that might help me to get started with Jinja", which made it appear you didn't know where to start and hadn't yet done even a basic search yourself, so I thought I *was* being helpful. Now that you provide the information that would have helped others to respond more usefully previously, perhaps they will. w >Thanks again -- http://mail.python.org/mailman/listinfo/python-list
Re: Clarity vs. code reuse/generality
On Fri, 03 Jul 2009 14:34:58 GMT, Alan G Isaac wrote: >On 7/3/2009 10:05 AM kj apparently wrote: === 8< === >2. >from scipy.optimize import bisect >def _binary_search(lo, hi, func, target, epsilon): >def f(x): return func(x) - target >return bisect(f, lo, high, xtol=epsilon) > >3. If you don't want to use SciPy (why?), have them >implement http://en.wikipedia.org/wiki/Bisection_method#Pseudo-code >to produce their own `bisect` function. Of course this isn't really pseudo-code, it's VB code with quite poor comments: 'Bisection Method 'Start loop Do While (abs(right - left) > 2*epsilon) 'Calculate midpoint of domain midpoint = (right + left) / 2 'Find f(midpoint) If ((f(left) * f(midpoint)) > 0) Then 'Throw away left half left = midpoint Else 'Throw away right half right = midpoint End If Loop Return (right + left) / 2 and even just throwing away the VB code and leaving the comments does not give a good algorithm: 'Bisection Method 'Start loop 'Calculate midpoint of domain 'Find f(midpoint) 'Throw away left half 'Throw away right half A much better approach to teaching introductory programming in any language at almost any level is to incorporate some "top down problem solving", including writing a method of solution (algorithm) in some reasonably well-defined pseudo-code that can be easily elaborated and translated into one's target language (and, peferably, some reasonable-sized subset of related languages). This pseudo-code should then become comments (or equivalent) for the students to convert to real code, as in: Algorithm bisect (f, left, right, epsilon): # Bisection Method to find a root of a real continuous function f(x): #Assume f(x) changes sign between f(left) and f(right) and # we want a value not further than epsilon from a real root. #Begin with the domain left...right. # While the absolute value of (left - right) exceeds 2*epsilon: # Calculate the midpoint, mid, of the domain. # If the product of f(left) and f(mid) is positive: # Set left to mid; # Otherwise: # Set right to mid. # Return the midpoint of left...right. === And adapting this approach to kj's case is straightforward. Of course, what consitutes a suitable vocabulary and syntax for an algorithm pseudo-code language depends upon the target language(s), the tastes of the instructor, and the point in the lesson or course. My choice is for python+COBOL (as above) initially, soon incorporating the usual arithmetic and relational operators (and how soon and how many at once depends upon the level of the students: for an introductory university/college course in Computer Science or equivalent, where everyone should have a reasonable background in mathemtics notation as a prerequisite, this should be very soon and quite fast), arrays and subscripting, etc. But if we were to write this algorithm or kj's in python-like pseudo-code it would already *be* python codeor very close to it--which is why we should teach intorductory programming in python. Very soon students would be writing algorithms that required very little elaboration to be programs. But without including suitable problem solving and psudo-code algorithm writing there will soon come a time or an example where students are trying to think in code instead of in their natural language and don't have the experience and repertoire to be able to do that well. I hope that's not too pedantic or AR? wayne >hth, >Alan Isaac -- http://mail.python.org/mailman/listinfo/python-list
Re: Natural Language Processing in Python
On Fri, 14 Aug 2009 09:31:43 -0700 (PDT), Prateek wrote: >Hi, > >Can somebody please provide me link to a good online resource or e- >book for doing natural language processing programming in Python. > >Thanks, >Prateek http://www.nltk.org/book -- http://mail.python.org/mailman/listinfo/python-list
