summaryrefslogtreecommitdiffstats
path: root/lib/puppet/simple_graph.rb
Commit message (Collapse)AuthorAgeFilesLines
* Removed extra whitespace from end of linesIan Taylor2009-06-061-12/+12
|
* Fix #2218 - Ruby YAML bug prevents reloading catalog in puppetdBrice Figureau2009-05-021-14/+0
| | | | | | | | | | | | | | | | | | | Because of ruby bug: http://rubyforge.org/tracker/?group_id=426&atid=1698&func=detail&aid=8886 and http://redmine.ruby-lang.org/issues/show/1331 YAML dump of hashes using ruby objects as keys is incorrect leading to an error when deserializing the YAML in puppetd. The error is easy to correct by a post-process fix-up of the generated YAML, which transforms: &id004 !ruby/object:Puppet::Relationship ? to the correct: ? &id004 !ruby/object:Puppet::Relationship Signed-off-by: Brice Figureau <brice-puppet@daysofwonder.com>
* Fixed #2188 - Added set require to simple_graph.rbJames Turnbull2009-04-271-0/+1
|
* Always making sure graph edges appear firstLuke Kanies2009-04-241-1/+11
| | | | | | | If we don't do this, there's a chance we'll get hit by the ruby yaml bug again. Signed-off-by: Luke Kanies <luke@madstop.com>
* Reverting part of the switch to sets in SimpleGraphLuke Kanies2009-04-241-3/+3
| | | | | | | | | Unfortunately, again because of a Ruby bug (http://rubyforge.org/tracker/?group_id=426&atid=1698&func=detail&aid=8886) Ruby can't print yaml that it can read, if custom classes are used as keys in hashes, which Sets use internally. Signed-off-by: Luke Kanies <luke@madstop.com>
* Fixing #2182 - SimpleGraph#walk is now iterativeLuke Kanies2009-04-221-4/+15
| | | | | | | | It was previously recursive, and was causing significant performance problems for large, wide graphs. Signed-off-by: Luke Kanies <luke@madstop.com>
* Fixing #2181 - Using Sets instead of Arrays in SimpleGraphLuke Kanies2009-04-221-10/+10
| | | | | | This can cause a huge speedup for large numbers of edges. Signed-off-by: Luke Kanies <luke@madstop.com>
* Fixing #2111 - SimpleGraph only creates valid adjacenciesLuke Kanies2009-04-121-1/+1
| | | | | | | | | | | The way this class was testing edges was causing them to appear adjacencies to appear magically, because it was only testing that a hash had a key, not that the value had any edges. This fixes the infinite recursion mentioned in #2111. Signed-off-by: Luke Kanies <luke@madstop.com>
* Removing duplicate method definition from SimpleGraphLuke Kanies2009-04-121-8/+0
| | | | Signed-off-by: Luke Kanies <luke@madstop.com>
* Fixed #1849 - Ruby 1.9 portability: `when' doesn't like colons, replace with ↵James Turnbull2009-02-261-1/+1
| | | | semicolons
* Removing the Hash default proc from SimpleGraph.Luke Kanies2009-02-061-5/+21
| | | | | | | Again, necessary so that the class can be dumped in Marshal or YAML. Signed-off-by: Luke Kanies <luke@madstop.com>
* Adding SimpleGraph#leaves, which I apparently did not migrate from PGraphLuke Kanies2008-11-061-0/+7
| | | | Signed-off-by: Luke Kanies <luke@madstop.com>
* Removing the PGraph class and subsuming it into SimpleGraph.Luke Kanies2008-11-061-0/+103
| | | | | | | This class is a holdover from when I was using GRATR, and it's obsolete now. Signed-off-by: Luke Kanies <luke@madstop.com>
* Moving Catalog#write_graph to SimpleGraph, where it belongs.Luke Kanies2008-11-061-0/+12
| | | | Signed-off-by: Luke Kanies <luke@madstop.com>
* Fixed #1021 -- the problem was that my method of determiningLuke Kanies2008-02-131-6/+9
| | | | | the in-degree sometimes resulted in a lower number than the number of in-edges.
* Removing the last remaining vestiges of GRATR --Luke Kanies2008-02-111-4/+4
| | | | removing the bangs from 'add_vertex!' and 'add_edge!'.
* Fixing #982 -- I have completely removed the GRATR graph libraryLuke Kanies2008-01-071-7/+71
| | | | from the system, and implemented my own topsort method.
* Fixing #937 -- I had not ported the dot methods at all,Luke Kanies2007-12-111-2/+2
| | | | and I had to make a few small changes to make them work.
* Switching the graph base class from GRATR::DigraphLuke Kanies2007-11-071-4/+78
| | | | | | to Puppet::SimpleGraph, which should dramatically enhance performance. It should be largely functionally equivalent, with the only difference being that edges are no longer deduplicated.
* Adding a new graphing base class, because the GRATR stuffLuke Kanies2007-11-071-0/+177
is just too slow. This class has just about no iteration, and vertex deletation is dramatically (as in, 1000x) faster). Here are the results of some very simplistic graph operations: Vertex tests (add and remove 1000 vertices): gratr: Add: 0.01; Remove: 9.70 simple: Add: 0.02; Remove: 0.01 Edge tests (add and remove 1000 edges): gratr: Add: 0.02; Remove: 0.03 simple: Add: 0.07; Remove: 0.02 I expect I can get the cost of the edge addition down some, but even as it is, it's a couple of orders of magnitude faster. This doesn't even count things like searching, which I did some other testing on and got consistently faster results (somewhere between 1.5x and 1500x faster, depending on how the test was set up and how big the graph was).
generated by cgit (git 2.34.1) at 2025-09-25 18:36:02 +0000