History log of /inkscape/src/libvpsc/pairingheap/PairingHeap.cpp
Revision Date Author Comments Expand
36d9047104b5881ca587a71ade77b1f21d083bc4 25-Oct-2011 Jon A. Cruz <jon@joncruz.org>

Cleanup pass on documentation that was dumping garbage into doxygen output.

/inkscape/src/2geom/basic-intersection.h /inkscape/src/2geom/conic_section_clipper.h /inkscape/src/2geom/conic_section_clipper_cr.h /inkscape/src/2geom/conic_section_clipper_impl.h /inkscape/src/2geom/conicsec.h /inkscape/src/2geom/convex-cover.h /inkscape/src/2geom/ellipse.h /inkscape/src/2geom/geom.h /inkscape/src/2geom/linear.h /inkscape/src/2geom/nearest-point.h /inkscape/src/2geom/piecewise.h /inkscape/src/2geom/sbasis-geometric.h /inkscape/src/2geom/sbasis-math.h /inkscape/src/2geom/sbasis-poly.h /inkscape/src/2geom/sbasis.h /inkscape/src/2geom/shape.h /inkscape/src/2geom/svg-path-parser.h /inkscape/src/2geom/svg-path.h /inkscape/src/2geom/toposweep.h /inkscape/src/bind/javabind-private.h /inkscape/src/bind/javabind.h /inkscape/src/bind/javainc/jni.h /inkscape/src/color-rgba.h /inkscape/src/color.h /inkscape/src/desktop.h /inkscape/src/display/canvas-temporary-item-list.h /inkscape/src/display/canvas-temporary-item.h /inkscape/src/display/curve.h /inkscape/src/display/grayscale.h /inkscape/src/display/nr-filter-utils.h /inkscape/src/display/snap-indicator.h /inkscape/src/display/sodipodi-ctrlrect.h /inkscape/src/display/sp-canvas-group.h /inkscape/src/display/sp-canvas-item.h /inkscape/src/display/sp-canvas.h /inkscape/src/dom/css.h /inkscape/src/dom/cssreader.h /inkscape/src/dom/dom.h /inkscape/src/dom/domimpl.h /inkscape/src/dom/domptr.h /inkscape/src/dom/domstring.h /inkscape/src/dom/events.h /inkscape/src/dom/io/base64stream.h /inkscape/src/dom/io/bufferstream.h /inkscape/src/dom/io/domstream.h /inkscape/src/dom/io/gzipstream.h /inkscape/src/dom/io/stringstream.h /inkscape/src/dom/io/uristream.h /inkscape/src/dom/ls.h /inkscape/src/dom/lsimpl.h /inkscape/src/dom/odf/odfdocument.h /inkscape/src/dom/smil.h /inkscape/src/dom/smilimpl.h /inkscape/src/dom/stylesheets.h /inkscape/src/dom/svg.h /inkscape/src/dom/svg2.h /inkscape/src/dom/svgimpl.h /inkscape/src/dom/svgreader.h /inkscape/src/dom/svgtypes.h /inkscape/src/dom/traversal.h /inkscape/src/dom/ucd.h /inkscape/src/dom/uri.h /inkscape/src/dom/util/digest.h /inkscape/src/dom/util/thread.h /inkscape/src/dom/util/ziptool.h /inkscape/src/dom/views-level3.h /inkscape/src/dom/views.h /inkscape/src/dom/xmlreader.h /inkscape/src/dom/xmlwriter.h /inkscape/src/dom/xpath.h /inkscape/src/dom/xpathimpl.h /inkscape/src/dom/xpathparser.h /inkscape/src/dom/xpathtoken.h /inkscape/src/event-context.h /inkscape/src/event-log.h /inkscape/src/extension/internal/gimpgrad.h /inkscape/src/extension/internal/odf.h /inkscape/src/extension/internal/pdfinput/pdf-input.h /inkscape/src/extension/internal/pdfinput/pdf-parser.h /inkscape/src/extension/internal/pdfinput/svg-builder.h /inkscape/src/extension/script/InkscapeScript.h /inkscape/src/gc-anchored.h /inkscape/src/gc-soft-ptr.h /inkscape/src/graphlayout.h /inkscape/src/guide-snapper.h /inkscape/src/help.h /inkscape/src/helper-fns.h /inkscape/src/helper/geom-curves.h /inkscape/src/helper/geom-nodetype.h /inkscape/src/helper/geom.h /inkscape/src/io/base64stream.h /inkscape/src/io/gzipstream.h /inkscape/src/io/inkscapestream.h /inkscape/src/io/resource.h /inkscape/src/io/uristream.h /inkscape/src/io/xsltstream.h /inkscape/src/knot-enums.h /inkscape/src/knot-holder-entity.h /inkscape/src/libcola/defs.h /inkscape/src/libvpsc/block.h /inkscape/src/libvpsc/csolve_VPSC.h PairingHeap.cpp PairingHeap.h /inkscape/src/libvpsc/solve_VPSC.h /inkscape/src/libvpsc/variable.h /inkscape/src/line-snapper.h /inkscape/src/object-hierarchy.h /inkscape/src/object-snapper.h /inkscape/src/registrytool.h /inkscape/src/rubberband.h /inkscape/src/selection.h /inkscape/src/snap-candidate.h /inkscape/src/snap-enums.h /inkscape/src/snap-preferences.h /inkscape/src/sp-gradient.h /inkscape/src/sp-object.h /inkscape/src/sp-offset.h /inkscape/src/sp-spiral.h /inkscape/src/svg-view-widget.h /inkscape/src/svg-view.h /inkscape/src/svg/path-string.h /inkscape/src/trace/siox.h /inkscape/src/trace/trace.h /inkscape/src/ui/dialog/guides.h /inkscape/src/ui/view/edit-widget-interface.h /inkscape/src/ui/view/view-widget.h /inkscape/src/ui/view/view.h /inkscape/src/ui/widget/attr-widget.h /inkscape/src/ui/widget/button.h /inkscape/src/ui/widget/color-preview.h /inkscape/src/ui/widget/combo-enums.h /inkscape/src/ui/widget/dock-item.h /inkscape/src/ui/widget/entity-entry.h /inkscape/src/ui/widget/entry.h /inkscape/src/ui/widget/handlebox.h /inkscape/src/ui/widget/icon-widget.h /inkscape/src/ui/widget/labelled.h /inkscape/src/ui/widget/licensor.h /inkscape/src/ui/widget/notebook-page.h /inkscape/src/ui/widget/page-sizer.h /inkscape/src/ui/widget/panel.h /inkscape/src/ui/widget/point.h /inkscape/src/ui/widget/preferences-widget.h /inkscape/src/ui/widget/random.h /inkscape/src/ui/widget/registered-enums.h /inkscape/src/ui/widget/registered-widget.h /inkscape/src/ui/widget/registry.h /inkscape/src/ui/widget/rendering-options.h /inkscape/src/ui/widget/rotateable.h /inkscape/src/ui/widget/ruler.h /inkscape/src/ui/widget/scalar-unit.h /inkscape/src/ui/widget/scalar.h /inkscape/src/ui/widget/selected-style.h /inkscape/src/ui/widget/spin-slider.h /inkscape/src/ui/widget/style-subject.h /inkscape/src/ui/widget/svg-canvas.h /inkscape/src/ui/widget/text.h /inkscape/src/ui/widget/toolbox.h /inkscape/src/ui/widget/unit-menu.h /inkscape/src/ui/widget/zoom-status.h /inkscape/src/undo-stack-observer.h /inkscape/src/uri.h /inkscape/src/util/enums.h /inkscape/src/util/list.h /inkscape/src/verbs.h /inkscape/src/widgets/paint-selector.h
1ec681f88b68c6186b267afcce12c7fd667cc9f8 12-Jul-2006 tgdwyer <tgdwyer@users.sourceforge.net>

