#include "uvedit_clipboard_graph_iso.hh"
#include "BLI_assert.h"
#include "MEM_guardedalloc.h"
#include <algorithm>
#include <climits>

Classes
class	GraphISO_DegreeCompare

Macros
#define	L 0

#define	R 1

#define	LL 2

#define	RL 3

#define	ADJ 4

#define	P 5

#define	W 6

#define	IRL 7

#define	BDS 8

Functions
static void	update_incumbent (uint8_t cur[][2], int inc[][2], int cur_pos, int *inc_pos)

static void	add_bidomain (uint8_t domains[][BDS], int *bd_pos, uint8_t left_i, uint8_t right_i, uint8_t left_len, uint8_t right_len, uint8_t is_adjacent, uint8_t cur_pos)

static int	calc_bound (const uint8_t domains[][BDS], int bd_pos, int cur_pos)

static int	partition (uint8_t arr, int start, int len, const uint8_t adjrow)

static void	generate_next_domains (uint8_t domains[][BDS], int bd_pos, int cur_pos, uint8_t left, uint8_t right, uint8_t v, uint8_t w, int inc_pos, uint8_t adjmat0, uint8_t *adjmat1)

static uint8_t	select_next_v (uint8_t left, uint8_t bd)

static uint8_t	find_min_value (const uint8_t *arr, uint8_t start_idx, uint8_t len)

static void	select_bidomain (uint8_t domains[][BDS], int bd_pos, const uint8_t *left, int current_matching_size, bool connected)

static uint8_t	select_next_w (const uint8_t right, uint8_t bd)

static void	maximum_common_subgraph_internal (int incumbent[][2], int inc_pos, uint8_t adjmat0, int n0, uint8_t adjmat1, int n1, bool r_search_abandoned)

static bool	check_automorphism (const GraphISO g0, const GraphISO g1, int solution[][2], int *solution_length)

bool	ED_uvedit_clipboard_maximum_common_subgraph (GraphISO g0_input, GraphISO g1_input, int solution[][2], int solution_length, bool r_search_abandoned)

Macro Definition Documentation

◆ ADJ

#define ADJ 4

Definition at line 23 of file uvedit_clipboard_graph_iso.cc.

Referenced by add_bidomain(), generate_next_domains(), and select_bidomain().

◆ BDS

#define BDS 8

Definition at line 28 of file uvedit_clipboard_graph_iso.cc.

Referenced by maximum_common_subgraph_internal(), and select_bidomain().

◆ IRL

#define IRL 7

Definition at line 26 of file uvedit_clipboard_graph_iso.cc.

Referenced by add_bidomain(), calc_bound(), maximum_common_subgraph_internal(), and select_next_v().

◆ L

#define L 0

Definition at line 19 of file uvedit_clipboard_graph_iso.cc.

Referenced by add_bidomain(), generate_next_domains(), maximum_common_subgraph_internal(), select_bidomain(), select_next_v(), and update_incumbent().

◆ LL

#define LL 2

Definition at line 21 of file uvedit_clipboard_graph_iso.cc.

Referenced by add_bidomain(), BLI_uuid_generate_random(), calc_bound(), generate_next_domains(), maximum_common_subgraph_internal(), select_bidomain(), select_next_v(), seq_disk_cache_read_header(), and seq_disk_cache_write_header().

◆ P

#define P 5

Definition at line 24 of file uvedit_clipboard_graph_iso.cc.

