Реализация графа через смежные вершины

[martaOlegovna]

Здравствуйте. У меня есть задача- написать функции для графа через сопредельные вершины - добавить вершину, добавить ребро, добавить вес ребра.
Удалить вершину, удалить ребро, удалить вес ребра
Найти смежные ли ребра.

Я начала разбираться но я все равно не могу найти толковый материал. Что нашла (смогла) написила. теперь хочу попросить Вас в помощи. Можете дать ссылку на исходник чтобы можно было посмотреть как на самом деле реализованы эти функции. или если код есть в книгах буду благодарна. А то я уже 2 неделю не могу ничего толкового найти.
Спасибо.

То что у меня есть:

#pragma once
#include <vector>
using AjacencyList = std::vector<Node>;
using VertexList = std::vector<AdjacencyList>;
struct Edge 
{
public:
   Edge(int v, int w);
private:
   int mV; 
   int mW;
};

struct Node
{ 
   int mEnd; 
   float mWeight; 
};

class Graph
{
public:
   Graph(int key, bool digraph);
   void insert(int key);
   void insertEdge(Edge edge);
   void remove(int key);
   void removeEdge(Edge edge);
   bool relatedEdge(Edge edge1, Edge edge2);

   int V();
   int E();
   bool directed();
   
private:
   int Vcnt;
   int Ecnt;
   bool mDigraph = false;
   std::vector<std::vector<int>>  adjacencyLists;
   
};

#include "Graph.h"


Edge::Edge(int v, int w)
   : mV(v)
   , mW(w)
{
}

Graph::Graph(int key, bool digraph)
   : Vcnt(key)
   , Ecnt(0)
   , mDigraph(digraph)
   , adjacencyLists(key)
{
   adjacencyLists.assign(key, 0);
}

void Graph::insert(int key)
{
}

void Graph::insertEdge(Edge edge)
{
   int v = edge.mV;
   int w = edge.mW;
   adjacencyLists[v] = new Node(w, adjacencyLists[v]);
   if (!mDigraph)
      adjacencyLists[w] = new Node(v, adjacencyLists[w]);
   Ecnt++;
}

void Graph::remove(int key)
{
}

void Graph::removeEdge(Edge edge)
{
}

int Graph::V()
{
   return Vcnt;
}

int Graph::E()
{
   return Ecnt;
}

bool Graph::directed()
{
   return mDigraph;
}

[martaOlegovna]

Это мне нужно написать на С++

[martaOlegovna]

Немножко доделала, но есть еще функции которые не могу доделать

#pragma once
#include <vector>
struct Edge 
{
   int mV; 
   int mW;
};

struct Node
{ 
   int mEnd; 
   float mWeight; 
};

using AjacencyList = std::vector<Node>;
class Graph
{
public:
   Graph(int key, bool digraph);
   void insert(int key);
   void insertEdge(Edge edge);
   void remove(int key);
   void removeEdge(Edge edge);
   bool relatedEdge(Edge edge1, Edge edge2);
   bool directed();
   
private:
   bool mDigraph = false;
   AjacencyList mAdjacencyLists;
};

#include "stdafx.h"
#include "Graph.h"
#include <iostream>

Graph::Graph(int key, bool digraph)
   : mDigraph(digraph)
   , mAdjacencyLists(key)
{
}

void Graph::insert(int key)
{ 
   if (mAdjacencyLists[key].mEnd == false)
      mAdjacencyLists[key].mEnd = true;
   else
      std::cout << "Sorry" << "\n";
}

void Graph::insertEdge(Edge edge)
{
   if ((mAdjacencyLists[edge.mV].mEnd == true) && (mAdjacencyLists[edge.mW].mEnd == true) 
      && (mAdjacencyLists[edge.mV].mWeight == false) && (mAdjacencyLists[edge.mW].mEnd == false) && (edge.mV != edge.mW))
   {
      Node node;
      mAdjacencyLists[edge.mV] = node.mEnd; // ???
      mAdjacencyLists[edge.mW] = node.mWeight; //???

   }
}

void Graph::remove(int key)
{
   if (mAdjacencyLists[key].mEnd == true)
   {
      mAdjacencyLists[key].mEnd = false;
      for (int i = 1; i < 1000; ++i)
      {
         if (mAdjacencyLists[i].mEnd == 1)
            --mEnd; // ????????
      }
   }
   else
      std::cout << "Error" <<"\n";
}

void Graph::removeEdge(Edge edge)
{
   if ((mAdjacencyLists[edge.mV].mEnd == true) && (mAdjacencyLists[edge.mW].mEnd == true) && (mAdjacencyLists[edge.mV].mWeight == true) 
      && (mAdjacencyLists[edge.mW].mEnd == true) && (edge.mV != edge.mW))
   {
      // ???
   
   }
}

bool Graph::relatedEdge(Edge edge1, Edge edge2)
{
   if (edge1.mW == edge2.mW)
      return true;
   return false;
}

bool Graph::directed()
{
   return mDigraph;
}

[rockclimber]

martaOlegovna в сообщении #1298877 писал(а):

Можете дать ссылку на исходник чтобы можно было посмотреть как на самом деле реализованы эти функции.

На исходник чего? Вряд ли даже для учебных заданий существуют реализации, признанные эталонными. А уж для практических нужд - тем более. От учебного задания обычно требуется, чтобы оно хоть как-то выдавало правильный ответ и не выдавало неправильный. Если ваш код это делает, то все ОК. (Я С++ не знаю, если что)

[martaOlegovna]

