Member Avatar for shelton22

Hi Friends,

I have a graph in text file (origin, destin, link_id) such as

1   2   1
1   3   2
1   5   3
2   1   4
2   3   5
2   4   6
2   5   7
3   1   8
3   2   9
3   4   10
4   2   11
4   3   12
4   5   13
5   1   14
5   2   15
5   4   16

I declared,

vector<int>pathway;

multimap<int,vector<int>> allpathsmap;
multimap<int,vector<int>>:: iterator itapm; 
typedef pair<int,vector<int>> pairapm;

In addition I found all paths from a given Source to Destination.
and I stored them in multimap 'allpathsmap'

And I wrote the code to display them as follows:

for(itapm=allpathsmap.begin(); itapm!=allpathsmap.end(); ++itapm)
        {
        cout << endl << itapm->first <<" => ";
        for(size_t n=1; n<(*itapm).second.size(); ++n)
            {
            cout <<" "<<itapm->second[n-1]<<"->"<<itapm->second[n];
            }
        }

Eg:
If Source is 1 and Destination is 4,
1 2 4
1 3 4
1 5 4
1 2 3 4
1 2 5 4
1 3 2 4
1 5 2 4
1 3 2 5 4
1 5 2 3 4

then it displays,
1->2 2->4
1->3 3->4
1->5 5->4
1->2 2->3 3->4
1->2 2->5 5->4
1->3 3->2 2->4
1->5 5->2 2->4
1->3 3->2 2->5 5->4
1->5 5->2 2->3 3->4

Can you help me how to get the link_id of two nodes on a path?

eg:
1, 6
2, 10
3, 16
1, 5, 10
1, 7, 16
2, 9, 6
3, 15, 6
2, 9, 7, 16
3, 15, 5, 10

  • 2 Contributors
  • 1 Reply
  • 264 Views
  • 1 Hour Discussion Span
  • Latest Post Latest Post by Slavi

Dani AI

Generated

Short answer: build a lookup keyed by each ordered node pair and then translate every consecutive pair in each found path into its link_id. ’s idea (filter the input rows by origin and next-node) is the same concept — do the filter once into a fast map, then reuse it for every path.

Example implementation (single link per ordered pair). Read the three-column file into a map, then for each stored path look up each consecutive pair and collect link IDs:

#include <map>
#include <vector>
#include <utility>
#include <fstream>
#include <iostream>

std::map<std::pair<int,int>,int> edgeId;
std::ifstream fin("edges.txt");
int a,b,id;
while (fin >> a >> b >> id) edgeId[std::make_pair(a,b)] = id;

// assume foundRoutes is a container of std::vector<int> produced earlier
for (const auto& route : foundRoutes) {
    std::vector<int> linkIds;
    for (size_t i = 0; i + 1 < route.size(); ++i) {
        auto it = edgeId.find(std::make_pair(route[i], route[i+1]));
        if (it == edgeId.end()) { std::cerr << "Missing edge: " << route[i] << "->" << route[i+1] << '\n'; linkIds.clear(); break; }
        linkIds.push_back(it->second);
    }
    // print or store linkIds as needed
}

If the input can contain multiple parallel links for the same ordered pair (a multigraph), store a vector of link IDs per pair and decide how to pick one (first, smallest, all, etc.):

#include <unordered_map>
struct PairHash { size_t operator()(const std::pair<int,int>& p) const noexcept {
    return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
}};
std::unordered_map<std::pair<int,int>, std::vector<int>, PairHash> multi;
multi[{a,b}].push_back(id); // while reading file

Troubleshooting tips: confirm directionality (use ordered pairs), validate every consecutive node-pair before relying on results, log missing pairs for data-cleaning, and use unordered_map+custom hash for large inputs to get average O(1) lookups. This keeps the translation from node-paths to link-id sequences simple, fast, and reusable.

Member Avatar for Slavi

I was doing something similiar in matlab, where a had a huge data file with few thousand rows and about 15 colomns. I had to filter it so for example if value in column1 is 2 and in column2 is 4 then return the number in column 3. I think this will work with you as well, where you check according to your source and the connection next to it. Does this answer your question?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.