Referenced by _btMprVec3PointSegmentDist2(), add_bidomain(), Mesh::add_vertex(), Mesh::add_vertex_slow(), btDeformableCorotatedForce::addScaledElasticForce(), btDeformableLinearElasticityForce::addScaledElasticForce(), btDeformableNeoHookeanForce::addScaledElasticForce(), btDeformableLinearElasticityForce::addScaledHessian(), area_light_intersect(), area_light_mnee_sample_update(), area_light_rect_sample(), area_light_sample(), area_light_spread_clamp_light(), area_light_tree_parameters(), area_light_valid_ray_segment(), assign_final_coords_from_mdisps(), assign_final_elements_from_orig_mdisps(), attr_create_motion_from_velocity(), attr_create_motion_from_velocity(), attr_create_motion_from_velocity(), background_light_pdf(), background_light_sample(), background_num_possible_portals(), background_portal_data_fetch_and_check_side(), background_portal_pdf(), background_portal_sample(), bake_offset_towards_center(), Hair::Curve::bounds_grow(), Hair::Curve::bounds_grow(), Hair::Curve::bounds_grow(), Hair::Curve::bounds_grow(), PointCloud::Point::bounds_grow(), btMprVec3PointTriDist2(), btVec3PointSegmentDist2(), btVec3PointTriDist2(), libmv::Build_Minimal2Point_PolynomialFactor(), BVH(), BVH(), BVH(), BVH(), bvh_aligned_node_intersect(), bvh_instance_pop(), bvh_instance_push(), bvh_node_intersect(), bvh_unaligned_node_intersect(), bvh_unaligned_node_intersect_child(), calc_bound(), camera_direction_from_point(), camera_distance(), camera_sample_orthographic(), camera_sample_panorama(), camera_sample_perspective(), camera_world_to_ndc(), camera_z_depth(), Freestyle::GridHelpers::closestPointToSegment(), Freestyle::OGF::compute_curvature_tensor(), compute_emitter_centroid_and_dir(), compute_v(), Freestyle::ComputeMaxError(), Mesh::copy_center_to_motion_step(), PointCloud::copy_center_to_motion_step(), decasteljau_bicubic(), decasteljau_cubic(), Freestyle::GeomUtils::distPointSegment(), libmv::EliminateRow(), Freestyle::StrokeShaders::CurvePiece::error(), libmv::EuclideanIntersect(), libmv::EuclideanResect(), libmv::euclidean_resection::EuclideanResectionPPnP(), BicubicPatch::eval(), LinearQuadPatch::eval(), QuadDice::eval_projected(), blender::opensubdiv::VolatileEvalOutput< SRC_VERTEX_BUFFER, EVAL_VERTEX_BUFFER, STENCIL_TABLE, PATCH_TABLE, EVALUATOR, DEVICE_CONTEXT >::evalPatches(), blender::opensubdiv::VolatileEvalOutput< SRC_VERTEX_BUFFER, EVAL_VERTEX_BUFFER, STENCIL_TABLE, PATCH_TABLE, EVALUATOR, DEVICE_CONTEXT >::evalPatchesWithDerivatives(), blender::opensubdiv::EvalOutputAPI::evaluateLimit(), evaluateLimit(), blender::opensubdiv::EvalOutputAPI::evaluatePatchesLimit(), evaluatePatchesLimit(), export_pointcloud_motion(), libmv::NViewDataSet::F(), libmv::F_FromCorrespondance_2points(), fast_sinpif(), btDeformableCorotatedForce::firstPiola(), btDeformableLinearElasticityForce::firstPiola(), btDeformableNeoHookeanForce::firstPiola(), libmv::FundamentalFrom7CorrespondencesLinear(), generate_next_domains(), get_left_probability(), OSLRenderServices::get_object_standard_attribute(), GPU_matrix_bind(), guiding_bsdf_init(), guiding_phase_init(), guiding_record_background(), guiding_record_bssrdf_segment(), guiding_record_light_surface_segment(), guiding_record_volume_segment(), Freestyle::GeomUtils::includePointTriangle(), libmv::ProjectiveReconstruction::InsertCamera(), integrate_light(), integrate_surface_bsdf_bssrdf_bounce(), integrate_surface_ray_portal(), integrator_eval_background_shader(), integrator_init_from_bake(), integrator_state_read_ray(), integrator_state_read_shadow_ray(), integrator_state_write_ray(), integrator_state_write_shadow_ray(), interp_m3_m3m3(), blender::math::interpolate(), libmv::isInFrontOfCamera(), libmv::isInFrontOfCamera(), kernel_displace_evaluate(), CCL_NAMESPACE_BEGIN::kernel_tex_image_interp_3d(), kernel_tex_image_interp_3d(), kernel_tex_image_interp_3d(), libmv::KRt_From_P(), light_sample(), light_sample(), light_sample_from_position(), light_sample_from_volume_segment(), light_sample_mis_weight_forward_background(), light_sample_mis_weight_forward_distant(), light_sample_mis_weight_forward_lamp(), light_sample_mis_weight_forward_surface(), light_sample_to_surface_shadow_ray(), light_sample_to_volume_shadow_ray(), light_sample_update(), light_tree_child_importance(), light_tree_cluster_select_emitter(), light_tree_cos_bound_subtended_angle(), light_tree_emitter_importance(), light_tree_node_importance(), light_tree_pdf(), light_tree_pdf(), light_tree_sample(), light_tree_to_local_space(), maximum_common_subgraph_internal(), motion_triangle_intersect(), motion_triangle_point_from_uv(), multires_reshape_apply_base_update_mesh_coords(), Freestyle::NewtonRaphsonRootFind(), object_grid_element_to_tangent_displacement(), object_inverse_position_transform(), object_position_transform(), Freestyle::VecMat::operator*(), osl_eval_nodes< SHADER_TYPE_SURFACE >(), osl_texture3d(), libmv::P_From_KRt(), point_light_intersect(), point_light_mnee_sample_update(), point_light_sample(), point_light_tree_parameters(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::Project(), libmv::ProjectionChangeAspectRatio(), libmv::ProjectionShiftPrincipalPoint(), libmv::ProjectiveResect(), ray_aligned_disk_intersect(), ray_cone_intersect(), ray_disk_intersect(), ray_infinite_cylinder_intersect(), ray_offset(), ray_optical_depth(), ray_plane_intersect(), libmv::NViewDataSet::Reproject(), libmv::resection::Resection(), libmv::RootMeanSquareError(), libmv::RootMeanSquareError(), QuadDice::scale_factor(), select_bidomain(), set_attribute_float3_3(), EdgeDice::set_vert(), shader_setup_from_displace(), shader_setup_from_sample(), shadow_ray_offset(), shadow_ray_setup(), shadow_ray_smooth_surface_offset(), single_scattering(), Freestyle::OGF::sphere_clip_vector(), spherical_stereo_transform(), spot_light_mnee_sample_update(), spot_light_sample(), spot_light_tree_parameters(), spot_light_valid_ray_segment(), svm_node_enter_bump_eval(), OSLRenderServices::texture3d(), OSLRenderServices::trace(), triangle_intersect(), triangle_light_sample(), triangle_light_tree_parameters(), triangle_light_valid_ray_segment(), triangle_point_from_uv(), triangle_point_normal(), triangle_vertices(), triangle_vertices_and_normals(), wireframe(), Camera::world_to_raster_size(), and xml_read_mesh().

◆ R

#define R 1

Definition at line 20 of file uvedit_clipboard_graph_iso.cc.

Referenced by add_bidomain(), generate_next_domains(), maximum_common_subgraph_internal(), select_next_w(), and update_incumbent().

◆ RL

#define RL 3

Definition at line 22 of file uvedit_clipboard_graph_iso.cc.

Referenced by add_bidomain(), generate_next_domains(), maximum_common_subgraph_internal(), select_bidomain(), select_next_v(), and select_next_w().

◆ W

Function Documentation

◆ add_bidomain()

static void add_bidomain	(	uint8_t	domains[][BDS],
		int *	bd_pos,
		uint8_t	left_i,
		uint8_t	right_i,
		uint8_t	left_len,
		uint8_t	right_len,
		uint8_t	is_adjacent,
		uint8_t	cur_pos )

static

Definition at line 138 of file uvedit_clipboard_graph_iso.cc.

References ADJ, IRL, L, LL, P, R, RL, UINT8_MAX, and W.

Referenced by generate_next_domains(), and maximum_common_subgraph_internal().

◆ calc_bound()

static int calc_bound	(	const uint8_t	domains[][BDS],
		int	bd_pos,
		int	cur_pos )

static

Definition at line 158 of file uvedit_clipboard_graph_iso.cc.

References IRL, LL, and P.

Referenced by maximum_common_subgraph_internal().

◆ check_automorphism()

static bool check_automorphism	(	const GraphISO *	g0,
		const GraphISO *	g1,
		int	solution[][2],
		int *	solution_length )

static

Definition at line 380 of file uvedit_clipboard_graph_iso.cc.

References GraphISO::adjmat, GraphISO::label, and GraphISO::n.

Referenced by ED_uvedit_clipboard_maximum_common_subgraph().

◆ ED_uvedit_clipboard_maximum_common_subgraph()

bool ED_uvedit_clipboard_maximum_common_subgraph	(	GraphISO *	g0_input,
		GraphISO *	g1_input,
		int	solution[][2],
		int *	solution_length,
		bool *	r_search_abandoned )

Find the maximum common subgraph between two graphs. (Can be used to find graph ismorphism.)

Returns: True when found.

Definition at line 404 of file uvedit_clipboard_graph_iso.cc.

References GraphISO::adjmat, check_automorphism(), GraphISO::label, maximum_common_subgraph_internal(), GraphISO::n, result, GraphISO::sort_vertices_by_degree(), and UINT8_MAX.

Referenced by find_isomorphism().

◆ find_min_value()

static uint8_t find_min_value	(	const uint8_t *	arr,
		uint8_t	start_idx,
		uint8_t	len )

static

Definition at line 241 of file uvedit_clipboard_graph_iso.cc.

References len, and UINT8_MAX.

Referenced by select_bidomain().

◆ generate_next_domains()

static void generate_next_domains	(	uint8_t	domains[][BDS],
		int *	bd_pos,
		int	cur_pos,
		uint8_t *	left,
		uint8_t *	right,
		uint8_t	v,
		uint8_t	w,
		int	inc_pos,
		uint8_t **	adjmat0,
		uint8_t **	adjmat1 )

static

Definition at line 179 of file uvedit_clipboard_graph_iso.cc.

References add_bidomain(), ADJ, L, LL, P, partition(), R, RL, v, and w().

Referenced by maximum_common_subgraph_internal().

◆ maximum_common_subgraph_internal()

static void maximum_common_subgraph_internal	(	int	incumbent[][2],
		int *	inc_pos,
		uint8_t **	adjmat0,
		int	n0,
		uint8_t **	adjmat1,
		int	n1,
		bool *	r_search_abandoned )