<commit_before>//////////////////////////////////////////////////////////////////////////
//
//  Copyright (c) 2012, <NAME>. All rights reserved.
//  Copyright (c) 2013-2014, Image Engine Design Inc. All rights reserved.
//
//  Redistribution and use in source and binary forms, with or without
//  modification, are permitted provided that the following conditions are
//  met:
//
//      * Redistributions of source code must retain the above
//        copyright notice, this list of conditions and the following
//        disclaimer.
//
//      * Redistributions in binary form must reproduce the above
//        copyright notice, this list of conditions and the following
//        disclaimer in the documentation and/or other materials provided with
//        the distribution.
//
//      * Neither the name of <NAME> nor the names of
//        any other contributors to this software may be used to endorse or
//        promote products derived from this software without specific prior
//        written permission.
//
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
//  IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
//  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
//  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
//  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
//  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
//  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
//  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
//  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
//  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
//////////////////////////////////////////////////////////////////////////

#include <cassert>

#include "boost/graph/adjacency_list.hpp"

#include "OpenEXR/ImathVec.h"

#include "IECore/BoundedKDTree.h"
#include "IECore/BoxAlgo.h"
#include "IECore/MessageHandler.h"

#include "Gaffer/Plug.h"
#include "Gaffer/DependencyNode.h"
#include "Gaffer/StandardSet.h"
#include "Gaffer/Dot.h"
#include "Gaffer/Switch.h"
#include "Gaffer/BoxOut.h"

#include "GafferUI/StandardGraphLayout.h"
#include "GafferUI/GraphGadget.h"
#include "GafferUI/Nodule.h"
#include "GafferUI/ConnectionGadget.h"
#include "GafferUI/NodeGadget.h"

using namespace std;
using namespace Imath;
using namespace IECore;
using namespace Gaffer;
using namespace GafferUI;

//////////////////////////////////////////////////////////////////////////
//
// Layout Engine
//
// Internal code for performing node positioning and layout, targeted
// at the kinds of graphs produced using the StandardNodeGadget.
//
// Such graphs are strongly directional, but nodes may accept connections
// on all sides, and connections may therefore flow horizontally /and/
// vertically within the same graph. Additionally, each connection endpoint
// is located at a specific fixed location on the node, so the relative
// position of inputs to a node is important when attempting to reduce
// unnecessary crossings among connections.
//
// Unfortunately, the standard layered drawing algorithms (such as Sugiyama's)
// are not a good fit for our purposes because they lay out nodes in a single
// direction only. Standard force directed algorithms are not a good match
// for us either, as they produce organic looking graphs which provide no
// control over the direction of connections, or mechanisms for explicitly
// reducing crossings.
//
// We adopt a hybrid approach where we combine force directed layout with
// additional hard constraints that enforce the directionality of connections
// and ordering of inputs to minimise crossings. This approach is based on
// ideas described in the following paper :
//
// Scalable, Versatile and Simple Constrained Graph Layout
// <NAME>
// Eurographics/ IEEE-VGTC Symposium on Visualization 2009
//
// The current implementation still has plenty of room for improvement -
// here are a few ideas worth exploring :
//
//    - Repulsive forces between nodes, proportional to the length
//      of the shortest path between them.
//
//    - Segmenting the graph into vertical and horizontal chunks
//      and grouping the nodes in the horizontal chunks after laying
//      them out separately. Or even better perhaps, preventing the
//      convex hulls of such chunks from overlapping using the method
//      described in the Dwyer paper.
//
//    - Alignment constraints between nodes with only a single
//      input/output.
//
//    - Investigating the balance between spring stiffness, number
//      of constraints iterations etc.
//
//////////////////////////////////////////////////////////////////////////

namespace
{

/// \todo Refactor into simple constraint in single axis,
/// remove LessThanOrEqualTo.
class Constraint
{

	public :

		enum Type
		{
			EqualTo,
			GreaterThanOrEqualTo,
			LessThanOrEqualTo
		};

