In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 14th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #09 exercise sheet]


[AED050] Node Weighted Degree

In this problem you should only submit a graph.h file with a self-containing definition of a class Graph.

Base Code

Use as a basis the class Graph (see code | download code) which implements a graph (that can have directions and weights) using an adjacency list, assumes nodes are identified by integers between 1 and |V| and already has methods for adding an edge, reading a graph and doing a basic DFS and a basic BFS.

The Problem

Add a new method int weightedOutDegree(int v) to the class. The function should return weighted outgoing degree of the node v, that is, the sum of the weights of the connections that have v as start node.

All the input graphs will be simple (no self-loops or parallel edges) and weighted, but they can directed or undirected. It is guaranteed that |V|<=100, |E|<=500 and all weights will be integers between 1 and 100.

Submission

You should submit the file graph.h with the method weightedOutDegree added to Graph as requested (and without removing any of the other existing methods). You can however create additional methods and/or attribute variables, if you need them.

Mooshak will use the following code to link to your class, read the inputs, build the graphs and call your method, printing its result.

#include <iostream>
#include "graph.h"

int main() {

  // Read one input graph
  Graph *g = Graph::readGraph();

  // read q integer indicating nodes to ask for outDegree
  int q;
  std::cin >> q;
  for (int i=0; i<q; i++) {
    int x;
    std::cin >> x;
    std::cout << "g->weightedOutDegree(" << x << ") = " << g->weightedOutDegree(x) << std::endl;    
  }
  
  delete g;
  
  return 0;
}

Example Input 1 Example Output 1
9 undirected weighted
10
1 2 5
1 3 4
2 4 8
3 4 7
4 5 3
5 6 5
6 9 1
5 7 9
7 8 2
9 8 42
5
1 4 9 5 8
g->weightedOutDegree(1) = 9
g->weightedOutDegree(4) = 18
g->weightedOutDegree(9) = 43
g->weightedOutDegree(5) = 17
g->weightedOutDegree(8) = 44

Explanation of Example Input 1

The Graph* g of the example input 1 corresponds to the following figure:


Example Input 2 Example Output 2
9 directed weighted
8
1 3 3
2 1 2
4 1 1
5 4 1
5 6 2
6 7 2
6 8 1
8 7 3
4
6 4 2 3
g->weightedOutDegree(6) = 3
g->weightedOutDegree(4) = 1
g->weightedOutDegree(2) = 2
g->weightedOutDegree(3) = 0

Explanation of Example Input 2

The Graph* g of the example input 2 corresponds to the following figure:



Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto