4
\$\begingroup\$

I am building a generic Graph. I want to know whether the current design is fine. Are there any memory leaks ? Any suggestions are deeply appreciated.

GraphCode

#include <iostream>
#include <memory>
#include <vector>
#include <atomic>
#include <map>

namespace AtomicOps
{
int GetID()
{
  static std::atomic<int> id(0);
  return id++;
}

} // namespace AtomicOps

template <typename T>
class Graph;

template <typename T>
class GraphFactory
{

public:
  GraphFactory()
  {
  }

  ~GraphFactory()
  {
    mGraphDataMap.clear();
    mCurrentPath.clear();
    mTotalPath.clear();
  }

  //ID is provided by GETID fuction
  Graph<T> &GetObject(T &data, int id = -1, bool addToPath = false)
  {
    return *GetObjectPTR(data, id, addToPath);
  }

  Graph<T> &GetObject(T &&data, int id = -1, bool addToPath = false)
  {
    //no need to move as we are creating copy of it

    return *GetObjectPTR(data, id, addToPath);
  }

  //*************************************

  //graph like (src node ---W--- dst-node)

  void BuildGraph(T &&src, int weight, T &&dest, int srcID = -1, int dstID = -1, bool srcAddToPath = false, bool dstAddToPath = false)
  {
    BuildGraphHelper(src, weight, dest, srcID, dstID, srcAddToPath, dstAddToPath);
  }

  void BuildGraph(T &src, int weight, T &dest, int srcID = -1, int dstID = -1, bool srcAddToPath = false, bool dstAddToPath = false)
  {
    BuildGraphHelper(src, weight, dest, srcID, dstID, srcAddToPath, dstAddToPath);
  }

  std::vector<std::shared_ptr<Graph<T>>> GetAllNodes()
  {
    return mTotalPath;
  }

  std::vector<std::shared_ptr<Graph<T>>> GetCurrentPath()
  {
    return mCurrentPath;
  }

  void ClearCurrentPath()
  {
    mCurrentPath.clear();
  }

  void AddToCurrentPath(Graph<T> &obj, int id = -1)
  {
    auto pathPTR = GetObjectPTR(obj.mData, id);
    mCurrentPath.push_back(pathPTR);
  }

private:
  std::shared_ptr<Graph<T>> &GetObjectPTR(T &data, int id, bool addToPath)
  {
    auto pair = std::make_pair<T &, int &>(data, id);
    if (mGraphDataMap.find(pair) == mGraphDataMap.end())
    {

      mGraphDataMap[pair] = std::make_shared<Graph<T>>(Graph<T>(std::forward<T>(data)));
      mGraphDataMap[pair]->mID = id;
      mTotalPath.push_back(mGraphDataMap[pair]);
      if (addToPath)
      {
        mCurrentPath.push_back(mGraphDataMap[pair]);
      }
    }

    return (mGraphDataMap[pair]);
  }

  void BuildGraphHelper(T &src, int weight, T &dest, int srcID = -1, int dstID = -1, bool srcAddToPath = false, bool dstAddToPath = false)
  {
    auto &srcNode = (GetObject(src, srcID, srcAddToPath));
    auto &dstNode = (GetObject(dest, dstID, dstAddToPath));
    srcNode.AddEdge(dstNode, weight);
  }
  std::map<std::pair<T, int>, std::shared_ptr<Graph<T>>> mGraphDataMap;
  std::vector<std::shared_ptr<Graph<T>>> mCurrentPath;
  std::vector<std::shared_ptr<Graph<T>>> mTotalPath;
};

template <typename T>
class GraphAlgo
{

  typedef std::shared_ptr<Graph<T>> GraphPTR;

public:
  GraphAlgo(std::vector<GraphPTR> &path) : mPath(path)
  {
  }

  void Clear()
  {
    for (auto& item : mPath)
    {
      item->ClearMeta();
    }
  }

  const GraphPTR findMin()
  {

    int dist = INT32_MAX;
    GraphPTR minNode;
    int index = -1;
    int last_index = 0;
    for (auto &node : mPath)
    {
      if (dist > node->mDist && !node->mVisited)
      {
        dist = node->mDist;
        minNode = node;
      }
    }

    //nodes[last_index].mVisited= true;
    minNode->mVisited = true;
    return minNode;
  }

  //This node consider to be shortest node
  std::vector<Graph<T>>
  DijkstraShortestPath()
  {

    std::vector<GraphPTR> tmp;
    std::vector<Graph<T>> pathToParent;
    if (mPath.empty())
    {
      pathToParent;
    }

    //we should be knowing in advance which nodes are going to participate
    //mPath variable should be static varable
    mPath[0]->mDist = 0;
    // or we can find all pair shortest path
    for (int j = 0; j < mPath.size(); j++)
    {
      auto minNode = findMin();

      int size = minNode->mEdges.size();

      for (int i = 0; i < size; i++)
      {

        if (minNode->mEdges[i].weight < 0)
        {
          return pathToParent;
        }

        if (minNode->mEdges[i].edge->mDist > minNode->mDist + minNode->mEdges[i].weight)
        {

          minNode->mEdges[i].edge->mDist = minNode->mDist + minNode->mEdges[i].weight;
          //std::swap(minNode->mEdges[i].edge->mParent, nullptr);
          minNode->mEdges[i].edge->mParent = minNode;

          // Front
        }
      }
    }

    GraphPTR graph = mPath[mPath.size() - 1];

    while (graph)
    {
      pathToParent.push_back(*graph);
      graph = graph->mParent;
    }

    return pathToParent;
  }

private:
  std::vector<GraphPTR> mPath;
};

