Можно ли удалить вершину в моем графе ускорения в списке смежности? - PullRequest
Новая
       39

Можно ли удалить вершину в моем графе ускорения в списке смежности?

2 голосов
/ 09 июня 2019

Я создал простой граф с меткой Boost, который использует внутренний список смежности. Когда я вызываю remove_vertex(v1, graph.graph());, я вижу, что количество вершин уменьшилось до 1, но когда я проверяю, существует ли вершина, она все равно возвращает true.

Я пробовал graph.remove_vertex("1");, а также remove_vertex(v1, graph.graph());, которые, похоже, не удаляют вершины. 

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <cmath> // infinity

using namespace std;

struct EdgeProperties {
    double weight = INFINITY;
    EdgeProperties() = default;
    EdgeProperties(const double d) : weight(d) {}
};

struct Node
{
    string id;
    Node() = default;
    Node(const string i) : id(i) {} 
};

typedef boost::labeled_graph<boost::adjacency_list<boost::hash_setS, boost::hash_setS, boost::directedS, Node, EdgeProperties>, std::string> BoostGraph;
typedef BoostGraph::vertex_descriptor Vertex;
typedef BoostGraph::edge_descriptor Edge;

int main(){

    BoostGraph graph;

    const Vertex& v1 = add_vertex("1", Node("1"), graph);
    const Vertex& v2 = add_vertex("2", Node("2"), graph);

    const pair<Edge, bool>& edge = add_edge(v1, v2, EdgeProperties(INFINITY), graph);

    assert(2 == boost::num_vertices(graph));
    assert(1 == boost::num_edges(graph));
    assert(boost::edge(v1, v2, graph).second); // edge from v1->v2 exists

    // delete v1
    clear_vertex(v1, graph);
    graph.remove_vertex("1");

    assert(graph.vertex("1") == graph.null_vertex());

    assert(1 == boost::num_vertices(graph));
    assert(0 == boost::num_edges(graph));
    assert(not boost::edge(v1, v2, graph).second); // edge from v1->v2 shouldn't exist anymore

    cout << "All tests passed" << endl;
    return 0;
}

Я вижу, что assert(1 == boost::num_vertices(graph)); работает, но когда я проверяю, существует ли вершина, используя assert(graph.vertex("1") == graph.null_vertex());, она возвращает false, то есть вершина 1 все еще существует.

1 Ответ

0 голосов
/ 11 июня 2019

Нет, labeleled_graph_adapter не знает, как обновить или удалить метку, что означает, что любая метка будет признана недействительной , когда соответствующий дескриптор признан недействительным (например, когда соответствующий элемент графика удален ИЛИ в некоторых модели графа при добавлении любой другой вершины / ребра).

В зависимости от того, какие именно модели вы используете, обновление меток может быть выполнено путем простой перемаркировки существующих вершин, но удаление не поддерживается операциями (просто отсканируйте кодовую базу для всех операций, выполненных на _map).

Rant Notes:

  • Адаптер Labeled_graph НЕ является частью документированного интерфейса библиотеки
  • В прошлом было много проблем, Например. :

    • Приветствия. Будьте уверены, я узнал о labeled_graph трудном пути. Честно говоря, я был немного шокирован состоянием обслуживания, в котором он находится. Возможно, легче написать более подробный код, чем бороться с утечкой абстракции. Конечно, вы можете судить сами. Если вы продолжите использовать его, возможно, вы сможете улучшить его!

    • copy_graph - adjacency_list со связанными свойствами
    • https://github.com/boostorg/graph/pull/58
...