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

Question

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.

Only the graph is to be stored. Right? Are P1 and P2 relevant to you? — Kunal Puri
Only the graph need to be stored. P1 and P2 are not relevant — ptpkueqf
@ptpkueqf See this: theoryofprogramming.com/2018/01/14/… .This is in Java. But you will get the idea. — Kunal Puri
@ptpkueqf I think you're going to have to explain what you mean by dummy vertices. I can see the graph above is a bit unusual, but exactly what a dummy vertex is, and how you want to process them is a bit unclear. — john

Ayxan Haqverdili Ayxan Haqverdili · Accepted Answer · 2019-01-20T08:23:10

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

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

1 Answers