Giter VIP home page Giter VIP logo

graph-search-tool's Introduction

nb17-xzeng17-xiaojun7-yuesong3

Presentation Video

https://youtu.be/lkfoLybeqss

Obtained data source from:

  1. GitHub Social Network http://snap.stanford.edu/data/github-social.html
  2. California Road Network http://snap.stanford.edu/data/roadNet-CA.html
  3. Gnutella peer to peer network from August 8 2002 http://snap.stanford.edu/data/p2p-Gnutella08.html

File Directory:

project
|
|__assets: contains data
|__cs225: makefile and catch
|__fileloaders: class used to read data and create graph
|__graphs: graph classes
|__structs: utility structs, (traversal algorithms and UI)
|__tests: test suites
|__traversals: contains all our algorithms implementation
|
main.cpp

Compile Program:

  1. To compile file: $ make
  2. To compile test case: $ make test
  3. To run the main.cpp: $ ./main
  4. To run all test case: $ ./test

User Guide:

Start and Load Graph

  1. start the program with $ ./main
  2. You entered the main menu from step 1. Navigation system will be very similar to a mobile service robot.
  3. Input 1 for loading/replacing data. This allows you to load a graph from assets folder.
    You only need to type the file name with extension.
    You have to select whether the graph is a directed graph or undirected graph. The data set we selected have simple representation, and you can build them into either directed or undirected graph.
    The third option is to decide how much data you want to load. For example, The roadNet-CA.txt is very very large, and I recommend only load 0.005!
    After that, when you are back to the main menu, you will see that your data has been loaded with additional informations.
  4. After you have loaded the data, you can input 2 for running some algorithms.

Run Algorithms

When you entered "Run graph search algorithms", you will again see a list of available actions.
0: DFS
1: BFS
2: IDDFS
3: Dijkstra
4: SCC (only available when directed graph is loaded)

Help

Input 8 to reveal the actions you can do.

Exit

Input 9 to exit program.

Command oneline

If you decide to not to use our user-interaction console, you can run algothem on graph in the following format. $ ./main [data filename] [graph type] [graph load factor] [Algorithm] [parameter 1] [parameter 2] [parameter 3]

  • DFS parameter 1: source vertex (string number), parameter 2: destination vertex (string number)
  • BFS parameter 1: source vertex (string number), parameter 2: destination vertex (string number)
  • IDDFS parameter 1: source vertex (string number), parameter 2: destination vertex (string number), parameter 3: maximum depth (positive int)
  • Dijkstra parameter 1: source vertex (string number), parameter 2: destination vertex (string number)
  • SCC parameter 1: number of SSC to display, parameter 2: Threshold number for SSC
  • Plug in -1 for string number to get a random node

    Examples:
    $ ./main musae_git_edges.csv undirected 1.0 DFS -1 -1
    $ ./main musae_git_edges.csv undirected 1.0 BFS -1 -1
    $ ./main musae_git_edges.csv undirected 1.0 IDDFS -1 -1 100
    $ ./main musae_git_edges.csv undirected 1.0 Dijkstra -1 -1
    $ ./main roadNet-CA.txt directed 0.005 SCC 3 5
    $ ./main p2p-Gnutella08.txt directed 1 SCC 3 1

    Tips:

    1. roadNet-CA.txt is 80 mb and it is almost impossible to load the entire graph, therefore we suggest only load 0.005 portion. We tested at 0.01, it worked locally but not on ews.
    2. Original data musae_git_edges.csv and roadNet-CA.txt are undirected graph, and p2p-Gnutella08.txt is directed grpah. However, you can still load datas as either directed/undirected graph.
    3. For test purpose, we recommend load data as undirected graph to test DFS, BFS, IDDFS and Dijkstra if you want to select random node otherwise expect to see many no path exist result.

    Test suites:

    We adapted the cs225's test suites and wrote personalized data sets to specifically test the edge cases that we might encounter in real data. The tests mainly focus on the accuracy of our algorithms.

  • graph-search-tool's People

    Contributors

    nursultanbs avatar

    Watchers

     avatar

    Forkers

    jinjintwice

    Recommend Projects

    • React photo React

      A declarative, efficient, and flexible JavaScript library for building user interfaces.

    • Vue.js photo Vue.js

      ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

    • Typescript photo Typescript

      TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

    • TensorFlow photo TensorFlow

      An Open Source Machine Learning Framework for Everyone

    • Django photo Django

      The Web framework for perfectionists with deadlines.

    • D3 photo D3

      Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

    Recommend Topics

    • javascript

      JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

    • web

      Some thing interesting about web. New door for the world.

    • server

      A server is a program made to process requests and deliver data to clients.

    • Machine learning

      Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

    • Game

      Some thing interesting about game, make everyone happy.

    Recommend Org

    • Facebook photo Facebook

      We are working to build community through open source technology. NB: members must have two-factor auth.

    • Microsoft photo Microsoft

      Open source projects and samples from Microsoft.

    • Google photo Google

      Google โค๏ธ Open Source for everyone.

    • D3 photo D3

      Data-Driven Documents codes.