在无向BGL图中：我是否可以获得边缘（u，v）==（v，u）最初是作为（u，v）还是作为（v，u）添加的信息？
背景：
我使用Pythons图形工具库创建了一个图形，它在内部使用Boost Graph Library（BGL） . 每条边都有"directed attribute"指向边的源和目标： (source_range, target_range) .
我想执行无向深度优先搜索以查找两个节点之间的所有路径 . 我'm using graph-tools get_all_paths() as a basis. I altered the underlying BGL implementation in a way that traversal of the graph depends on the 2644342 . I got it working for the directed case. However when I switch the graph to undirected I have the problem that I don'知道边缘的初始方向 . 因此我不知道edge属性的顺序：
(source_range, target_range) vs (target_range, source_range)
这是我的DFS代码，其中提到了停止标准（ // Check overlap part）：
template <class Graph, class Yield, class VMap, class EMap>
void get_all_paths(size_t s, size_t t, size_t cutoff, VMap visited,
EMap startend, Yield& yield, Graph& g)
{
typedef typename graph_traits<Graph>::out_edge_iterator eiter_t;
typedef std::pair<eiter_t, eiter_t> item_t;
visited[s] = true; // set visited true for source node
// could also use refrences to startend property map here. meh...
uint8_t t_start_e1, t_end_e1, q_start_e1, q_end_e1;
uint8_t q_start_e2, q_end_e2, t_start_e2, t_end_e2;
int32_t startend_e1;
int32_t startend_e2;
typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
vector<size_t> vs = {s}; // vector of indexes
vector<item_t> stack = {out_edges(s, g)}; // vector of edge_iterator pairs
while (!stack.empty())
{
std::cout << "Stack before check overlap: ";
for (uint8_t i=0; i<stack.size(); i++) {
std::cout << " (" << source(*stack[i].first, g) << "," << target(*stack[i].first, g) << ") ";
}
std::cout << "\n";
auto& pos = stack.back(); // last element in eiter vector
// End of path because of self loop or cutoff is reached
if (pos.first == pos.second || stack.size() > cutoff)
{
visited[vs.back()] = false; // revoke visited flag for last node
vs.pop_back();
stack.pop_back();
if (!stack.empty())
++stack.back().first; // increment first iterator
continue;
}
// Check overlap
if (stack.size() > 1)
{
auto& pos_prev = *(stack.rbegin() + 1); // second last eiter
startend_e1 = startend[*pos_prev.first];
startend_e2 = startend[*pos.first];
std::cout << "Checking Edges: (" << source(*pos_prev.first, g) << "," << target(*pos_prev.first, g) << ")";
std::cout << " (" << source(*pos.first, g) << "," << target(*pos.first, g) << "):";
// take apart 2x int32_t to 8x int8_t (memory optimization)
// Undirected case:If the edge was added
// as (u,v) and (v,u) was detected
// I need to swap q(uery) and t(arget) values here.
// --> How can I detect if (u,v) was initially added as (u,v)
// or (v, u)
q_start_e1 = startend_e1 & 0xFF;
q_end_e1 = (startend_e1 >> 8) & 0xFF;
t_start_e1 = (startend_e1 >> 16) & 0xFF;
t_end_e1 = (startend_e1 >> 24) & 0xFF;
q_start_e2 = startend_e2 & 0xFF;
q_end_e2 = (startend_e2 >> 8) & 0xFF;
t_start_e2 = (startend_e2 >> 16) & 0xFF;
t_end_e2 = (startend_e2 >> 24) & 0xFF;
if ((min(t_end_e1, q_end_e2) - max(t_start_e1, q_start_e2)) < 1)
{
std::cout << "Failed\n";
++pos.first;
std::cout << "Stack after check overlap: ";
for (uint8_t i=0; i<stack.size(); i++) {
std::cout << "(" << source(*stack[i].first, g) << "," << target(*stack[i].first, g) << ") ";
}
std::cout << "\n";
continue;
}
std::cout << "Passed\n";
}
auto v = target(*pos.first, g); // get target vertex
// reached target node
if (v == t)
{
vector<size_t> path = {s}; // path vector
for (auto& ei : stack)
path.push_back(target(*ei.first, g));
yield(wrap_vector_owned<size_t>(path)); // yield path
++pos.first; // increment eiter
}
else
{
//check if node was visited
if (!visited[v]) //not visited
{
visited[v] = true;
vs.push_back(v);
stack.push_back(out_edges(v, g));
}
else // visited
{
++pos.first;
}
}
}
};
谢谢您的帮助！
更新：
我为我的问题提出了以下解决方法 . 我有一个边缘 (some_val_ref_u, some_val_ref_v) 的边缘属性 (some_val_ref_u, some_val_ref_v) . 在无向图中，边 (v,u) 仍将具有边属性 (some_val_ref_u, some_val_ref_v) . 因此，我将 some_val_ref_u 分配给 v 和 some_val_ref_v 为 u ，这是不正确的 . 在处理"reverse edge"时，我必须考虑订单 . 我想出的解决方案是在创建图表时动态设置顺序，具体取决于 v 和 u 的边缘索引 .
if edge_index[v] < edge_index[u]:
g.ep.myattr[g.edge(v,u)] = (some_val_ref_v, some_val_ref_u)
else:
g.ep.myattr[g.edge(v,u)] = (some_val_ref_u, some_val_ref_v)
所以edge属性元组的顺序取决于哪个边缘索引更小 . 因此，当遍历图形时，我可以通过比较顶点索引来确定边缘属性的顺序 .
这并没有直接回答我的问题，但希望能解决我的问题 .
2 回答
你可以简单地迭代：
这是由于邻接列表存储了每个节点的邻接列表 .
Live On Coliru
打印
sehe的答案是错误的 - 无法从 any 边缘描述符获取原始源和目标顶点，如下所示：
如上所述，一种解决方案是迭代所有边缘 .
另一个更高效的是在顶点u的外边缘（或相反的方向）寻找顶点v：