rockclimber в сообщении #1298997 писал(а):

martaOlegovna в сообщении #1298877 писал(а):

Можете дать ссылку на исходник чтобы можно было посмотреть как на самом деле реализованы эти функции.

На исходник чего? Вряд ли даже для учебных заданий существуют реализации, признанные эталонными. А уж для практических нужд - тем более. От учебного задания обычно требуется, чтобы оно хоть как-то выдавало правильный ответ и не выдавало неправильный. Если ваш код это делает, то все ОК. (Я С++ не знаю, если что)

если вы посмотрете на мой код, то там есть у меня вопросы , на которые я не знаю ответа. поэтому ваш ответ как спам......
Я думаю уже есть реализованые функции для графа. поэтому и спросила может кто то знает где их можно найти

[slavav]

Я прочитал ваш код. Всё очень плохо. Вы сравниваете переменные типа int и float с константами true и false. Например вес ребра. Из такого кода невозможно понять как вы собираетесь работать с данными.
Пожалуйста, вернитесь на шаг назад: опишите структуру данных словами или псевдокодом. Опишите операции над структурой данных. Участники форума вам помогут сделать описания корректными. Затем можно будет перейти к реализации на C++.

-- 22.03.2018, 11:56 --

Начнём с начала: что такое представление графа в виде списков смежности?

[martaOlegovna]

slavav в сообщении #1299003 писал(а):

Я прочитал ваш код. Всё очень плохо. Вы сравниваете переменные типа int и float с константами true и false. Например вес ребра. Из такого кода невозможно понять как вы собираетесь работать с данными.
Пожалуйста, вернитесь на шаг назад: опишите структуру данных словами или псевдокодом. Опишите операции над структурой данных. Участники форума вам помогут сделать описания корректными. Затем можно будет перейти к реализации на C++.

-- 22.03.2018, 11:56 --

Начнём с начала: что такое представление графа в виде списков смежности?

вы об векторе ? или об графе? так как вектор структура данных)
мне в моем класе граф нужно сделать две операции(функции)

class Graph
{
public:
   bool addEdge(const Edge& edge);
   bool removeEdge(const Edge& edge);

и как их реализовать я не знаю. если знаете помогите. если просто написали чтобы поспрашивать по теории. так я знаю теорию. но я ж могу вам скинуть с вики и вы так и не узнаете знаю ли я теорию или нет)

-- 22.03.2018, 11:10 --

НО как я думаю: Список смежных вершин представляет собой контейнер, каждый элемент которого является списком (vector) номеров вершин

[slavav]

Спасибо за ответ. Вы на верном пути. Два вопроса про контейнер, который вы описали:
1. Какой граф описывает такой контейнер? Направленный? Ненаправленный?
2. Вы упоминали вес ребра. Где он в вашей структуре?

[martaOlegovna]

slavav в сообщении #1299055 писал(а):

Спасибо за ответ. Вы на верном пути. Два вопроса про контейнер, который вы описали:
1. Какой граф описывает такой контейнер? Направленный? Ненаправленный?
2. Вы упоминали вес ребра. Где он в вашей структуре?

1) направленый
2) float mWeight;

struct Edge
{
   Edge(int v, int w, float weight);
   int mV;
   int mW;
   float mWeight;
};

struct Node
{
   int mEnd;
   float mWeight;
};

[slavav]

Спасибо за ответы. Вы привели две структуры. Зачем нужна структура Edge?
Определите на C++ тип структуры для хранения данных графа. Думаю что вам пригодится структура Node (неудачное название, так она не описывает никакой узел (node) графа).

[martaOlegovna]

slavav
мне не интересно гадать что вы от меня хотите.
Edge это ребро. и если я ищу ребро. значет логично что мне нужна структура ребро?!!
Я переделала, но крешится. В онлайн кампиляторе норм работает. а в вижуал креш(((
Если есть замечания пишите.

#include <iostream>
#include <algorithm>

Edge::Edge(int v, int w, float weight)
   : mV(v)
   , mW(w)
   , mWeight(weight)
{
}

bool Graph::addEdge(const Edge& edge)
{
   mVertexList.reserve(10);
   mVertexList[edge.mV].push_back({ edge.mW, edge.mWeight });
   mVertexList[edge.mW].push_back({ edge.mV, edge.mWeight });
   return true;
}

bool Graph::removeEdge(const Edge& edge)
{
   int v = edge.mV;
   int w = edge.mW;
   auto ita = find_if(mVertexList[edge.mV].cbegin(), mVertexList[edge.mV].cend(), [w](const Node& n) { return n.mEnd == w; });
   mVertexList[edge.mV].erase(ita);
   auto itb = find_if(mVertexList[edge.mW].cbegin(), mVertexList[edge.mW].cend(), [v](const Node& n) { return n.mEnd == v; });
   mVertexList[edge.mW].erase(itb);

   return true;
}

void Graph::print(const Edge & edge)
{
   std::cout << "(" << edge.mV << "," << edge.mW << "," << edge.mWeight << ")" << "\n";
}

int main()
{

   Graph graph;
   Edge edge1(0, 1, 10);
   Edge edge2(1, 2, 20);
   Edge edge3(2, 3, 30);

   graph.addEdge(edge1);
   graph.addEdge(edge2);
   graph.addEdge(edge3);

   graph.print(edge1);
   graph.print(edge2);
   graph.print(edge3);

   graph.removeEdge(edge2);

   return 0;
}

[Pphantom]

Форумный движок обеспечивает возможность подсветки кода, этим стоит пользоваться.