Giter VIP home page Giter VIP logo

libgraph's Introduction

Graph and Search

GitHub Workflow Status codecov

C++ class templates for constructing graphs and search. This library is distributed under MIT license.

1. Design

Assuming a graph G = (V, E) contains n vertices and m edges:

Data Structure

A "Graph" class contains a collection of "Vertex" objects (stored in vertex_map_ of type VertexMapType) and each "Vertex" contains a list of edges (stored in edges_to_ of type EdgeListType) connecting to its adjacent vertices.

Type STL Data Structure Internal
VertexMapType std::unordered_map<int64_t, Vertex *> hash table
EdgeListType std::list<Edge> linked list

The overall space complexity of this graph implementation is O(m+n).

Time Complexity

Operation Time Complexity
Find Vertex Average O(1), Worst O(n)
Add Vertex Average O(1), Worst O(n)
Remove Vertex Average O(1), Worst O(n)*
Find Edge Worst O(m*)
Add Edge Worst O(1)
Remove Edge Worst O(m^2)
  • here O(1), O(n) only accounts for the operation to remove the vertex from the vertex map. Additionally it may take up to O(m^2) to remove all edges connected to the vertex both from upstream and downstream. Possible improvement can be made to reduce the O(m^2) complexity by using a different data structure for vertics_from and edges_to lists.
  • for a sparse graph, the number of edges that a vertex contains should be much less than m

Graph Search

The dynamic priority queue is implemented as a binary heap, thus the time complexity of a graph search is O((m+n)*log(n)).

2. Dependencies

  • A compiler that supports C++11

This is a header-only library. There are multiple ways you can integrate this library to your project:

  1. Simply copy content of the "src" folder to your project and include "graph/graph.hpp".
  2. If you're using CMake, you could integrate the library to your project by adding this repository as a git submodule. Then use "add_subdirectory()" in your CMakeLists.txt to add the library to your build tree.
  3. You can build and install this library to your system path and use CMake "find_package(graph REQUIRED)" to find the library and add dependency by using "target_link_libraries(your_app PRIVATE rdu::graph)".

3. Build the demo & pack the library

A ".deb" installation package can be generated if you want to install the library to your system. Relevant CMake configuration files will also be installed so that you can easily use "find_package()" command to find and use the library in your project. Note that the library is exported as "rdu::graph" to avoid naming conflicts with other libraries.

$ git clone --recursive https://github.com/rxdu/libgraph.git
$ mkdir build && cd build
$ cmake --build .
$ cpack

Demo programs will be built and put into "build/bin" folder. A ".deb" package would be generated inside "build" folder. Install the library with the ".deb" package using command "dpkg", for example

$ sudo dpkg -i libgraph_1.1_amd64.deb

4. Build document

You need to have doxygen to build the document.

$ sudo apt-get install doxygen
$ cd docs
$ doxygen doxygen/Doxyfile

Outlines of core data structures for the purpose of API reference are given at https://rdu.im/libgraph/ .

5. Construct a graph

You can associate any object to a vertex, but you need to provide an index function for the State struct/class. The index function is used to generate a unique index for a state and it's necessary for checking whether two given states are the same so that only one vertex is created for one unique state inside the graph.

A default indexer is provided and could be used if you have a member function "GetId()" or a member variable "id_" or "id" that provide you with a unique value of the object.

You can also define your own index function if the default one is not suitable for your application.

// struct YourStateIndexFunction is a functor that defines operator "()". 
struct YourStateIndexFunction
{
    // you should have this one if "State" type 
    // of your Graph is a raw pointer type
    int64_t operator()(YourStateType* state)
    {
        // Generate <unique-value> with state
        return <unique-value>;
    }

    // you should have this one if "State" type 
    // of your Graph is a value type
    int64_t operator()(const YourStateType& state)
    {
        // Generate <unique-value> with state
        return <unique-value>;
    }
};

See "simple_graph_demo.cpp" in "demo" folder for a working example.

6. Known limitations

libgraph's People

Contributors

rxdu avatar

Stargazers

Karthee avatar void0red avatar  avatar Markell avatar Raymond Daley avatar Dingjiang Zhou avatar Mohammed Tousif Zaman avatar  avatar  avatar Librada Osinski avatar  avatar

Watchers

James Cloos avatar  avatar  avatar

libgraph's Issues

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.