summaryrefslogtreecommitdiff
path: root/graph.py
Commit message (Collapse)AuthorAgeFilesLines
* added pruning of the recursive search tree for detecting cycles in graphs. ↵Dirk Baechle2013-04-111-3/+6
| | | | | | | | | | | | | | | | | | | | | Closes #2469 provides a significant speedup for get_cycles() Rationale for the whole patch: While trying to analyze the source tree of SCons (www.scons.org), I noticed that pylint took forever to finish a single run. I tracked the problem down a little and finally ended my search at the _get_cycles() function that gets called recursively. They way it is implemented at the moment, you will get a very high number of calls for medium to large graphs that are also very dense in nature (have a high vertex degree). In the case of SCons there are about 176 packages involved, which import each other a lot. This results in 130869104 calls of _get_cycles() and a runtime of 27minutes and 6.835seconds fo the whole pylint run. With this patch you get 10156 calls, taking 30.893s for the complete pylint call. Note, that the pruning of the search tree also reduces the list of output results, since all manifolds that are simple rotated versions of each other, get suppressed automatically.
* [packaging] prepare 0.55.1logilab-common-version-0.55.1Nicolas Chauvat2011-03-281-1/+1
|
* fix call to dot via subprocess: linux seems to need the shell=False, while ↵Alexandre Fayolle2011-03-021-2/+6
| | | | windows requires shell=True...
* [graph] fix command line construction bugAlexandre Fayolle2011-02-241-6/+5
|
* fix the ordered_nodes fix by reverting to previous orderNicolas Chauvat2011-02-091-2/+5
|
* graph: fix and test ordered_nodes() [closes #60288]Nicolas Chauvat2011-01-311-19/+29
|
* cleanup: remove deprecated compat importsEmile Anclin2010-11-221-1/+1
|
* 2to3: fix a lot of white space after commaEmile Anclin2010-11-151-1/+1
|
* py3k: use str_encode for lgc.graphEmile Anclin2010-11-021-5/+2
|
* py3.x compat: pass a key to sortedEmile Anclin2010-10-181-1/+1
|
* py2.3 compat : import compat.set, remove deprecated stuffSylvain Th?nault2010-09-241-1/+2
|
* import locally so graph is still importable with 2.3Sylvain Th?nault2010-09-211-1/+1
|
* don't raise string exception in testlib (closes #35331)Sylvain Th?nault2010-07-011-4/+4
|
* missing replacement in disclaimer; include COPYING.LESSER in manifest; kill ↵Sylvain Th?nault2010-04-281-1/+1
| | | | DEPENDS file
* propre licensing information (LGPL-2.1). Hope I get it right this time.Sylvain Th?nault2010-04-281-3/+20
|
* add docstringSylvain Th?nault2010-04-201-0/+7
|
* graph: new ordered_nodes method to return an ordered list of nodes from a graphSylvain Th?nault2010-04-161-0/+27
|
* generate methods now takes an optional mapfile argument to generate html ↵katia2010-04-131-4/+8
| | | | image maps
* update license, logilab-common is licensed under LGPLv2Adrien Di Mascio2010-04-131-2/+2
|
* mergelogilab-common-version-0.45.2Sylvain Th?nault2009-11-231-3/+3
|\
| * fix has_path returned value to include the destination node, else we getSylvain Th?nault2009-11-121-3/+3
| | | | | | | | an empty list which makes think there is no path (test added)
* | include Dotan Barak spell fixes patchSylvain Th?nault2009-11-231-1/+1
|/
* fix file descriptor leak with an incorrect use of mkstempAurelien Campeas2009-09-091-5/+4
|
* win32 adjustmentsAurelien Campeas2009-09-081-3/+9
|
* [cleanup] delete-trailing-whitespaceNicolas Chauvat2009-07-191-6/+6
|
* use endswith methodEmile Anclin2009-05-071-1/+1
|
* fix double ".dot" extension using outpufile="name.dot"Emile Anclin2009-05-061-4/+8
|
* have a link to graphviz.org in docstringEmile Anclin2009-04-141-4/+6
|
* fix typos; little code _get_cycle simplificationEmile Anclin2009-04-091-11/+8
|
* fix dot files' edge generationAdrien Di Mascio2008-11-131-1/+1
| | | | | | | | | | | | | | | | | | | | | Before this patch, edges were defined using the following scheme : Node1 -> Node2 edge [attrs...] Node2 -> Node3 which `dot` understands as three instructions : Node1 -> Node2 ; edge [attr...]; Node2 -> Node3; which means that edge properties are applied to the Node2->Node3 edge rather than to the Node1->Node2 edge. The correct syntax is : Node1 -> Node2 [attr...]; Node2 -> Node3;
* new has_path methodSylvain Thenault2008-10-031-0/+19
|
* fix emit_edge bug #5945Emile Anclin2008-09-091-3/+3
|
* make plattform independent temporary fileEmile Anclin2008-08-201-9/+12
|
* put dotsource in /tmp to avoid deleting a dotfile previously in storedirEmile Anclin2008-08-201-1/+3
|
* improve dots backends configurationPierre-Yves David2008-07-281-2/+6
|
* improve doc for better epydoc generation (again).Nicolas Chauvat2008-07-141-2/+4
|
* improve doc for better epydoc generation.Nicolas Chauvat2008-07-131-13/+14
|
* doc updateSylvain2008-02-081-3/+4
|
* explicit charset declaration in the dot fileSylvain2007-08-221-1/+5
|
* fix escape for DOT node ids.Adrien Di Mascio2007-05-031-1/+2
| | | | | | | | | | | | | | | | | The doc says : ... node_id : ID [ port ] ... and later: An ID is one of the following: - Any string of alphabetic characters, underscores or digits, not beginning with a digit; - a number [-]?(.[0-9]+ | [0-9]+(.[0-9]*)? ); - any double-quoted string ("...") possibly containing escaped quotes (\"); - an HTML string (<...>). so just quoting the node id seems enough
* graph name written in the dot file has to be normalizedSylvain2007-04-091-1/+1
|
* replace - by _ in dot node idSylvain2007-03-061-3/+5
|
* remove cvs kwSylvain2006-12-111-1/+0
|
* added missing importsAdrien Di Mascio2006-10-231-0/+3
|
* backport a dot backend from yamsSylvain2006-10-221-0/+155
View Lorry Controller Status