		/// \todo Remove - it's only here so we can call m_constraints.resize()
		/// to remove the collision constraints.
		Constraint()
		{
		}

		// Enforces p - q ( ==, >=, <= ) d in direction v
		Constraint( V2f *p, V2f *q, Type type, float d, const V2f &v, float w = 0.5 )
			:	m_p( p ), m_q( q ), m_type( type ), m_d( d ), m_v( v ), m_w( w )
		{
		}

		void apply() const
		{
			const float p = m_v.dot( *m_p );
			const float q = m_v.dot( *m_q );
			const float separation = p - q;

			if(
				( m_type == EqualTo && separation == m_d ) ||
				( m_type == GreaterThanOrEqualTo && separation >= m_d ) ||
				( m_type == LessThanOrEqualTo && separation <= m_d )
			)
			{
				return;
			}

			const V2f r = m_v * (m_d - separation);
			*m_p += r * m_w;
			*m_q -= r * (1.0f - m_w);
		}

	private :

		V2f *m_p;
		V2f *m_q;
		Type m_type;
		float m_d;
		V2f m_v;
		float m_w;

};

class LayoutEngine
{

	public :

		LayoutEngine( GraphGadget *graphGadget, float edgeLengthScale, float nodeSeparationScale )
			:	m_graphGadget( graphGadget ),
				m_edgeLength( 5.0f * edgeLengthScale ),
				m_nodeSeparation( 2.0f * nodeSeparationScale ),
				m_springStiffness( 0.1 ),
				m_maxIterations( 10000 ),
				m_constraintsIterations( 10 )
		{

			// Convert the visible graph into our internal boost::graph format.
			// Start by putting all the visible nodes in the graph as vertices.
			// Build a map from node to vertex so we can use it to lookup nodes<commit_msg>GafferUI::StandardGraphLayout : Change autolayout default spacing from 5.0 to 4.0, since 4.0 looks tidy with new noodles<commit_after>//////////////////////////////////////////////////////////////////////////
//
//  Copyright (c) 2012, <NAME>. All rights reserved.
//  Copyright (c) 2013-2014, Image Engine Design Inc. All rights reserved.
//
//  Redistribution and use in source and binary forms, with or without
//  modification, are permitted provided that the following conditions are
//  met:
//
//      * Redistributions of source code must retain the above
//        copyright notice, this list of conditions and the following
//        disclaimer.
//
//      * Redistributions in binary form must reproduce the above
//        copyright notice, this list of conditions and the following
//        disclaimer in the documentation and/or other materials provided with
//        the distribution.
//
//      * Neither the name of <NAME> nor the names of
//        any other contributors to this software may be used to endorse or
//        promote products derived from this software without specific prior
//        written permission.
//
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
//  IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
//  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
//  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
//  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
//  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
//  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
//  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
//  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
//  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
//////////////////////////////////////////////////////////////////////////

#include <cassert>

#include "boost/graph/adjacency_list.hpp"

#include "OpenEXR/ImathVec.h"

#include "IECore/BoundedKDTree.h"
#include "IECore/BoxAlgo.h"
#include "IECore/MessageHandler.h"

#include "Gaffer/Plug.h"
#include "Gaffer/DependencyNode.h"
#include "Gaffer/StandardSet.h"
#include "Gaffer/Dot.h"
#include "Gaffer/Switch.h"
#include "Gaffer/BoxOut.h"

#include "GafferUI/StandardGraphLayout.h"
#include "GafferUI/GraphGadget.h"
#include "GafferUI/Nodule.h"
#include "GafferUI/ConnectionGadget.h"
#include "GafferUI/NodeGadget.h"

using namespace std;
using namespace Imath;
using namespace IECore;
using namespace Gaffer;
using namespace GafferUI;

//////////////////////////////////////////////////////////////////////////
//
// Layout Engine
//
// Internal code for performing node positioning and layout, targeted
// at the kinds of graphs produced using the StandardNodeGadget.
//
// Such graphs are strongly directional, but nodes may accept connections
// on all sides, and connections may therefore flow horizontally /and/
// vertically within the same graph. Additionally, each connection endpoint
// is located at a specific fixed location on the node, so the relative
// position of inputs to a node is important when attempting to reduce
// unnecessary crossings among connections.
//
// Unfortunately, the standard layered drawing algorithms (such as Sugiyama's)
// are not a good fit for our purposes because they lay out nodes in a single
// direction only. Standard force directed algorithms are not a good match
// for us either, as they produce organic looking graphs which provide no
// control over the direction of connections, or mechanisms for explicitly
// reducing crossings.
//
// We adopt a hybrid approach where we combine force directed layout with
// additional hard constraints that enforce the directionality of connections
// and ordering of inputs to minimise crossings. This approach is based on
// ideas described in the following paper :
//
// Scalable, Versatile and Simple Constrained Graph Layout
// <NAME>
// Eurographics/ IEEE-VGTC Symposium on Visualization 2009
//
// The current implementation still has plenty of room for improvement -
// here are a few ideas worth exploring :
//
//    - Repulsive forces between nodes, proportional to the length
//      of the shortest path between them.
//
//    - Segmenting the graph into vertical and horizontal chunks
//      and grouping the nodes in the horizontal chunks after laying
//      them out separately. Or even better perhaps, preventing the
//      convex hulls of such chunks from overlapping using the method
//      described in the Dwyer paper.
//
//    - Alignment constraints between nodes with only a single
//      input/output.
//
//    - Investigating the balance between spring stiffness, number
//      of constraints iterations etc.
//
//////////////////////////////////////////////////////////////////////////

namespace
{

/// \todo Refactor into simple constraint in single axis,
/// remove LessThanOrEqualTo.
class Constraint
{

	public :

		enum Type
		{
			EqualTo,
			GreaterThanOrEqualTo,
			LessThanOrEqualTo
		};

		/// \todo Remove - it's only here so we can call m_constraints.resize()
		/// to remove the collision constraints.
		Constraint()
		{
		}

		// Enforces p - q ( ==, >=, <= ) d in direction v
		Constraint( V2f *p, V2f *q, Type type, float d, const V2f &v, float w = 0.5 )
			:	m_p( p ), m_q( q ), m_type( type ), m_d( d ), m_v( v ), m_w( w )
		{
		}

		void apply() const
		{
			const float p = m_v.dot( *m_p );
			const float q = m_v.dot( *m_q );
			const float separation = p - q;

			if(
				( m_type == EqualTo && separation == m_d ) ||
				( m_type == GreaterThanOrEqualTo && separation >= m_d ) ||
				( m_type == LessThanOrEqualTo && separation <= m_d )
			)
			{
				return;
			}

			const V2f r = m_v * (m_d - separation);
			*m_p += r * m_w;
			*m_q -= r * (1.0f - m_w);
		}

	private :

		V2f *m_p;
		V2f *m_q;
		Type m_type;
		float m_d;
		V2f m_v;
		float m_w;

};

class LayoutEngine
{

	public :

		LayoutEngine( GraphGadget *graphGadget, float edgeLengthScale, float nodeSeparationScale )
			:	m_graphGadget( graphGadget ),
				m_edgeLength( 4.0f * edgeLengthScale ),
				m_nodeSeparation( 2.0f * nodeSeparationScale ),
				m_springStiffness( 0.1 ),
				m_maxIterations( 10000 ),
				m_constraintsIterations( 10 )
		{

			// Convert the visible graph into our internal boost::graph format.
			// Start by putting all the visible nodes in the graph as vertices.
			// Build a map from node to vertex so we can use it to lookup nodes
{'fraction_non_alphanumeric': 0.12938847003274692, 'fraction_numerical': 0.006549386946919504, 'mean_word_length': 2.647777777777778, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6596313', 'n_tokens_mistral': 3928, 'n_tokens_neox': 3574, 'n_words': 1520}