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

[martaOlegovna]

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

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

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

Код: Выделить всё

#pragma once
#include <vector>
struct Edge 
{
public:
    Edge(int v, int w);
private:
    int mV; 
    int mW;
};
 
struct Node 
{
public:
    Node(int x, Node* node);
private:
    int mX;
    Node* mNode;
};
 
class Graph
{
public:
    Graph(int key, bool digraph);
    void insert(int key);
    void insertEdge(Edge edge);
    void remove(int key);
    void removeEdge(Edge edge);
 
    int V();
    int E();
    bool directed();
    
private:
    int Vcnt;
    int Ecnt;
    bool mDigraph = false;
    std::vector<std::vector<int>> mVector;
    std::vector<Node*>  adjacencyLists;
};

Код: Выделить всё

#include "Graph.h"
 
 
Edge::Edge(int v, int w)
    : mV(v)
    , mW(w)
{
}
 
 
Node::Node(int x, Node* node)
    : mX(x)
    , mNode(node)
{
}
 
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;
}

[Absurd]

Я делаю такие структуры как и в СУБД. В вашем случае, наверное, будет так:

1) таблица узлов с первичным ключом. В С++ обычно используют адрес объекта в оперативной памяти, он гарантированно уникален ( std::unordered_set<Node*> ).

2) таблица ребро->вес, у нее ключ составной в виде кортежа из двух узлов (std::unordered_map< std::tuple<Node*, Node*>, int, Comparer(..), Hasher()> );. Так же надо определить компаратор и хэшер для кортежа std::tuple<Node*, Node*>

3) Таблица узел А -> узел Б, где на каждый A допускается несколько Б, в ней первичного ключа нет и поэтому надо использовать мультимап: std::unordered_multimap<Node*, Node*>.