template <typename T>
class Graph;

template <typename T>
void no_op(Graph<T> *)
{
}

template <typename T>
class Graph
{
  typedef std::shared_ptr<Graph<T>> GraphPTR;

public:
  T &GetData()
  {
    return mData;
  }

  ~Graph()
  {
    mPath.clear();
  }

  void AddEdge(Graph<T> &edge, int weight = 1)
  {

    // Don't copy we need ref
    // As client function is going
    // to manage memory of obj we shouldn't be
    // deleting obj;
    // TODO : use instead raw pointer here

    GraphPTR ptr(&edge, no_op<T>);
    mEdges.push_back(GraphMeta(ptr, weight));
  }

  void SetPath(std::vector<GraphPTR> &gPtr)
  {
    mPath = gPtr;
  }

  void ClearPath()
  {
    mPath.clear();
  }

  void AddToPath(Graph<T> &edge)
  {
    //TODO : use insted raw pointer here
    GraphPTR ptr(&edge, no_op<T>);
    mPath.push_back(ptr);
  }

  Graph(const Graph<T> &&copy) : mID(copy.mID),
                                 mData(std::move(copy.mData)),
                                 mEdges(std::move(copy.mEdges)),
                                 mDist(std::move(copy.mDist)),
                                 mVisited(copy.mVisited)

  {
    //   mParent(nullptr);
  }

  Graph(const Graph<T> &copy) : mID(copy.mID),
                                mData(copy.mData),
                                mEdges(copy.mEdges),
                                mDist(copy.mDist),
                                mVisited(copy.mVisited)

  {
    //   mParent(nullptr);
  }

  Graph<T> &operator=(const Graph<T> &&copy)
  {
    mID = copy.mID;
    mData = std::move(copy.mData);
    mEdges = std::move(copy.mEdges);
    mDist = std::move(copy.mDist);
    mVisited = copy.mVisited;
    mParent = std::move(mParent);
  }

  Graph<T> &operator=(const Graph<T> &copy)
  {
    mID = copy.mID;
    mData = (copy.mData);
    mEdges = (copy.mEdges);
    mDist = (copy.mDist);
    mVisited = copy.mVisited;
    mParent = (mParent);
  }

private:
  Graph()
  {
  }
  void clearMeta()
  {

    mParent = nullptr;
    mVisited = false;
    mDist = INT32_MAX;
  }

  Graph(T &data, int id = -1) : mData(data)
  {
    mDist = INT32_MAX;
    mVisited = false;
    mID = id;
  }

  Graph(T &&data, int id = -1) : mData(std::move(data))
  {
    mDist = INT32_MAX;
    mVisited = false;
    mID = id;
  }

  struct GraphMeta
  {
    GraphMeta(GraphPTR ptr, int wt) : edge(ptr), weight(wt)
    {
    }

    GraphMeta(const GraphMeta &other) : weight(other.weight),
                                        edge(other.edge)
    {
    }

    GraphMeta &operator=(const GraphMeta &other)
    {
      weight = other.weight;
      edge = other.edge;
    }

    int weight;
    Graph::GraphPTR edge;
  };

private:
  friend class GraphFactory<T>;
  friend class GraphAlgo<T>;
  T mData;
  int mDist;
  GraphPTR mParent;
  bool mVisited;
  std::vector<GraphMeta> mEdges;
  std::vector<GraphPTR> mPath;
  int mID;
};

Client Code

int main()
{
  GraphFactory<int> obj;
  obj.BuildGraph(1, 1, 2);
  obj.BuildGraph(2, 1, 6);
  //6  1 10,  10  1  11
  obj.BuildGraph(6, 3, 10);
  obj.BuildGraph(2, 1, 11);
  obj.BuildGraph(10, 1, 11);

  auto list = obj.GetAllNodes();
  GraphAlgo<int> algoObj(list);

  auto nodes = algoObj.DijkstraShortestPath();


  for(auto item: nodes) {
    std::cout << item.GetData() <<std::endl;
  }



 return 0;
}

Compiler : MINGW(Windows)

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ Commented Oct 10, 2019 at 13:12
  • \$\begingroup\$ Ok sorry i am reverting back \$\endgroup\$ Commented Oct 10, 2019 at 13:13
  • \$\begingroup\$ Why don't you =default your copy/move constructors and assignment operators? Seems redundant. I don't see why you would want the generic type T as a part of your graph. It doesn't seem like an integral part of the graph class, so I'd drop it. At most make a template child of graph that contains the data. \$\endgroup\$ Commented Oct 12, 2019 at 9:14
  • \$\begingroup\$ 1) Yes, you are right I can do it that way but now I have just written this code, so I want it easy to debug. I am getting complete flow of program how object is moving and copying. For example, as this graph any object you have added now and may have edge in future, if you have created copy of that object you will not able to have edge (As graph have reference to copied object not actual object).This kind of issues i was facing so created that. 2) Thanks for suggestion for decoupling data and graph itself. I will refactor that way I don’t see any disadvantage. \$\endgroup\$ Commented Oct 12, 2019 at 14:34

1 Answer 1

Reset to default
4
\$\begingroup\$

This destructor is pointless:

  ~GraphFactory()
  {
    mGraphDataMap.clear();
    mCurrentPath.clear();
    mTotalPath.clear();
  }

Those three members are going out of scope anyway, so clear() is redundant. Just omit the destructor entirely.

Here's a useless statement:

if (mPath.empty())
{
  pathToParent;
}

Was that meant to be a return?

Use consistent types for comparisons. For example, we have:

for (int j = 0; j < mPath.size(); j++)

A vector's size() is a std::size_t, so use the same type for j:

for (std::size_t j = 0;  j < mPath.size();  ++j)

In initializer lists, it helps readers if you write the initializers in the order that they will be executed (which is the order in which the members are declared):

Graph(const Graph<T>&& copy)
    : mData(std::move(copy.mData)),
      mDist(std::move(copy.mDist)),
      mParent(),
      mVisited(copy.mVisited),
      mEdges(std::move(copy.mEdges)),
      mPath(),
      mID(copy.mID)
{
}

There's a couple of unused variables in findMin():

int index = -1;
int last_index = 0;

Prefer to use initializers rather than assignment in constructors:

Graph(T& data, int id = -1)
    : mData(data),
      mDist(INT32_MAX),
      mParent(),
      mVisited(false),
      mEdges(),
      mPath(),
      mID(id)
{
}

All the points above are found simply by compiling with a reasonable set of warnings (g++ -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++), so easily fixed yourself.

The GraphMeta member functions (constructors and assignment) add no value, as they are identical to the compiler-generated code, so we can omit them. We just need to change the member order to match the construction call, and use braces at the call site:

struct GraphMeta
{
    Graph::GraphPTR edge;
    int weight;
};

    mEdges.push_back(GraphMeta{ptr, weight});

I'd like to move in to look at GetObjectPTR.

We're missing some of the point of std::make_shared(), in that we don't need to construct an object and copy it in; though we do need to read How do I call std::make_shared on a class with only protected or private constructors? (or to make the Graph constructor public).

It doesn't make sense to make a GraphFactory of rvalue-references, so std::forward() is pointless in this method; we should accept a reference to const T instead.

There's no need to return its shared pointer by reference - pointers should almost always be passed by value

There's also much repetition of work here (repeated lookup in the map). We should keep a reference or iterator to avoid the re-work.

I ended up with:

std::shared_ptr<Graph<T>> GetObjectPTR(const T& data, int id, bool addToPath)
{
    auto pair = std::make_pair<const T&,const int&>(data, id);
    auto found = mGraphDataMap.find(pair);
    if (found != mGraphDataMap.end()) {
        return found->second;
    }

    auto p = std::make_shared<Graph<T>>(data, id);
    mGraphDataMap[pair] = p;
    mTotalPath.push_back(p);
    if (addToPath) {
        mCurrentPath.push_back(p);
    }

    return p;
}

Additionally, a handful of T& arguments on other functions became const T& to match.

This expression:

   GraphPTR graph = mPath[mPath.size() - 1];

is normally written:

    GraphPTR graph = mPath.back();
\$\endgroup\$
4
  • \$\begingroup\$ BTW, this isn't a complete review - I ran out of time, but I might be back to add to it if you don't get other answers. \$\endgroup\$ Commented Oct 10, 2019 at 12:33
  • \$\begingroup\$ Thanks for great comment. I have opinion that we should always passing template object as ref because that object can be anything in future, I don't want to copy always. In Graph<T> class always passes object as ref because i want to create pointer to object so that if some modification in future (like add edge to that object) i should be keeping track of that. Shared_ptr by ref is fine stackoverflow.com/questions/3310737/… \$\endgroup\$ Commented Oct 10, 2019 at 12:35
  • 1
    \$\begingroup\$ That question is slightly different - that's about how to pass the pointer into a function. Here, we were returning a (mutable) reference to a map value. In principle, the receiving could could reset the referenced pointer, or hold onto it beyond its lifetime. Good practice for return values isn't the same as good practice for parameters! \$\endgroup\$ Commented Oct 10, 2019 at 12:49
  • \$\begingroup\$ Gotcha Thanks :) but object passing by ref is batter here. Do you have opinion \$\endgroup\$ Commented Oct 10, 2019 at 12:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.