本文整理汇总了C++中graph类的典型用法代码示例。如果您正苦于以下问题:C++ graph类的具体用法?C++ graph怎么用?C++ graph使用的例子?那么恭喜您, 这里精选的类代码示例或许可以为您提供帮助。
在下文中一共展示了graph类的20个代码示例,这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞,您的评价将有助于我们的系统推荐出更棒的C++代码示例。
示例1: dijkstra
map<char *, int> dijkstra(graph g, char* source_node) {
int MAX_INT = 63356 ;
// build the heap
heap nodes_heap;
// create a map with not visited nodes
map<char *, int> m_not_visited;
graph::iterator it;
for( it = g.begin(); it != g.end(); it++)
{
if( strcmp(it->first, source_node) ){
nodes_heap.push(make_pair(MAX_INT, it->first));
m_not_visited.insert(make_pair(it->first, MAX_INT));
}
}
m_not_visited.insert(make_pair(source_node, 0));
// initialize the map that will store the shortest paths.
map<char *, int> m_shortest_path;
m_shortest_path.insert( make_pair(source_node , 0) );
while(nodes_heap.size() > 0){
pair<int, char*> node = nodes_heap.top();
if( m_not_visited.find( node.second ) == m_not_visited.end() )
continue;
m_shortest_path[node.second] = node.first;
update_heap(nodes_heap, g, source_node, m_not_visited, node.first);
m_not_visited.erase(node.second);
}
return m_shortest_path;
}
开发者ID:mateifl,项目名称:calgor,代码行数:32,代码来源:anarc08f.cpp
示例2: kruskal
void kruskal(graph &g, graph &sf)
// from weighted graph g, set sf to minimum spanning forest
// uses a priority queue with edges sorted from large to min weight
// since top of queue is the back of underlying vector
// for every edge, add to sf, but if it creates cycle, then
// remove it and move to next edge
{
g.clearMark();
pqueue edges = getEdges(g);
while (!edges.empty())
{
edgepair pair = edges.top();
edges.pop();
// add both edges to create undirected edges
sf.addEdge(pair.i, pair.j, pair.cost);
sf.addEdge(pair.j, pair.i, pair.cost);
if (isCyclic(sf))
{
sf.removeEdge(pair.i, pair.j);
sf.removeEdge(pair.j, pair.i);
}
}
}
开发者ID:mossberg,项目名称:eece3326,代码行数:25,代码来源:p6b.cpp
示例3: kruskal
void mst::kruskal(graph g) {
int num = g.num_of_vertices();
vector< vector<float> > edges;
union_find explored;
reset();
// put all connected vertices in "edges"
for(int i=0; i<num; ++i) {
for(int j=0; j<num; ++j) {
float c = g.cost(i, j);
if (c!=0) {
vector<float> temp;
temp.push_back(i);
temp.push_back(j);
temp.push_back(c);
edges.push_back(temp);
}
}
}
sort(edges.begin(), edges.end(), kruskal_compare);
for(vector<vector<float> >::iterator p=edges.begin(); p!=edges.end(); ++p) {
// both nodes in the closed set ==> detecting a cycle
vector<float> temp = *p;
int f1 = explored.find(temp[0]);
int f2 = explored.find(temp[1]);
if(f1!=-1 && f2!=-1 && f1==f2) continue;
path_cost += temp[2];
explored.insert(temp[0], temp[1]);
//cout <<"From "<<temp[0]<<" To "<<temp[1]<<" -- Cost "<<temp[2]<<endl;
}
// ckeck if there are isolated nodes
if (explored.num_of_unions() != 1) path_cost=-1;
}
开发者ID:chubbypanda,项目名称:learning,代码行数:34,代码来源:mst.cpp
示例4: findCities
void findCities(graph<int>& g, LList<int>& cities, int cityId, int p){
elem_link1<int>* start = g.point(cityId);
int dist[100]; // 100???
bool visited[100]; // 100??? - nikoi ne garantira, che id-tata na cities shte sa posledovatelni chisla pod 100
memset(dist, -1, 100);
memset(visited, 0, 100);
if (start){
visited[start->inf] = true;
dist[start->inf] = 0;
queue<int> q;
q.push(start->inf);
while (!q.empty()){
int current = q.front();
q.pop();
elem_link1<int>* p = g.point(current);
p = p->link;
while (p){
if (!visited[p->inf]){
visited[p->inf] = true;
dist[p->inf] = dist[current] + 1;
q.push(p->inf);
}
p = p->link;
}
}
for (int i = 0; i < 100; i++){
if (dist[i] >= 0 && dist[i] <= p){
cities.toEnd(i);
}
}
}
}
开发者ID:stefolog,项目名称:fmi-sdp2015-test2,代码行数:35,代码来源:zad1_81222.cpp
示例5: path
// calculate the path using dijkstra's algo.
void dijkstra::path(graph g, int u, int v) {
int num = g.num_of_vertices();
minheap* candidates = new minheap(num);
// reset the path_cost and clear the closed_set
reset();
// initialize the heap
// the nodes in the heap are those of "open set"
for (int i=0; i<num; ++i) {
float c = g.cost(u, i);
if (c!=0)
candidates->update(c, i);
}
while (candidates->size()!=0) {
heapitem t = candidates->pop();
int node = t.get_node();
// not record the duplicated probed nodes
if (closed_set.find(node)!=closed_set.end())
continue;
closed_set.insert(node);
path_cost = t.get_key();
// terminated if arrives at the destination
if (node == v)
return;
vector<int> n = g.neighbors(node);
// update the heap with newly found nodes
for(vector<int>::iterator i=n.begin(); i!=n.end(); ++i) {
candidates->update(path_cost+g.cost(node,*i), *i);
}
}
// after iteration, the v is not found
path_cost = -1;
}
开发者ID:chubbypanda,项目名称:learning,代码行数:35,代码来源:dijkstra.cpp
示例6: daiquistra
vector<int> daiquistra(graph& g, int v){
vector<int> dist(g.size(), INT_MAX);
vector<int> prev(g.size(), -1);
dist[v] = 0;
set<pair<int, int> > q;
for(int i = 0; i<g.size(); i++){
q.insert(make_pair(dist[i], i));
}
while(!q.empty()){
int u = q.begin()->second;
int p = q.begin()->first;
q.erase(q.begin());
if(dist[u] == INT_MAX)
break;
for(int i = 0; i<g[u].size(); i++){
int w = g[u][i].second;
int alt = dist[u] + g[u][i].first;
if(alt < dist[w]){
q.erase(make_pair(dist[w], w));
dist[w] = alt;
prev[w] = u;
q.insert(make_pair(dist[w], w));
}
}
}
return prev;
}
开发者ID:ivan94,项目名称:faculdade,代码行数:31,代码来源:graph.cpp
示例7: while
bool CDLib::read_edgelist(graph& g, const string& filepath) {
g.clear();
ifstream ifs;
ifs.open(filepath.c_str());
if (ifs.is_open()) {
vector<string> units;
double weight;
while (!ifs.eof()) {
weight = 1;
string line;
getline(ifs, line);
if ((line.size() > 0) && (line[0] != '#')) {
split(line, units);
if (units.size() != 0) {
if ((units.size() < 2) || (units.size() > 3)) return false;
if (units.size() == 3) weight = str2T<double>(units[2]);
g.add_node(units[0]);
g.add_node(units[1]);
g.add_edge(units[0], units[1], weight);
}
}
}
g.set_graph_name(filename(filepath));
return true;
}
return false;
}
开发者ID:BalkiLab,项目名称:graffy,代码行数:27,代码来源:graphio.cpp
示例8: kruskal
graph kruskal (graph &rede){
graph result;
int max_custo = 0;
graph::iterator it;
int no1, no2;
vertice v;
for (it = rede.begin(); it != rede.end(); it++){
v = it->second;
no1 = v.first;
no2 = v.second;
if (findset(no1) != findset(no2)){
v = ordena (v.first, v.second);
result.insert (make_pair (0, v));
join (no1, no2);
max_custo += it->first;
}
}
cout << max_custo << endl;
return result;
}
开发者ID:guilhermeleobas,项目名称:maratona,代码行数:31,代码来源:redotica.cpp
示例9: return
int dijkstra::check(graph& G)
{
if ((s == node()) || (!weights_set))
{
return GTL_ERROR;
}
bool source_found = false;
graph::node_iterator node_it;
graph::node_iterator nodes_end = G.nodes_end();
for (node_it = G.nodes_begin(); node_it != nodes_end; ++node_it)
{
if (*node_it == s)
{
source_found = true;
break;
}
}
if (!source_found)
{
return(GTL_ERROR);
}
graph::edge_iterator edge_it;
graph::edge_iterator edges_end = G.edges_end();
for(edge_it = G.edges_begin(); edge_it != edges_end; ++edge_it)
{
if (weight[*edge_it] < 0.0)
{
return false;
}
}
return GTL_OK;
}
开发者ID:WillisLing,项目名称:cassowary,代码行数:35,代码来源:dijkstra.cpp
示例10: goodCircuit
bool circuit::goodCircuit()
{
matrix<int> adj2 = circuit_graph.adjacency_matrix();
adj2 = adj2*adj2;
for(int i=0;i<circuit_graph.nVertices();i++) if(adj2(i,i)<2) return false;
return circuit_graph.isConnected();
}
开发者ID:fdenzer,项目名称:KLEG,代码行数:7,代码来源:electricity.hpp
示例11: path
void path(town start, graph<town>& g, int p, LList<town> &visited){
if (g.empty())return;
int count = 0;
queue<town> q;
q.push(start);
visited.toEnd(start);
elem_link1<town> * f = g.point(start);
f = f->link;
while (!q.empty()){
town t;
q.pop(t);
while (f){
if (p == count)return;
else if (!member(visited, f->inf)){
q.push(f->inf);
visited.toEnd(f->inf);
count++;
}
f = f->link;
}
}
}
开发者ID:stefolog,项目名称:fmi-sdp2015-test2,代码行数:26,代码来源:fn81231_zad1(1).cpp
示例12: findCycle
void findCycle(int curr, int start, bool &found, graph &g)
// checks for cycles in a graph
{
g.mark(curr);
vector<int> lst = getNeighbors(curr, g);
for (int i = 0; i < lst.size(); i++)
{
if (start == lst[i])
{
continue;
}
if (g.isMarked(lst[i]))
{
found = true;
}
else if (!g.isVisited(lst[i]))
{
findCycle(lst[i], curr, found, g);
}
} // for
g.unMark(curr);
g.visit(curr);
} // findCycle
开发者ID:tLiMiT,项目名称:EECE-3326,代码行数:27,代码来源:p6b.cpp
示例13: findSpanningForest
void findSpanningForest(graph &g, graph &sf)
// Create a graph sf that contains a spanning forest on the graph g.
{
if (isConnected(g) && !isCyclic(g))
{
sf = g;
}
else
{
// add nodes to sf
for (int i = 0; i < g.numNodes(); i++)
{
sf.addNode(g.getNode(i));
}
// build sf
for (int i = 0; i < g.numNodes(); i++)
{
for (int j = 0; j < g.numNodes(); j++)
{
if (g.isEdge(i, j) && !sf.isEdge(i, j))
{
sf.addEdge(i, j, g.getEdgeWeight(i, j));
sf.addEdge(j, i, g.getEdgeWeight(j, i));
if(isCyclic(sf))
{
sf.removeEdge(j, i);
sf.removeEdge(i, j);
} // if
} // if
} // for
} // for
} // else
} // findSpanningForest
开发者ID:tLiMiT,项目名称:EECE-3326,代码行数:35,代码来源:p6b.cpp
示例14: order_subgraphs_wrapper
void order_subgraphs_wrapper(vector<subgraph*> &sgorder, subgraph *sg,
graph &g) {
// simplify the call to the above order subgraphs
deque<vertex> order;
map<vertex,subgraph*> new_sub;
map<vertex,vertex> new_old;
if (sg == 0) {
vector<vertex> verts;
for (unsigned int i = 0; i != g.num_vertices(); ++i)
if (g.find_parent(i) == 0 && (g.adj(i).size() > 0 || g.inv_adj(i).size() > 0))
verts.push_back(i);
order_subgraphs(order, new_sub, new_old, 0, verts, g.subgraphs, g);
}
else {
order_subgraphs(order, new_sub, new_old, sg, sg->vertices, sg->subs, g);
}
map<vertex,subgraph*>::iterator itr = new_sub.begin();
for (unsigned int i = 0; i < order.size(); i++) {
map<vertex,subgraph*>::iterator iter = new_sub.find(order[i]);
if (iter != new_sub.end()) {
sgorder.push_back(iter->second);
}
}
}
开发者ID:cookjj,项目名称:btoblas,代码行数:27,代码来源:translate_utils.cpp
示例15: topo_sort
void topo_sort(graph& g, deque<vertex>& order)
{
vector<bool> visited(g.num_vertices(), false);
for (vertex i = 0; i != g.num_vertices(); ++i)
if (! visited[i])
topo_sort_r(i, g, order, visited);
}
开发者ID:cookjj,项目名称:btoblas,代码行数:7,代码来源:translate_utils.cpp
示例16: vertex_cover
vector<string> vertex_cover(const graph g) {
vector<connection> list;
copy(g.begin(), g.end(), back_inserter(list));
sort(list.begin(), list.end(), [](connection a, connection b) {
return a.second.size() > b.second.size();
});
vector<string> cover;
while (list.size()) {
connection max = list.at(0);
cover.push_back(max.first);
list.erase(list.begin());
for (string conc : max.second) {
if (!list.size())
break;
auto to_remove = find_if(list.begin(), list.end(), [conc](connection c) {
return c.first == conc;
});
if (to_remove != list.end()) {
list.erase(to_remove);
}
}
}
return cover;
}
开发者ID:hawkrives,项目名称:fast-correct-pick-one,代码行数:31,代码来源:fast.cpp
示例17: update_iters_sg
void update_iters_sg(graph &g, subgraph *sg) {
vector<iterOp_t>::iterator i;
for (i = sg->sg_iterator.conditions.begin();
i != sg->sg_iterator.conditions.end(); ++i) {
vector<string> separate;
boost::split(separate, i->right, boost::is_any_of("+"));
string newString = g.get_iter_rep(separate[0]);
for (unsigned int k=1; k < separate.size(); ++k) {
newString += "+" + g.get_iter_rep(separate[k]);
}
i->right = newString;
}
for (i = sg->sg_iterator.updates.begin();
i != sg->sg_iterator.updates.end(); ++i) {
vector<string> separate;
boost::split(separate, i->right, boost::is_any_of("+"));
string newString = g.get_iter_rep(separate[0]);
for (unsigned int k = 1; k < separate.size(); ++k) {
newString += "+" + g.get_iter_rep(separate[k]);
}
i->right = newString;
}
for (auto i : sg->subs) {
update_iters_sg(g, i);
}
}
开发者ID:cookjj,项目名称:btoblas,代码行数:32,代码来源:build_graph.cpp
示例18: recursiveDFS
void recursiveDFS(int curId, int dstId, graph &g,
stack<int> &path, bool &done)
// depth first search that uses the mem stack to search the graph g
{
if (curId == dstId)
{
done = true;
path.push(curId);
}
else
{
g.mark(curId);
g.visit(curId);
vector<int> lst = getNeighbors(curId, g);
while (!lst.empty())
{
int current = lst.back();
lst.pop_back();
if (!g.isVisited(current))
{
recursiveDFS(current, dstId, g, path, done);
}
if (done)
// if we found our node then construct our path
{
path.push(curId);
break;
}
}
}
}
开发者ID:maguire,项目名称:Optimization-Methods,代码行数:35,代码来源:program.cpp
示例19: draw_dashes_draft
//------------------------------------------------------------------------
void draw_dashes_draft()
{
pixfmt pixf(rbuf_window());
base_renderer rb(pixf);
primitives_renderer prim(rb);
outline_rasterizer ras(prim);
int i;
for(i = 0; i < m_graph.get_num_edges(); i++)
{
graph::edge e = m_graph.get_edge(i);
graph::node n1 = m_graph.get_node(e.node1, width(), height());
graph::node n2 = m_graph.get_node(e.node2, width(), height());
curve c(n1.x, n1.y, n2.x, n2.y);
dash_stroke_draft<curve> s(c, 6.0, 3.0, m_width.value());
int r = rand() & 0x7F;
int g = rand() & 0x7F;
int b = rand() & 0x7F;
int a = 255;
if(m_translucent.status()) a = 80;
prim.line_color(agg::srgba8(r, g, b, a));
ras.add_path(s);
}
}
开发者ID:Bashakov,项目名称:agg,代码行数:26,代码来源:graph_test.cpp
示例20: getMap
bool maze::findShortestPath1(graph &g)
//finds the shortest path in the given graph using DFS
{
g.clearVisit();
g.clearMark();
int start = getMap(0, 0);
int end = getMap(numRows() - 1, numCols() - 1);
vector< stack<int> > rpaths = nonRecursiveDFS(start, end, g);
stack<int> reverse_path;
for(int i = 0; i < rpaths.size(); i++)
if (rpaths[i].size() > reverse_path.size())
reverse_path = rpaths[i];
stack<int> path;
while (!reverse_path.empty())
{
int top = reverse_path.top();
reverse_path.pop();
if (g.isVisited(top))
{
path.push(top);
}
}
printPath(path);
}
开发者ID:maguire,项目名称:Optimization-Methods,代码行数:31,代码来源:program.cpp
注:本文中的graph类示例由纯净天空整理自Github/MSDocs等源码及文档管理平台,相关代码片段筛选自各路编程大神贡献的开源项目,源码版权归原作者所有,传播和使用请参考对应项目的License;未经允许,请勿转载。 |
请发表评论