# ShortestPath

VTKExamples/Cxx/Graphs/ShortestPath

### Description¶

Currently, the only way to find the shortest path on a graph is to convert the graph to a mesh (using vtkGraphToPolyData) and then use the shortest path on a mesh functionality of vtkDijkstraGraphGeodesicPath.

Question

### Code¶

ShortestPath.cxx

#include <vtkSmartPointer.h>
#include <vtkTree.h>
#include <vtkMutableDirectedGraph.h>
#include <vtkGraphLayoutView.h>
#include <vtkRenderWindowInteractor.h>
#include <vtkGraphToPolyData.h>
#include <vtkProperty.h>
#include <vtkPolyData.h>
#include <vtkSmartPointer.h>
#include <vtkPolyDataMapper.h>
#include <vtkActor.h>
#include <vtkRenderWindow.h>
#include <vtkRenderer.h>
#include <vtkRenderWindowInteractor.h>
#include <vtkDijkstraGraphGeodesicPath.h>

/*
O v0
/|\
5/ |5\5
v1-v2-v3
1  1

Shortest path between v0 and v2 should be 5
*/

int main ( int argc, char *argv[] )
{
vtkSmartPointer<vtkMutableDirectedGraph> graph =
vtkSmartPointer<vtkMutableDirectedGraph>::New();

// Associate physical locations with the vertices
vtkSmartPointer<vtkPoints> points =
vtkSmartPointer<vtkPoints>::New();
points->InsertNextPoint(0.0, 0.0, 0.0);
points->InsertNextPoint(-1.0, -5.0, 0.0);
points->InsertNextPoint(0.0, -5.0, 0.0);
points->InsertNextPoint(1.0, -5.0, 0.0);

graph->SetPoints(points);

// Convert the graph to a polydata
vtkSmartPointer<vtkGraphToPolyData> graphToPolyData =
vtkSmartPointer<vtkGraphToPolyData>::New();
graphToPolyData->SetInput(graph);
graphToPolyData->Update();

vtkSmartPointer<vtkDijkstraGraphGeodesicPath> dijkstra =
vtkSmartPointer<vtkDijkstraGraphGeodesicPath>::New();
dijkstra->SetInputConnection(graphToPolyData->GetOutputPort());
dijkstra->SetStartVertex(0);
dijkstra->SetEndVertex(2);
dijkstra->Update();

// Create a mapper and actor
vtkSmartPointer<vtkPolyDataMapper> pathMapper =
vtkSmartPointer<vtkPolyDataMapper>::New();
pathMapper->SetInputConnection(dijkstra->GetOutputPort());

vtkSmartPointer<vtkActor> pathActor =
vtkSmartPointer<vtkActor>::New();
pathActor->SetMapper(pathMapper);
pathActor->GetProperty()->SetColor(1,0,0); // Red
pathActor->GetProperty()->SetLineWidth(4);

// Create a mapper and actor
vtkSmartPointer<vtkPolyDataMapper> mapper =
vtkSmartPointer<vtkPolyDataMapper>::New();
mapper->SetInputConnection(graphToPolyData->GetOutputPort());

vtkSmartPointer<vtkActor> actor =
vtkSmartPointer<vtkActor>::New();
actor->SetMapper(mapper);

// Create a renderer, render window, and interactor
vtkSmartPointer<vtkRenderer> renderer =
vtkSmartPointer<vtkRenderer>::New();
vtkSmartPointer<vtkRenderWindow> renderWindow =
vtkSmartPointer<vtkRenderWindow>::New();
vtkSmartPointer<vtkRenderWindowInteractor> renderWindowInteractor =
vtkSmartPointer<vtkRenderWindowInteractor>::New();
renderWindowInteractor->SetRenderWindow(renderWindow);

// Add the actor to the scene
renderer->SetBackground(.3, .6, .3); // Background color green

// Render and interact
renderWindow->Render();
renderWindowInteractor->Start();

return EXIT_SUCCESS;
}


### CMakeLists.txt¶

cmake_minimum_required(VERSION 3.3 FATAL_ERROR)

project(ShortestPath)

find_package(VTK COMPONENTS
vtkCommonCore
vtkCommonDataModel
vtkFiltersModeling
vtkInteractionStyle
vtkRenderingCore
vtkRenderingFreeType
vtkRenderingOpenGL2
vtkViewsInfovis QUIET)
if (NOT VTK_FOUND)
message("Skipping ShortestPath: ${VTK_NOT_FOUND_MESSAGE}") return () endif() message (STATUS "VTK_VERSION:${VTK_VERSION}")
if (VTK_VERSION VERSION_LESS "8.90.0")
# old system
include(${VTK_USE_FILE}) add_executable(ShortestPath MACOSX_BUNDLE ShortestPath.cxx ) target_link_libraries(ShortestPath PRIVATE${VTK_LIBRARIES})
else ()
# include all components
target_link_libraries(ShortestPath PRIVATE ${VTK_LIBRARIES}) # vtk_module_autoinit is needed vtk_module_autoinit( TARGETS ShortestPath MODULES${VTK_LIBRARIES}
)
endif ()


cd ShortestPath/build


If VTK is installed:

cmake ..


If VTK is not installed but compiled on your system, you will need to specify the path to your VTK build:

cmake -DVTK_DIR:PATH=/home/me/vtk_build ..


Build the project:

make


and run it:

./ShortestPath


WINDOWS USERS

Be sure to add the VTK bin directory to your path. This will resolve the VTK dll's at run time.