Given an undirected unweighted graph, you want to evaluate its diameter,
which is the largest distance between two nodes of the graph.
Issue: the graph can be very large (millions of nodes!).
It won't be possible to compute the diameter's exact value every time. For instance, running a BFS (Breadth-First-Search) from each node would be too slow...
We will therefore compute an approximate value, and more precisely a lower bound.
This was discussed during the course, but ask again if you didn't understand.
I recommend that you simply re-use the BFS implementation done in the previous session (TD1): it's bundled in the test archive test.tar.gz.
-
In the file diam1.cc, finish writing the function DiametreLB() described in file diam1.h:
⚠ I'm providing excellent boilerplate for the .cc, with the "Time Limit" all written for you. Use it! ⚠
#ifndef __DIAM1_H
#define __DIAM1_H
#include <utility>
#include "ugraph.h"
using namespace std;
// Given a graph, this function tries to find two nodes whose distance
// to each other is the as large as possible (the "distance" between two
// nodes is the length of the shortest path between them).
//
// This will represent a lower bound of the diameter.
//
// WARNING:
// Your algorithm will have to run within a given maximum time:
// Tmax = 50ms + (M+N)*1µs, where M is the number of edges and N the
// number of nodes. This corresponds to O(M+N) complexity.
//
// For example, if M = 10M (10 millions), N = 1M (1million), Tmax = 11.05s.
//
// Then, the score you'll get will solely depend on the diameter your
// program finds for the various test graphs: the greater the lower bound,
// the better the score.
// But if you exceed the time limit (on my test machine!), your score
// will be zero: keep a safe margin!
pair<int, int> DiametreLB(const UndirectedGraph& graph);
#endif // __DIAM1_H
Test:
rm test.tar.gz; wget --no-cache http://fabien.viger.free.fr/oc/td5/test.tar.gz
tar xf test.tar.gz
make diam1
TO SUBMIT: diam1.cc
-
Implement in a file diam2.cc the function DiametreUB() described in file diam2.h:
#ifndef __DIAM2_H
#define __DIAM2_H
#include <vector>
#include "ugraph.h"
using namespace std;
// Given an undirected unweighted graph, this function returns either:
// - a "central" node (so, a vector<int> with a single element)
// that minimizes the "radius" of the graph for that center: the
// "radius" is the largest distance from the center to any other node.
// - a "central" sub-clique, i.e. a subset of nodes that are pairwise
// directly connected by an edge, and such that the "radius" is minimal
// for that "multi-center" (if that's unclear, ask me).
//
// In both cases, one can deduce an upper bound of the graph diameter:
// - if we returned a single node, with radius R: Diameter <= 2*R
// - if we returned a subclique, with radius R: Diameter <= 2*R+1
//
// To start simple, you can start by always returning a single node.
// The next improvement step should be to either return a single node,
// or an edge (which is a subclique of size 2).
// Then, you may try to further improve by returning larger sub-cliques
// when it helps.
//
// WARNING:
// Same time limit as the previous exercise.
// The score will this time be based on the upper bound of the diameter
// that can be deduced from your "center": the smaller the radius, the
// better the diameter upper bound, and the better the score.
vector<int> DiametreUB(const UndirectedGraph& graph);
#endif // __DIAM2_H
Test: make diam2
TO SUBMIT: diam2.cc
|
|
 |