проблема задокументирована в коде, посмотрите на него. Я пытаюсь отодвинуть ребро, но оно не вставлено. Может быть, я должен инициализировать даже списки, но я сделал в конструкторе, и ничего не меняется
Вот функция, в которой я пытаюсь добавить ребро в список смежности:
void Graph::addEdge(int vertex1, int vertex2){
if(!adjacent(vertex1, vertex2)) // if there isn't yet a Edge
adjacency_list[vertex1].push_back(Edge(vertex2, 1)); // add this edge without weight
std::cout << Edge(vertex2, 1) << std::endl; // THE OBJECT EDJE IS PROPERLY CREATED
std::cout << adjacency_list[vertex1].size() << std::endl; // THE SIZE IS EVERYTIME 0
printlist(adjacency_list[vertex1]); // THIS FUNCTION PRINTS JUST end, IN THE LIST THERE IS NOTHING
}
А вот конструктор графа, где есть переменная списка смежности и его инициализация
class Graph{
public:
//Graph constructor that takes as parameter the number of vertices in the Graph
Graph(int NumberOfVertices):vertices(NumberOfVertices),
edges(0),
adjacency_list(NumberOfVertices){
for(int x = 0; x < numberOfVertices; x++) adjacency_list[x] = std::list<Edge>();
};
~Graph() { adjacency_list.clear(); }
int V() const { return vertices; }
int E() const { return edges; }
Edge returnEdge(std::list<Edge> list, const int vertex2);
bool adjacent (int vertex1, int vertex2);
std::list<Edge> neighbors(int vertex1) const;
void addEdge(int vertex1, int vertex2);
Edge *deleteFromList(Edge *list, const int vertex2);
void deleteEdge(int vertex1, int vertex2);
int getEdgeWeight(int vertex1, int vertex2);
void setEdgeWeight(int vertex1, int vertex2, int weight);
int incrementEdges() { edges++; } //increment by 1 the number of edges
private: int vertices, //number of vertices
edges; //number of edges
std::vector<std::list<Edge> > adjacency_list; //adjacency_list: every element of index x the vector is a list of edges from x
};
Мне интересно, должен ли я инициализировать все списки в adjacency_list
вектор, но я не знаю, как это сделать. Как я могу решить проблему?
В линии возможна проблема вне зоны действия adjacency_list[vertex1].push_back(Edge(vertex2, 1));
а именно operator[]
не сигнализирует, находится ли запрошенный индекс вне диапазона. Чтобы решить эту проблему вы можете
adjacency_list
вектор по adjacency_list.max_size()
метод, а затем измените размер вектора, если необходимо, используя adjacency_list.resize()
или жеadjacency_list.at()
индексировать вектор, но проверить на out-of-range
исключение.По соображениям производительности было бы наиболее удобно построить достаточно большой вектор в начале.
Еще одним способом может быть использование map<list<Edge> >
(или unordered_map) вместо vector
,
Других решений пока нет …