Skip to content

Latest commit

 

History

History
29 lines (21 loc) · 1.92 KB

README.md

File metadata and controls

29 lines (21 loc) · 1.92 KB
Raw

Paralelizacija grafovskih algoritmov v funkcijskih programskih jezikih

V okviru diplomske naloge bom raziskoval paralelizacijo grafovskih algoritmov v funkcijskih programskih jezikih.

Nastavitev okolja

  • Inštalacija OCaml-a ter opam-a: Sledite inštalacijskim navodilom na https://ocaml.org/docs/up-and-running#installation-on-unix. Treba je:
    • opam instalirati
    • opam inicializirati
    • Ustvariti switch, ki je verzije >= 5.0.0
  • opam install dune
  • cd ./playground/graph
  • dune build. Primeri raznih dune datotek so zapisani na ./playground/graph/dune_file_contents.ml. V glavnem priporočam poganjanje datotek *_examples.ml, kjer je * ime algoritma, ki ga želite pognati (npr. bfs, dijkstra, ...).
  • Ta binary poženete z ./*_examples.exe iz direktorija ./playground/graph/.

Struktura projekta

V folderju /diploma so shranjeni pisni izdelki diplomske naloge (najpomembnejši izmed njih je verjetno diplomska naloga sama). Mapa /diploma uporablja rezultate iz mape /playground/graph/.

Struktura kode (znotraj folderja /playground):

  • Graph: Znotraj folderja Graph je shranjena grafovska predstavitev ter njihovi algoritmi
    • graph.ml: Predstavitev uteženega in neuteženega grafa. Graf je implementiran preko modulov Node, UnweightedGraph ter WeightedGraph.
    • fib.ml: Implemetacija naivnega paralelnega računanja Fibonaccijevih števil.
    • bfs.ml: Implementacija paralelnega in sekvenčnega algoritma BFS.
    • dijkstra.ml: Implementacija paralelnega in sekvenčnega algoritma Dijkstre.
    • floyd.ml: Implementacija paralelnega ter sekvenčnega Floyd-Warshallovega algoritma
    • computation_time_analysis/computation_time_analysis.ipynb: Primerjava časov izvajanja paralelnih in sekvenčnih algoritmov.