1. 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
   
   
2. 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
   
   

• There might be zero fight between A and C on record
• Or, for example, C might actually have won most fights against A, i.e. C is better than A.

#ifndef __FAS_H
#define __FAS_H

#include "graph.h"

// Returns a subgraph of "graph" (same nodes, but only a subset of its
// arcs) that is acyclic and that contains as many arcs as possible.
//
// TIME LIMIT: Like the previous exercises, you will have a time limit,
// which will be a bit greater:  Tmax = 50ms + (M+N)*10µs
//
// SCORING:
// - 0 if your code crashes or returns an invalid output, even if that
//   only happens for a single test case.
// - If all outputs are correct for all test cases:
//   - Each test case gets 0 if it violates the time limit
//   - Else, it'll depend on the number of arcs in your returned subgraph.
DirectedGraph MaxDAG(const DirectedGraph& graph);

#endif  // __FAS_H