当前位置: 动力学知识库 > 问答 > 编程问答 >

c++ - Boost (BGL): After calling djikstra's shortest paths I need to walk the tree

问题描述:

Kind of a noob with Boost Graph library:

Given I have bundled vertices and edges like such:

struct MarkerVertex{

MarkerID id;

};

struct RelationshipEdge{

float weight;

//there's other things in here too

//this is the only part that's relevant

};

and a graph descriptor like such:

typedef boost::adjacency_list<

boost::vecS, boost::vecS, boost::undirectedS,

MarkerVertex, RelationshipEdge>

Graph_t;

I call dijkstra's shortest path in the following manner:

dijkstra_shortest_paths(m_graph, startDescriptor,

weight_map(get(&RelationshipEdge::weight, m_graph))

.distance_map(make_iterator_property_map(distances.begin(),

get(boost::vertex_index, m_graph))));

using the weight property of the RelationshipEdge struct as the path distance

I would like to then traverse the graph from the start to each of the nodes, and do a calculation based on the previous node in the traversal

For instance

  • A->B
  • A->C
  • A->C->D
  • A->C->E

then say I'd like to assign "A" to A

- "AB" to B

- "AC" to C

- "ACD" to D

- "ACE" to E

This is just an example, I actually have to do matrix multiplication, so I do not want to start at the end because I actually have to calculate the predecessor values before I can calculate the leaves. Also, some vertices might not connect to the start vertex (possibly many)

What would be the boost syntax to walk from the source node to the rest and do some sort of calculation like that?

分享给朋友:
您可能感兴趣的文章:
随机阅读: