CODEWITHSUNDEEP
c++graphadjacency-matrixadjacency-list
ptpkueqf
ptpkueqf

Reputation: 11

How to represent a graph with dummy vertices using an adjacency list?

Dummy vertex

This graph contains dummy vertices. How to store the state information of the vertices using an adjacency list? The outgoing edges should be stored for each vertex.

I used simple adjacency list. But here, for example, v14 is having two different set of outgoing edges (one with no outgoing edge and another one with two outgoing). What data structure should I use to represent such dummy nodes.

Upvotes: 1

Views: 368

Answers (1)

Aykhan Hagverdili
Aykhan Hagverdili

Reputation: 29985

Since you don't have constraints on implementation, a simple class would do. Here, we store (shared) pointers to children in a vector. (Overloaded) addChild methods return a reference to the added child, so it is easier to chain together addChilds. Operator overloading used is nice to have, but not necessary, and you may remove them if desired. Here's the code:

#include <utility>
#include <iostream>
#include <string>
#include <vector>
#include <memory>

using std::vector;
using std::string;
using std::size_t;
using std::shared_ptr;
using std::make_shared;
using std::ostream;
using std::cout;
using std::endl;

class Node {
public:
  using child_ptr_type = shared_ptr<Node>;
  using contaner_type = vector<child_ptr_type >;

  explicit Node(string lab = "Default", contaner_type ch = {})
  : label(std::move(lab))
  , children(std::move(ch))
  {}

  const string &getLabel() const
  { return label; }

  void setLabel(const string &label)
  { Node::label = label; }

  const contaner_type &getChildren() const
  { return children; }

  const Node& getChild(size_t indx) const
  { return *children[indx]; }

  Node& getChild(size_t indx)
  { return *children[indx]; }

  Node& addChild(const string& lab = "Default", const contaner_type & ch = {})
  {
    children.push_back(make_shared<Node>(lab, ch));
    return *children.back();
  }

  Node& addChild(const child_ptr_type &child)
  {
    children.push_back(child);
    return *children.back();
  }

  Node& addChild(const Node& node)
  {
    children.push_back(make_shared<Node>(node));
    return *children.back();
  }

  friend ostream& operator<<(ostream& os, const Node &node)
  {
    node.print(os);
    return os;
  }

  Node&operator[](size_t indx)
  {
    return getChild(indx);
  }

  const Node&operator[](size_t indx) const
  {
    return getChild(indx);
  }



private:
  string label;
  contaner_type children;
  void print(ostream& os, size_t level = 0) const
  {
    for (size_t i = 0; i != level; ++i) {
      os << "|----";
    }
    os << label << '\n';
    for (const auto& child : children) {
      child->print(os, level + 1);
    }
  }
};

int main()
{
  Node V1("V1");

  V1.addChild("V2").addChild("V5").addChild("V7").addChild("V10");
  V1[0].addChild("V6").addChild("V8").addChild("V10");

  V1[0][1][0].addChild("V11").addChild("V13");
  V1[0][1][0].addChild("V14");

  V1.addChild("V3").addChild("V12").addChild("V14").addChild("V6");
  V1[1][0][0].addChild("V10");

  V1.addChild("V4").addChild("V13").addChild("V8");

  cout << V1 << endl;
  return 0;
}

The tree in main is your example in the picture. Here's the output:

V1
|----V2
|----|----V5
|----|----|----V7
|----|----|----|----V10
|----|----V6
|----|----|----V8
|----|----|----|----V10
|----|----|----|----V11
|----|----|----|----|----V13
|----|----|----|----V14
|----V3
|----|----V12
|----|----|----V14
|----|----|----|----V6
|----|----|----|----V10
|----V4
|----|----V13
|----|----|----V8

Upvotes: 0

Related Questions