# 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.

### 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();
      vtkIdType v0 = graph->AddVertex();
      vtkIdType v1 = graph->AddVertex();
      vtkIdType v2 = graph->AddVertex();
      vtkIdType v3 = graph->AddVertex();

      graph->AddEdge ( v0, v1 );
      graph->AddEdge ( v0, v2 );
      graph->AddEdge ( v0, v3 );
      graph->AddEdge ( v1, v2 );
      graph->AddEdge ( v2, v3 );

      // 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();
      renderWindow->AddRenderer(renderer);
      vtkSmartPointer<vtkRenderWindowInteractor> renderWindowInteractor =
        vtkSmartPointer<vtkRenderWindowInteractor>::New();
      renderWindowInteractor->SetRenderWindow(renderWindow);

      // Add the actor to the scene
      renderer->AddActor(actor);
      renderer->AddActor(pathActor);
      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
      vtkFiltersSources
      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
      add_executable(ShortestPath MACOSX_BUNDLE ShortestPath.cxx )
      target_link_libraries(ShortestPath PRIVATE ${VTK_LIBRARIES})
      # vtk_module_autoinit is needed
      vtk_module_autoinit(
        TARGETS ShortestPath
        MODULES ${VTK_LIBRARIES}
        )
    endif ()

### Download and Build ShortestPath

Click here to download ShortestPath and its CMakeLists.txt file. Once the tarball ShortestPath.tar has been downloaded and extracted,

    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.