<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html xmlns:gcse="googleCustomSearch"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><link rel="shortcut icon" href="dlib-icon.ico"><meta name="verify-v1" content="02MiiaFNVzS5/u0eQhsy3/knioFHsia1X3DXRpHkE6I="><meta name="google-site-verification" content="DGSSJMKDomaDaDTIRJ8jDkv0YMx9Cz7OESbXHjjr6Jw"><title>dlib C++ Library
- Graph Tools</title><script type="text/javascript" src="dlib.js"></script><link rel="stylesheet" type="text/css" href="dlib.css"></head><body><a name="top"></a><div id="page_header"><a href="http://dlib.net"><img src="dlib-logo.png"></a></div><div id="top_content"><div id="main_menu" class="menu"><div class="menu_top"><b>The Library</b><ul class="tree"><li><a href="algorithms.html" class="menu">Algorithms</a></li><li><a href="api.html" class="menu">API Wrappers</a></li><li><a href="bayes.html" class="menu">Bayesian Nets</a></li><li><a href="compression.html" class="menu">Compression</a></li><li><a href="containers.html" class="menu">Containers</a></li><li><a href="graph_tools.html" class="menu">Graph Tools</a></li><li><a href="imaging.html" class="menu">Image Processing</a></li><li><a href="linear_algebra.html" class="menu">Linear Algebra</a></li><li><a href="ml.html" class="menu">Machine Learning</a></li><li><a href="metaprogramming.html" class="menu">Metaprogramming</a></li><li><a href="other.html" class="menu">Miscellaneous</a></li><li><a href="network.html" class="menu">Networking</a></li><li><a href="optimization.html" class="menu">Optimization</a></li><li><a href="parsing.html" class="menu">Parsing</a></li></ul><br><b>Help/Info</b><ul class="tree"><li><a href="http://blog.dlib.net" class="menu">Dlib Blog</a></li><li><a onclick="Toggle(this)" class="sub menu"><img src="plus.gif">Examples: C++</a><ul style="display:none;"><li><a href="3d_point_cloud_ex.cpp.html" class="menu">3D Point Cloud</a></li><li><a href="assignment_learning_ex.cpp.html" class="menu">Assignment Learning</a></li><li><a href="file_to_code_ex.cpp.html" class="menu">Base64 Encoder</a></li><li><a href="bayes_net_from_disk_ex.cpp.html" class="menu">Bayesian Network From Disk</a></li><li><a href="bayes_net_gui_ex.cpp.html" class="menu">Bayesian Network GUI</a></li><li><a href="bayes_net_ex.cpp.html" class="menu">Bayesian Network</a></li><li><a href="bridge_ex.cpp.html" class="menu">Bridge</a></li><li><a href="bsp_ex.cpp.html" class="menu">BSP</a></li><li><a href="svm_c_ex.cpp.html" class="menu">C-Support Vector Machine</a></li><li><a href="compress_stream_ex.cpp.html#_top" class="menu">Cmd Line Parser</a></li><li><a href="compress_stream_ex.cpp.html" class="menu">Compress Stream</a></li><li><a href="config_reader_ex.cpp.html" class="menu">Config File Reader</a></li><li><a href="custom_trainer_ex.cpp.html" class="menu">Custom Trainers</a></li><li><a href="dnn_face_recognition_ex.cpp.html" class="menu">Deep Face Recognition</a></li><li><a href="dnn_dcgan_train_ex.cpp.html" class="menu">Deep Learning DCGAN</a></li><li><a href="dnn_mmod_dog_hipsterizer.cpp.html" class="menu">Deep Learning Dog Hipsterizer</a></li><li><a href="dnn_mmod_face_detection_ex.cpp.html" class="menu">Deep Learning Face Detection</a></li><li><a href="dnn_imagenet_ex.cpp.html" class="menu">Deep Learning Imagenet Classifier</a></li><li><a href="dnn_imagenet_train_ex.cpp.html" class="menu">Deep Learning Imagenet Trainer </a></li><li><a href="dnn_inception_ex.cpp.html" class="menu">Deep Learning Inception</a></li><li><a href="dnn_instance_segmentation_train_ex.cpp.html" class="menu">Deep Learning Instance Segmentation Trainer</a></li><li><a href="dnn_instance_segmentation_ex.cpp.html" class="menu">Deep Learning Instance Segmentation</a></li><li><a href="dnn_introduction_ex.cpp.html" class="menu">Deep Learning Introduction Part 1</a></li><li><a href="dnn_introduction2_ex.cpp.html" class="menu">Deep Learning Introduction Part 2</a></li><li><a href="dnn_introduction3_ex.cpp.html" class="menu">Deep Learning Introduction Part 3</a></li><li><a href="dnn_mmod_ex.cpp.html" class="menu">Deep Learning Max-Margin Object Detection</a></li><li><a href="dnn_mmod_find_cars2_ex.cpp.html" class="menu">Deep Learning Multi-Class Vehicle Detection</a></li><li><a href="dnn_semantic_segmentation_train_ex.cpp.html" class="menu">Deep Learning Semantic Segmentation Trainer</a></li><li><a href="dnn_semantic_segmentation_ex.cpp.html" class="menu">Deep Learning Semantic Segmentation</a></li><li><a href="dnn_mmod_train_find_cars_ex.cpp.html" class="menu">Deep Learning Vehicle Detection Trainer</a></li><li><a href="dnn_mmod_find_cars_ex.cpp.html" class="menu">Deep Learning Vehicle Detection</a></li><li><a href="dnn_metric_learning_ex.cpp.html" class="menu">Deep Metric Learning Introduction</a></li><li><a href="dnn_metric_learning_on_images_ex.cpp.html" class="menu">Deep Metric Learning on Images</a></li><li><a href="dir_nav_ex.cpp.html" class="menu">Directory Navigation</a></li><li><a href="empirical_kernel_map_ex.cpp.html" class="menu">Empirical Kernel Map</a></li><li><a href="face_detection_ex.cpp.html" class="menu">Face Detection</a></li><li><a href="face_landmark_detection_ex.cpp.html" class="menu">Face Landmark Detection</a></li><li><a href="fhog_ex.cpp.html" class="menu">FHOG Feature Extraction</a></li><li><a href="fhog_object_detector_ex.cpp.html" class="menu">FHOG Object Detection</a></li><li><a href="graph_labeling_ex.cpp.html" class="menu">Graph Labeling</a></li><li><a href="gui_api_ex.cpp.html" class="menu">GUI</a></li><li><a href="hough_transform_ex.cpp.html" class="menu">Hough Transform</a></li><li><a href="server_http_ex.cpp.html" class="menu">HTTP Server</a></li><li><a href="image_ex.cpp.html" class="menu">Image</a></li><li><a href="iosockstream_ex.cpp.html" class="menu">IO Socket Streams</a></li><li><a href="server_iostream_ex.cpp.html" class="menu">IO Streams Server</a></li><li><a href="kcentroid_ex.cpp.html" class="menu">Kernel Centroid</a></li><li><a href="kkmeans_ex.cpp.html" class="menu">Kernel K-Means Clustering</a></li><li><a href="krr_regression_ex.cpp.html" class="menu">Kernel Ridge Regression</a></li><li><a href="krls_filter_ex.cpp.html" class="menu">Kernel RLS Filtering</a></li><li><a href="krls_ex.cpp.html" class="menu">Kernel RLS Regression</a></li><li><a href="krr_classification_ex.cpp.html" class="menu">KRR Classification</a></li><li><a href="learning_to_track_ex.cpp.html" class="menu">Learning to Track</a></li><li><a href="max_cost_assignment_ex.cpp.html" class="menu">Linear Assignment Problems</a></li><li><a href="linear_manifold_regularizer_ex.cpp.html" class="menu">Linear Manifold Regularizer</a></li><li><a href="mpc_ex.cpp.html" class="menu">Linear Model Predictive Control</a></li><li><a href="logger_ex_2.cpp.html" class="menu">Logger Advanced</a></li><li><a href="logger_custom_output_ex.cpp.html" class="menu">Logger Custom Output</a></li><li><a href="logger_ex.cpp.html" class="menu">Logger</a></li><li><a href="matrix_expressions_ex.cpp.html" class="menu">Matrix Expressions</a></li><li><a href="matrix_ex.cpp.html" class="menu">Matrix</a></li><li><a href="member_function_pointer_ex.cpp.html" class="menu">Member Function Pointer</a></li><li><a href="model_selection_ex.cpp.html" class="menu">Model Selection</a></li><li><a href="multiclass_classification_ex.cpp.html" class="menu">Multiclass Classification</a></li><li><a href="multithreaded_object_ex.cpp.html" class="menu">Multithreaded Object</a></li><li><a href="mlp_ex.cpp.html" class="menu">Neural Network</a></li><li><a href="least_squares_ex.cpp.html" class="menu">Non-Linear Least Squares</a></li><li><a href="svm_ex.cpp.html" class="menu">Nu-Support Vector Machine</a></li><li><a href="integrate_function_adapt_simp_ex.cpp.html" class="menu">Numerical Integration</a></li><li><a href="object_detector_advanced_ex.cpp.html" class="menu">Object Detector Advanced</a></li><li><a href="object_detector_ex.cpp.html" class="menu">Object Detector</a></li><li><a href="one_class_classifiers_ex.cpp.html" class="menu">One Class Classifiers</a></li><li><a href="svm_pegasos_ex.cpp.html" class="menu">Online SVM</a></li><li><a href="optimization_ex.cpp.html" class="menu">Optimization</a></li><li><a href="parallel_for_ex.cpp.html" class="menu">Parallel For Loops</a></li><li><a href="pipe_ex_2.cpp.html" class="menu">Pipe 2</a></li><li><a href="pipe_ex.cpp.html" class="menu">Pipe</a></li><li><a href="quantum_computing_ex.cpp.html" class="menu">Quantum Computing</a></li><li><a href="queue_ex.cpp.html" class="menu">Queue</a></li><li><a href="random_cropper_ex.cpp.html" class="menu">Random Cropper</a></li><li><a href="rank_features_ex.cpp.html" class="menu">Rank Features</a></li><li><a href="rvm_ex.cpp.html" class="menu">Relevance Vector Classification</a></li><li><a href="rvm_regression_ex.cpp.html" class="menu">Relevance Vector Regression</a></li><li><a href="running_stats_ex.cpp.html" class="menu">Running Stats</a></li><li><a href="sequence_labeler_ex.cpp.html" class="menu">Sequence Labeling</a></li><li><a href="sequence_segmenter_ex.cpp.html" class="menu">Sequence Segmentation</a></li><li><a href="sockets_ex.cpp.html" class="menu">Sockets</a></li><li><a href="sockstreambuf_ex.cpp.html" class="menu">Sockstreambuf</a></li><li><a href="svm_sparse_ex.cpp.html" class="menu">Sparse Vectors</a></li><li><a href="sqlite_ex.cpp.html" class="menu">SQLite</a></li><li><a href="std_allocator_ex.cpp.html" class="menu">Std C++ Allocator</a></li><li><a href="svm_struct_ex.cpp.html" class="menu">Structural Support Vector Machines</a></li><li><a href="svr_ex.cpp.html" class="menu">Support Vector Regression</a></li><li><a href="surf_ex.cpp.html" class="menu">SURF</a></li><li><a href="svm_rank_ex.cpp.html" class="menu">SVM-Rank</a></li><li><a href="thread_function_ex.cpp.html" class="menu">Thread Function</a></li><li><a href="thread_pool_ex.cpp.html" class="menu">Thread Pool</a></li><li><a href="threaded_object_ex.cpp.html" class="menu">Threaded Object</a></li><li><a href="threads_ex.cpp.html" class="menu">Threads</a></li><li><a href="timer_ex.cpp.html" class="menu">Timer</a></li><li><a href="train_object_detector.cpp.html" class="menu">Train Object Detector</a></li><li><a href="train_shape_predictor_ex.cpp.html" class="menu">Train Shape Predictor</a></li><li><a href="using_custom_kernels_ex.cpp.html" class="menu">Using Custom Kernels</a></li><li><a href="video_tracking_ex.cpp.html" class="menu">Video Object Tracking</a></li><li><a href="webcam_face_pose_ex.cpp.html" class="menu">Webcam Face Pose Estimation</a></li><li><a href="xml_parser_ex.cpp.html" class="menu">XML Parser</a></li></ul></li><li><a onclick="Toggle(this)" class="sub menu"><img src="plus.gif">Examples: Python</a><ul style="display:none;"><li><a href="svm_binary_classifier.py.html" class="menu">Binary Classification</a></li><li><a href="cnn_face_detector.py.html" class="menu">CNN Face Detector</a></li><li><a href="face_alignment.py.html" class="menu">Face Alignment</a></li><li><a href="face_clustering.py.html" class="menu">Face Clustering</a></li><li><a href="face_detector.py.html" class="menu">Face Detector</a></li><li><a href="face_jitter.py.html" class="menu">Face Jittering/Augmentation</a></li><li><a href="face_landmark_detection.py.html" class="menu">Face Landmark Detection</a></li><li><a href="face_recognition.py.html" class="menu">Face Recognition</a></li><li><a href="find_candidate_object_locations.py.html" class="menu">Find Candidate Object Locations</a></li><li><a href="global_optimization.py.html" class="menu">Global Optimization</a></li><li><a href="max_cost_assignment.py.html" class="menu">Linear Assignment Problems</a></li><li><a href="sequence_segmenter.py.html" class="menu">Sequence Segmenter</a></li><li><a href="svm_struct.py.html" class="menu">Structural Support Vector Machines</a></li><li><a href="svm_rank.py.html" class="menu">SVM-Rank</a></li><li><a href="train_object_detector.py.html" class="menu">Train Object Detector</a></li><li><a href="train_shape_predictor.py.html" class="menu">Train Shape Predictor</a></li><li><a href="correlation_tracker.py.html" class="menu">Video Object Tracking</a></li></ul></li><li><a href="faq.html" class="menu">FAQ</a></li><li><a href="index.html" class="menu">Home</a></li><li><a href="compile.html" class="menu">How to compile</a></li><li><a href="howto_contribute.html" class="menu">How to contribute</a></li><li><a href="term_index.html" class="menu">Index</a></li><li><a href="intro.html" class="menu">Introduction</a></li><li><a href="license.html" class="menu">License</a></li><li><a href="python/index.html" class="menu">Python API</a></li><li><a href="books.html" class="menu">Suggested Books</a></li><li><a href="http://sourceforge.net/p/dclib/wiki/Known_users/" class="menu">Who uses dlib?</a></li></ul><br><b>Current Release</b><ul class="tree"><li><a href="change_log.html" class="menu">Change Log</a></li><li><a href="release_notes.html" class="menu">Release Notes</a></li><li>Version: 19.22</li></ul><br></div><div class="menu_footer">
Last Modified:<br>Sep 13, 2015</div></div><div id="main_text"><div id="main_text_title">Graph Tools</div><div id="main_text_body"><p>
In dlib, there are two types of graph representations. On the one
hand, there are graphs based on an object which encapsulates the whole
graph, such as the <a href="containers.html#graph">graph</a> and
<a href="containers.html#directed_graph">directed_graph</a> objects. On the
other hand, there are graphs which are represented as simple vectors
of edges. In this case, we use vectors of <a href="#sample_pair">sample_pair</a>
or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects for undirected
and directed graphs respectively.
</p></div></div><div id="right_menu" class="menu"><div class="menu_top"><b>Graph Object Based Graphs</b><ul class="tree"><li><a href="#copy_graph" class="menu">copy_graph</a></li><li><a href="#copy_graph_structure" class="menu">copy_graph_structure</a></li><li><a href="#create_join_tree" class="menu">create_join_tree</a></li><li><a href="#create_moral_graph" class="menu">create_moral_graph</a></li><li><a href="#edge" class="menu">edge</a></li><li><a href="#find_connected_nodes" class="menu">find_connected_nodes</a></li><li><a href="#graph_contains_directed_cycle" class="menu">graph_contains_directed_cycle</a></li><li><a href="#graph_contains_length_one_cycle" class="menu">graph_contains_length_one_cycle</a></li><li><a href="#graph_contains_undirected_cycle" class="menu">graph_contains_undirected_cycle</a></li><li><a href="#graph_has_symmetric_edges" class="menu">graph_has_symmetric_edges</a></li><li><a href="#graph_is_connected" class="menu">graph_is_connected</a></li><li><a href="#is_clique" class="menu">is_clique</a></li><li><a href="#is_join_tree" class="menu">is_join_tree</a></li><li><a href="#is_maximal_clique" class="menu">is_maximal_clique</a></li><li><a href="#triangulate_graph_and_find_cliques" class="menu">triangulate_graph_and_find_cliques</a></li></ul><br><b>Creating Edge List Based Graphs</b><ul class="tree"><li><a onclick="Toggle(this)" class="sub menu"><img src="plus.gif">Distance Functions</a><ul style="display:none;"><li><a href="#cosine_distance" class="menu">cosine_distance</a></li><li><a href="#negative_dot_product_distance" class="menu">negative_dot_product_distance</a></li><li><a href="#squared_euclidean_distance" class="menu">squared_euclidean_distance</a></li></ul></li><li><a href="#find_approximate_k_nearest_neighbors" class="menu">find_approximate_k_nearest_neighbors</a></li><li><a href="#find_k_nearest_neighbors" class="menu">find_k_nearest_neighbors</a></li><li><a href="#find_k_nearest_neighbors_lsh" class="menu">find_k_nearest_neighbors_lsh</a></li><li><a href="#find_percent_shortest_edges_randomly" class="menu">find_percent_shortest_edges_randomly</a></li><li><a href="#ordered_sample_pair" class="menu">ordered_sample_pair</a></li><li><a href="#sample_pair" class="menu">sample_pair</a></li></ul><br><b>Using Edge List Based Graphs</b><ul class="tree"><li><a href="#contains_duplicate_pairs" class="menu">contains_duplicate_pairs</a></li><li><a href="#convert_unordered_to_ordered" class="menu">convert_unordered_to_ordered</a></li><li><a href="#find_neighbor_ranges" class="menu">find_neighbor_ranges</a></li><li><a href="#is_ordered_by_index" class="menu">is_ordered_by_index</a></li><li><a href="#max_index_plus_one" class="menu">max_index_plus_one</a></li><li><a href="#order_by_descending_distance" class="menu">order_by_descending_distance</a></li><li><a href="#order_by_distance" class="menu">order_by_distance</a></li><li><a href="#order_by_distance_and_index" class="menu">order_by_distance_and_index</a></li><li><a href="#order_by_index" class="menu">order_by_index</a></li><li><a href="#remove_duplicate_edges" class="menu">remove_duplicate_edges</a></li><li><a href="#remove_long_edges" class="menu">remove_long_edges</a></li><li><a href="#remove_percent_longest_edges" class="menu">remove_percent_longest_edges</a></li><li><a href="#remove_percent_shortest_edges" class="menu">remove_percent_shortest_edges</a></li><li><a href="#remove_short_edges" class="menu">remove_short_edges</a></li><li><a href="#use_gaussian_weights" class="menu">use_gaussian_weights</a></li><li><a href="#use_weights_of_one" class="menu">use_weights_of_one</a></li></ul><br></div><div class="menu_footer"></div></div></div><div id="bottom_content"><a name="contains_duplicate_pairs"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">contains_duplicate_pairs</h1><BR><BR>
This function checks if a std::vector of <a href="#sample_pair">sample_pair</a> or
<a href="#ordered_sample_pair">ordered_sample_pair</a> objects
contains any edge more than once.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#contains_duplicate_pairs">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="convert_unordered_to_ordered"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">convert_unordered_to_ordered</h1><BR><BR>
This function takes a graph, defined by a vector of
<a href="#sample_pair">sample_pair</a> objects and converts it into the equivalent
graph defined by a vector of <a href="#ordered_sample_pair">ordered_sample_pair</a> objects.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#convert_unordered_to_ordered">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="copy_graph"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">copy_graph</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> or
<a href="containers.html#directed_graph">directed_graph</a> and
makes a copy of it.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#copy_graph">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="copy_graph_structure"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">copy_graph_structure</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> or
<a href="containers.html#directed_graph">directed_graph</a> and copies
its structure to another graph or directed_graph object. The only
restriction is that you can't copy the structure of a graph into a
directed_graph. The three other possible combinations are allowed
however.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#copy_graph_structure">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="cosine_distance"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">cosine_distance</h1><BR><BR>
This is a simple function object that computes cosine of the angle between
two vectors.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/function_objects_abstract.h.html#cosine_distance">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="create_join_tree"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">create_join_tree</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> object and
creates a join tree for that graph. Or in other words, this function finds a
tree decomposition of the given graph.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#create_join_tree">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="create_moral_graph"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">create_moral_graph</h1><BR><BR>
This function takes a <a href="containers.html#directed_graph">directed_graph</a>
and returns the moralized version of the graph in the form of a
<a href="containers.html#graph">graph</a> object.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#create_moral_graph">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="edge"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">edge</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> or
<a href="containers.html#directed_graph">directed_graph</a> object and a
pair of indices. It returns a reference to the edge object between the two nodes
with the given indices.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#edge">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="find_approximate_k_nearest_neighbors"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">find_approximate_k_nearest_neighbors</h1><BR><BR>
This function is a simple approximate form of <a href="#find_k_nearest_neighbors">find_k_nearest_neighbors</a>.
Instead of checking all possible edges it randomly samples a large number of them and then performs
exact k-nearest-neighbors on that randomly selected subset.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#find_approximate_k_nearest_neighbors">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="find_connected_nodes"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">find_connected_nodes</h1><BR><BR>
This function takes a node from a <a href="containers.html#graph">graph</a>
or <a href="containers.html#directed_graph">directed_graph</a> object and a
<a href="containers.html#set">set</a> of unsigned longs. It finds all the
nodes in the given graph that are connected to the given node by an
undirected path and returns them in the set (also note that the
original query node is also returned in this set).
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#find_connected_nodes">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="find_k_nearest_neighbors"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">find_k_nearest_neighbors</h1><BR><BR>
This is a function which finds all the k nearest neighbors of a set of points and outputs
the result as a vector of <a href="#sample_pair">sample_pair</a> objects. It takes O(n^2) time where
n is the number of data samples. A faster approximate version is provided by
<a href="#find_approximate_k_nearest_neighbors">find_approximate_k_nearest_neighbors</a>
and <a href="#find_k_nearest_neighbors_lsh">find_k_nearest_neighbors_lsh</a>.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#find_k_nearest_neighbors">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="find_k_nearest_neighbors_lsh"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">find_k_nearest_neighbors_lsh</h1><BR><BR>
This function is a simple approximate form of <a href="#find_k_nearest_neighbors">find_k_nearest_neighbors</a>.
It uses <a href="algorithms.html#hash_similar_angles_128">locality sensitive hashing</a>
to speed up the nearest neighbor computation and is also capable of using a multi-core CPU.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/find_k_nearest_neighbors_lsh_abstract.h.html#find_k_nearest_neighbors_lsh">More Details...</a><div class="include_file">#include <dlib/graph_utils_threaded.h></div></div></div><a name="find_neighbor_ranges"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">find_neighbor_ranges</h1><BR><BR>
This function takes a graph, defined by a vector of
<a href="#ordered_sample_pair">ordered_sample_pair</a> objects, and finds the
ranges that contain the edges for each node in the graph. The output therefore
lets you easily locate the neighbors of any node in the graph.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#find_neighbor_ranges">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="find_percent_shortest_edges_randomly"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">find_percent_shortest_edges_randomly</h1><BR><BR>
This function is a simple approximate form of <a href="#find_k_nearest_neighbors">find_k_nearest_neighbors</a>.
Instead of checking all possible edges it randomly samples a large number of them and
then returns the best ones.
<BR><BR>C++ Example Programs: <a href="linear_manifold_regularizer_ex.cpp.html">linear_manifold_regularizer_ex.cpp</a><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#find_percent_shortest_edges_randomly">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="graph_contains_directed_cycle"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">graph_contains_directed_cycle</h1><BR><BR>
This function checks a <a href="containers.html#directed_graph">directed_graph</a> for directed cycles.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#graph_contains_directed_cycle">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="graph_contains_length_one_cycle"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">graph_contains_length_one_cycle</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a>
or <a href="containers.html#directed_graph">directed_graph</a> object and
returns true if and only if the graph contains a node that has an edge that
links back to itself.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#graph_contains_length_one_cycle">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="graph_contains_undirected_cycle"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">graph_contains_undirected_cycle</h1><BR><BR>
This function checks a <a href="containers.html#directed_graph">directed_graph</a> for undirected cycles.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#graph_contains_undirected_cycle">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="graph_has_symmetric_edges"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">graph_has_symmetric_edges</h1><BR><BR>
This function checks if a <a href="containers.html#directed_graph">directed_graph</a>
has a pair of nodes with just one edge between them. If so then it
does not have symmetric edges.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#graph_has_symmetric_edges">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="graph_is_connected"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">graph_is_connected</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> or
<a href="containers.html#directed_graph">directed_graph</a> object and
determines if the graph is connected. That is, it returns true if and only if
there is an undirected path between any two nodes in the given graph.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#graph_is_connected">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="is_clique"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">is_clique</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> and a
<a href="containers.html#set">set</a> of node index values and checks
if the specified set of nodes is a clique in the graph.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#is_clique">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="is_join_tree"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">is_join_tree</h1><BR><BR>
This function takes two <a href="containers.html#graph">graph</a> objects and
checks if the second of the two graphs is a valid join tree (aka tree decomposition)
of the first graph.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#is_join_tree">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="is_maximal_clique"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">is_maximal_clique</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> and a
<a href="containers.html#set">set</a> of node index values and checks
if the specified set of nodes is a maximal clique in the graph.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#is_maximal_clique">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="is_ordered_by_index"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">is_ordered_by_index</h1><BR><BR>
This function checks if a vector of <a href="#sample_pair">sample_pair</a> or
<a href="#ordered_sample_pair">ordered_sample_pair</a> objects is in sorted
order according to their index values.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#is_ordered_by_index">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="max_index_plus_one"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">max_index_plus_one</h1><BR><BR>
This function finds the number that is one greater than the largest index
value in a std::vector of <a href="#sample_pair">sample_pair</a> or
<a href="#ordered_sample_pair">ordered_sample_pair</a> objects. Therefore,
it is useful for finding out how many nodes are in an edge list graph (assuming
the graph contains all node indices from 0 to the largest index indicated
by an edge).
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#max_index_plus_one">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="negative_dot_product_distance"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">negative_dot_product_distance</h1><BR><BR>
This is a simple function object that computes -dot(v1,v2) for two
vectors v1 and v2.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/function_objects_abstract.h.html#negative_dot_product_distance">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="ordered_sample_pair"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">ordered_sample_pair</h1><BR><BR>
This object is intended to represent an edge in a directed graph
which has data samples at its vertices. Therefore, it is the directed version
of <a href="#sample_pair">sample_pair</a>.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/ordered_sample_pair_abstract.h.html#ordered_sample_pair">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="order_by_descending_distance"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">order_by_descending_distance</h1><BR><BR>
This function provides a total ordering of <a href="#sample_pair">sample_pair</a>
or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects that causes
pairs with largest distance to be the first in a sorted list. This function
can be used with std::sort().
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/sample_pair_abstract.h.html#order_by_descending_distance">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="order_by_distance"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">order_by_distance</h1><BR><BR>
This function provides a total ordering of <a href="#sample_pair">sample_pair</a>
or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects that causes
pairs with smallest distance to be the first in a sorted list. This function
can be used with std::sort().
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/sample_pair_abstract.h.html#order_by_distance">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="order_by_distance_and_index"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">order_by_distance_and_index</h1><BR><BR>
This function provides a total ordering of <a href="#sample_pair">sample_pair</a> or
<a href="#ordered_sample_pair">ordered_sample_pair</a> objects that causes pairs
with smallest distance to be the first in a sorted list but also orders
samples with equal distances according to order_by_index(). This function
can be used with std::sort().
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/sample_pair_abstract.h.html#order_by_distance_and_index">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="order_by_index"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">order_by_index</h1><BR><BR>
This function provides a total ordering of <a href="#sample_pair">sample_pair</a>
or <a href="#ordered_sample_pair">ordered_sample_pair</a>
objects that will cause pairs that represent the same edge to be adjacent
when sorted. So for example, this function can be used
with std::sort() to first sort a sequence of sample_pair objects and then
find duplicate edges.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/sample_pair_abstract.h.html#order_by_index">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="remove_duplicate_edges"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">remove_duplicate_edges</h1><BR><BR>
This is a simple function for removing duplicate edges (i.e. edges that compare equal
according to ==) from
a vector of <a href="#sample_pair">sample_pair</a> or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#remove_duplicate_edges">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="remove_long_edges"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">remove_long_edges</h1><BR><BR>
This is a simple function for removing edges with a large distance value from
a vector of <a href="#sample_pair">sample_pair</a> or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#remove_long_edges">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="remove_percent_longest_edges"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">remove_percent_longest_edges</h1><BR><BR>
This is a simple function for removing edges with a large distance value from
a vector of <a href="#sample_pair">sample_pair</a> or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#remove_percent_longest_edges">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="remove_percent_shortest_edges"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">remove_percent_shortest_edges</h1><BR><BR>
This is a simple function for removing edges with a small distance value from
a vector of <a href="#sample_pair">sample_pair</a> or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#remove_percent_shortest_edges">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="remove_short_edges"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">remove_short_edges</h1><BR><BR>
This is a simple function for removing edges with a small distance value from
a vector of <a href="#sample_pair">sample_pair</a> or <a href="#ordered_sample_pair">ordered_sample_pair</a> objects.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/edge_list_graphs_abstract.h.html#remove_short_edges">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="sample_pair"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">sample_pair</h1><BR><BR>
This object is intended to represent an edge in an undirected graph
which has data samples at its vertices. Therefore, it is the undirected version
of <a href="#ordered_sample_pair">ordered_sample_pair</a>.
<BR><BR>C++ Example Programs: <a href="linear_manifold_regularizer_ex.cpp.html">linear_manifold_regularizer_ex.cpp</a><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/sample_pair_abstract.h.html#sample_pair">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="squared_euclidean_distance"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">squared_euclidean_distance</h1><BR><BR>
This is a simple function object that computes squared euclidean distance
between two <a href="linear_algebra.html#matrix">matrix</a> objects.
<BR><BR>C++ Example Programs: <a href="linear_manifold_regularizer_ex.cpp.html">linear_manifold_regularizer_ex.cpp</a><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/function_objects_abstract.h.html#squared_euclidean_distance">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="triangulate_graph_and_find_cliques"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">triangulate_graph_and_find_cliques</h1><BR><BR>
This function takes a <a href="containers.html#graph">graph</a> and
turns it into a chordal graph. It also returns a
<a href="containers.html#set">set</a> that contains
all the cliques present in the chordal graph.
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/graph_utils_abstract.h.html#triangulate_graph_and_find_cliques">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="use_gaussian_weights"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">use_gaussian_weights</h1><BR><BR>
This is a simple function object that takes a single argument
which should be an object similar to <a href="#sample_pair">sample_pair</a>.
<BR><BR>C++ Example Programs: <a href="linear_manifold_regularizer_ex.cpp.html">linear_manifold_regularizer_ex.cpp</a><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/function_objects_abstract.h.html#use_gaussian_weights">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div><a name="use_weights_of_one"></a><div class="component"><a href="#top"><font size="2"><center>[top]</center></font></a><h1 style="margin:0px;">use_weights_of_one</h1><BR><BR>
This is a simple function object that takes a single argument
and always returns 1
<BR><div class="include_file_more_details_wrapper"><a class="more_details" href="dlib/graph_utils/function_objects_abstract.h.html#use_weights_of_one">More Details...</a><div class="include_file">#include <dlib/graph_utils.h></div></div></div></div></body></html>