CODEWITHSUNDEEP
c++algorithmgraph
czaduu
czaduu

Reputation: 49

algorithm graph fiber network skeleton

I have a exercise to do fiber network skeleton. Each node is represented by IP address. On input I get commands to build network (B) and then commands to check (T) if there is connection between one node and another.

For every T commands I must to answer: yes or no. So in this example it will be: Y N Y Y N. I have good results, but my solution fails with execution time - I check it here: https://pl.spoj.com/problems/TFIBRE/

My code (edited):

#include <iostream>
#include <string>
#include <unordered_map>
#include <list>
#include <set>
#include <arpa/inet.h>

using namespace std; 
class Graph 
{ 
    std::unordered_map<uint32_t, bool> visited;
    std::unordered_map<uint32_t, set<uint32_t>> adj; 

    bool DFSUtil(const uint32_t& v, const uint32_t&, std::unordered_map<uint32_t, bool>& visited); 
public:
    
    Graph(): visited{}, adj{}
    {}
    
    void addEdge(const uint32_t& v, const uint32_t& w); 
    bool DFS(const uint32_t& v, const uint32_t& el);
}; 

void Graph::addEdge(const uint32_t& v, const uint32_t& w) 
{ 
    adj[v].insert(w);
    adj[w].insert(v);
} 
  
bool Graph::DFSUtil(const uint32_t& v, const uint32_t& el, std::unordered_map<uint32_t, bool>& visited) 
{ 
    if (v == el){
        return true;
    }

    visited[v] = true; 

    set<uint32_t>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i]){
            if(DFSUtil(*i, el, visited))
                return true;
            else
                continue;
        }
    return false;
} 
  
bool Graph::DFS(const uint32_t& v, const uint32_t& el) 
{ 
    visited.clear();
    
    for (std::pair<uint32_t, set<uint32_t>> element : adj)
        visited[element.first] = false;

    return DFSUtil(v, el, visited); 
}

int main() 
{ 
    Graph g;
    char command;
    char addr1[16];
    char addr2[16];
    
    in_addr ip1;
    in_addr ip2;

    
    while (scanf("%c %s %s ", &command, addr1, addr2) == 3)
    {        
        inet_aton(addr1, &ip1);
        inet_aton(addr2, &ip2);
        
        if (command == 'B')
            g.addEdge(ip1.s_addr, ip2.s_addr);
        else
            cout << (g.DFS(ip1.s_addr, ip2.s_addr) ? "T\n" : "N\n");
    }
    return 0; 
}

Searching takes the longest time. What can I do to improve this? Maybe I shouldn't use stl containers? but what to use then?

Upvotes: 0

Views: 137

Answers (2)

mcdowella
mcdowella

Reputation: 19621

If links are bi-directional and there is no limitation on distance you could try using https://en.wikipedia.org/wiki/Disjoint-set_data_structure (a.k.a. Union-Find). When you see a link, merge the sets owning the two ends of the link. To test for connectivity, see if the two ends have been merged into the same set.

Upvotes: 1

John Zwinck
John Zwinck

Reputation: 249502

An obvious problem is that you're allocating memory unnecessarily many times.

To start with you create a fresh std::vector<std::string> words; for every line which is pointless because you know each line has three words. So you can do this:

char command; // B or T
char addr1[16];
char addr2[16];
while (scanf("%c %s %s", &command, addr1, addr2) == 3)
{
    if (command == 'B')
        g.addEdge(addr1, addr2);
    else
        cout << g.DFS(addr1, addr2) ? "Y\n" : "N\n";
}

Note I also removed your use of endl which is slow because it forces a buffer flush every time.

Continue my work to remove more allocations from your code. For example your DFS() creates a new unordered_map every time, which is totally unnecessary, it could use the same map every time and just clear() it, reusing the same allocated memory. And using std::string is pointless when you know the strings are always between 8 and 16 bytes including the null terminator.

Even this line allocates memory!

for (std::pair<std::string, set<std::string>> element : adj)

It should use a reference, not a copy of each value:

for (auto& element : adj)

Upvotes: 0

Related Questions