项目作者: rafaelglikis

项目描述 :
There is given an undirected graph G = (V, E) from which edges are deleted one at a time. Questions like "Are the vertices u and v in the same connected component?" have to be answered in constant time.
高级语言: C++
项目地址: git://github.com/rafaelglikis/dynamic-connectivity.git
创建时间: 2018-07-13T23:58:54Z
项目社区:https://github.com/rafaelglikis/dynamic-connectivity

开源协议:MIT License

下载


An On-Line Edge-Deletion Problem POC

Abstract

There is given an undirected graph G = (V, E) from which edges are deleted one at a time. Questions like “Are the vertices u and v in the same connected component?” have to be answered “on-line”.

This is an implementation of a decremental dynamic algorithm [ES81] which maintains a data structure in which each question is answered in constant time and for which the total time involved in answering q questions and maintaining the data structure is O(q+|V||E|), and O(q+|E|log(|E|)) for acyclic graphs.

Requirements

  • boost graph library
  • openmp
  • cmake

How to use it

  • Create graph and initialize it
  • Make deletions
  • Make queries
  • Repeat

Example

  1. #include <iostream>
  2. #include "../incl/graph_types/DynamicGraph.h"
  3. int main()
  4. {
  5. // Create graph the bgl way
  6. DynamicGraph G;
  7. add_edge(0, 1, G);
  8. add_edge(0, 2, G);
  9. add_edge(2, 3, G);
  10. add_edge(4, 5, G);
  11. add_edge(4, 6, G);
  12. add_edge(6, 5, G);
  13. add_edge(7, 8, G);
  14. // Initialize dynamic Graph
  15. G.init();
  16. // Delete edge
  17. G.deleteEdge(7, 8);
  18. if(G.areConnected(7, 8)) {
  19. std::cout << "Vertices 7 and 8 are connected!" << std::endl;
  20. }
  21. else {
  22. std::cout << "Vertices 7 and 8 not are connected!" << std::endl;
  23. }
  24. }

Compile

  1. mkdir cmake-build
  2. cd cmake-build
  3. cmake ..
  4. cd ..
  5. cmake --build cmake-build

Usage

Usage:

  1. dynamic_connectivity ACTION* [OPTION]*

Example:

  1. dynamic_connectivity benchmark --random -v 500 -e 1000 -d 50 -q 50

Test:

  1. --test run all tests

Benchmarks:

  1. --benchmark run benchmark specified benchmarks
  2. --path run benchmark with path graph
  3. --tree run benchmark with tree graph
  4. --random run benchmark with random graph
  5. --path-complete run benchmark with path of complete subgraphs

Benchmark options:

  1. -v [ --vertices ] arg (=100) specify number of vertices
  2. -e [ --edges ] arg (=460) specify number of edges (only for random graphs)
  3. -d [ --deletions ] arg (=50) specify number of vertices
  4. -q [ --queries ] arg (=50) specify number of vertices

Examples:

  1. --example run an example at src/example.cpp

Help:

  1. --help produce help message

Visualization:

  1. dynamic_connectivity --example
  2. ./visualize-example.sh

References

  • [ES81] S. Even and Y. Shiloach, “An On-Line Edge-Deletion Problem”, Journal of the ACM, 28(1):1-4, 1981