codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
199 stars 269 forks source link

Adding support for graph.AdjacencyMatrix in C++ backend #513

Open nubol23 opened 1 year ago

nubol23 commented 1 year ago

Add graph cpp backend.

Currently working on AdjacencyMatrix implementation.

czgdp1807 commented 1 year ago

So, while adding support any data structure in C++ backend we need to make sure that there is no difference between the interface supported by C++ backend and Python backend. Internally both can follow different implementations.

Since we have already implemented Graph in Python backend so we need to make sure that interface of every method defined in https://github.com/codezonediitj/pydatastructs/blob/master/pydatastructs/graphs/graph.py works with C++ backend as well. The pattern I notice is here that we pass nodes as input, call str upon these nodes and use the output to index the graph data structure.

So I would say let's follow a similar pattern for now in C++ backend as well, with a small tweak i.e., I would use name attribute instead of calling str on the input nodes which will return the name for these nodes. Then use these names to index the data structure.

Now, AdjacencyMatrixCpp can contain the following containers to store information related to nodes and edges,

  1. std::map<std::pair<std::string, std::string>, bool> - Similarly to https://github.com/codezonediitj/pydatastructs/blob/8f419fd11ad73e9a60666d7834797cce321bb975/pydatastructs/graphs/adjacency_matrix.py#L26-L28.
  2. std::map<std::pair<std::string, std::string>, GraphEdgeCpp> - Similar to https://github.com/codezonediitj/pydatastructs/blob/8f419fd11ad73e9a60666d7834797cce321bb975/pydatastructs/graphs/adjacency_matrix.py#L29

And in addition to AdjancencyMatrixCpp we will need following data structures in C++ backend,

  1. GraphNodeCpp - Similar to https://github.com/codezonediitj/pydatastructs/blob/8f419fd11ad73e9a60666d7834797cce321bb975/pydatastructs/utils/misc_util.py#L364-L369.
  2. AdjancencyMatrixGraphNodeCpp - Similar to https://github.com/codezonediitj/pydatastructs/blob/8f419fd11ad73e9a60666d7834797cce321bb975/pydatastructs/utils/misc_util.py#L434
  3. GraphEdgeCpp - Similar to https://github.com/codezonediitj/pydatastructs/blob/8f419fd11ad73e9a60666d7834797cce321bb975/pydatastructs/utils/misc_util.py#L467
codecov[bot] commented 1 year ago

Codecov Report

Merging #513 (eed61cb) into master (8f419fd) will increase coverage by 0.009%. The diff coverage is 100.000%.

@@              Coverage Diff              @@
##            master      #513       +/-   ##
=============================================
+ Coverage   98.528%   98.538%   +0.009%     
=============================================
  Files           32        34        +2     
  Lines         4010      4037       +27     
=============================================
+ Hits          3951      3978       +27     
  Misses          59        59               
Impacted Files Coverage Δ
pydatastructs/graphs/__init__.py 100.000% <100.000%> (ø)
pydatastructs/graphs/_extensions.py 100.000% <100.000%> (ø)
pydatastructs/utils/__init__.py 100.000% <100.000%> (ø)
pydatastructs/utils/_extensions.py 100.000% <100.000%> (ø)
pydatastructs/utils/misc_util.py 99.148% <100.000%> (+0.018%) :arrow_up:

Impacted file tree graph