Previously graph layout was done using the Kamada-Kawai layout algorithm implemented in Boost. I am replacing this with a custom implementation of a constrained stress-majorization algorithm. The stress-majorization algorithm is more robust and has better convergence characteristics than Kamada-Kawai, and also simple constraints can be placed on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints). Another big advantage is that we no longer need Boost. I've tested the basic functionality, but I have yet to properly handle disconnected graphs or to properly scale the resulting layout. This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola.

/inkscape/configure.ac /inkscape/mkinstalldirs /inkscape/src/Makefile.am /inkscape/src/Makefile_insert /inkscape/src/graphlayout/graphlayout.cpp /inkscape/src/libcola/Makefile_insert /inkscape/src/libcola/cola.cpp /inkscape/src/libcola/cola.h /inkscape/src/libcola/conjugate_gradient.cpp /inkscape/src/libcola/conjugate_gradient.h /inkscape/src/libcola/cycle_detector.cpp /inkscape/src/libcola/cycle_detector.h /inkscape/src/libcola/defs.h /inkscape/src/libcola/gradient_projection.cpp /inkscape/src/libcola/gradient_projection.h /inkscape/src/libcola/shortest_paths.cpp /inkscape/src/libcola/shortest_paths.h /inkscape/src/libcola/straightener.cpp /inkscape/src/libcola/straightener.h /inkscape/src/libvpsc/COPYING /inkscape/src/libvpsc/Makefile_insert /inkscape/src/libvpsc/block.cpp /inkscape/src/libvpsc/block.h /inkscape/src/libvpsc/blocks.cpp /inkscape/src/libvpsc/blocks.h /inkscape/src/libvpsc/constraint.cpp /inkscape/src/libvpsc/constraint.h /inkscape/src/libvpsc/csolve_VPSC.cpp /inkscape/src/libvpsc/csolve_VPSC.h /inkscape/src/libvpsc/generate-constraints.cpp /inkscape/src/libvpsc/generate-constraints.h /inkscape/src/libvpsc/isnan.h .dirstamp PairingHeap.cpp PairingHeap.h dsexceptions.h /inkscape/src/libvpsc/placement_SolveVPSC.h /inkscape/src/libvpsc/remove_rectangle_overlap.cpp /inkscape/src/libvpsc/remove_rectangle_overlap.h /inkscape/src/libvpsc/solve_VPSC.cpp /inkscape/src/libvpsc/solve_VPSC.h /inkscape/src/libvpsc/variable.cpp /inkscape/src/libvpsc/variable.h /inkscape/src/removeoverlap/Makefile_insert /inkscape/src/removeoverlap/pairingheap/.cvsignore /inkscape/src/removeoverlap/placement_SolveVPSC.cpp /inkscape/src/removeoverlap/remove_rectangle_overlap-test.cpp /inkscape/src/removeoverlap/removeoverlap.cpp