Dr Antonio Gulli - A Collection of Graph Programming Interview Questions Solved in C++

A graph data structure involves a finite set of nodes or vertices and a set of ordered pairs called edges or arcs connecting two nodes. A graph might have labels associated to the nodes and/or to the edges, thus denoting different attributes (such as names, costs, capacity, length, colours). The first direct graph implementation represents a node and an edge as a C++ struct . The first direct graph implementation represents a node and an edge as a C++ struct .

In addition a collection of nodes is memorized in a and all the edges originating from each node are memorized in a . This representation is known as Adjacency list . In this particular implementation each node has a unique identifier NodeID , a label NodeWeight and another label representing the name of the node. Indeed each edge stores the destination NodeID , a label EdgeWeightI representing the weight of the edge and another label representing the name of the edge. The second direct graph implementation represents a Graph using a matrix of size where n is the number of nodes.

const std:: string emptyString; // // Direct Graph // with Adjacent lists class Graph { public : typedef unsigned int NodeID ; typedef unsigned int EdgeID ; typedef int NodeWeight ; typedef int EdgeWeight ; struct Edge { Edge( NodeID nid , EdgeWeight wt , const std:: string & lb ) : v( nid ), w( wt ), label( lb ) {}; const NodeID v; const EdgeWeight w; const std:: string label; }; struct Node { Node( NodeWeight wt , const std:: string & l ) : w( wt ), label( l ){}; NodeWeight w; std:: string label; }; // all nodes typedef std:: vector < Node > Nodes ; // edges from a node typedef std:: forward_list < Edge > EdgesList ; // all edges (id -> edgeList) typedef std:: vector < EdgesList > Edges ; // allocate |V| lists of edges Graph( NodeID V = 0, EdgeID E = 0) { if ( V ) { _nodes.reserve( V ); _outdegree.reserve( V ); } if ( E ) _edges.reserve( E ); }; void reserveNodes( NodeID n ) { _nodes.reserve( n ); _outdegree.reserve( n ); } void reserveEdges( EdgeID n ) { _edges.reserve( n ); } // // we can have multiple edge (v1, v2) void addEdge( NodeID v1 , NodeID v2 , EdgeWeight w = 0, const std:: string & label = emptyString) { if ( v1 > _nodes.size() || v2 > _nodes.size()) return ; Edge e( v2 , w , label ); _edges[ v1 ].push_front(e); _outdegree[ v1 ]++; } // // nodes are unique void addNode( NodeWeight w = 0, const std:: string & label = emptyString) { EdgesList el; Node n( w , label ); _nodes.push_back(n); // another node _edges.push_back(el); // with its EdgeList _outdegree.push_back(0); } const EdgesList & edges( NodeID v ) const { return _edges[ v ]; }; Graph :: NodeID outdegree( NodeID v ) const { return _outdegree[ v ]; } const Nodes & nodes() const { return _nodes; }; NodeID numNodes() const { return _nodes.size(); }; EdgeID numEdges() const { return _edges.size(); }; private : Edges _edges; Nodes _nodes; std:: vector < Graph :: NodeID > _outdegree; Graph( const Graph & g) = delete ; Graph & operator=( const Graph & g) = delete ; }; std:: ostream & operator << (std:: ostream & os , const Graph & g ) { Graph :: NodeID id = 0; for ( const auto & n : g.nodes()) { os << " node=" << id << " weight=" << n.w << " label=" << n.label << std::endl; for ( const auto & e : g.edges(id)) os << " ->" << e.v << " w=" << e.w << " label=" << n.label << " lableEdge=" << e.label << std::endl; ++id; } return os ; } // // Undirect Graph // with Adjacency Matrix template < typename T > class Matrix { public : Matrix( const Matrix &) = delete ; Matrix & operator=( const Matrix &) = delete ; Matrix( unsigned int dim1 , unsigned int dim2 ) : _M( new T *[ dim1 ]), _dim1( dim1 ), _dim2( dim2 ) { for ( unsigned int i = 0; i < dim1 ; ++i) _M[i] = new T [ dim2 ]; } Matrix( unsigned int dim1 , unsigned int dim2 , T defaultValue ) : Matrix ( dim1 , dim2 ) { for ( unsigned int i = 0; i < _dim1; ++i) for ( unsigned int j = 0; j < _dim2; ++j) _M[i][j] = defaultValue ; } Matrix( Matrix && aMatrix ) { _dim1 = aMatrix ._dim1; _dim2 = aMatrix ._dim2; _M = aMatrix ._M; aMatrix ._dim1 = 0; aMatrix ._dim2 = 0; aMatrix ._M = nullptr ; } ~Matrix() { for ( unsigned int i = 0; i < _dim1; ++i) delete [] _M[i]; delete [] _M; } T & operator()( const unsigned int i , const unsigned int j ) { return _M[ i ][ j ]; } T & operator()( const unsigned int i , const unsigned int j ) const { return _M[ i ][ j ]; } unsigned int dim1() const { return _dim1; }; unsigned int dim2() const { return _dim2; }; friend std:: ostream & operator <<(std:: ostream & out , const Matrix < T >& m ) { for ( unsigned int i = 0; i < m ._dim1; ++i){ for ( unsigned int j = 0; j < m ._dim2; ++j) out << m ._M[i][j] << ' ' ; out << std::endl; } return out ; } void swap( Matrix & other ) { std::swap(_M, other ._M); std::swap(_dim1, other ._dim1); std::swap(_dim2, other ._dim2); } private : T ** _M; unsigned int _dim1, _dim2; }; // // MatrixGraph class MatrixGraph { MatrixGraph & operator=( const MatrixGraph &) = delete ; public : typedef unsigned int NodeID ; typedef int weight ; MatrixGraph( NodeID numNodes ) : n( numNodes ) { M = new weight *[n]; for ( NodeID i = 0; i < n; ++i) { M[i] = new weight [n]; for ( NodeID j = 0; j < n; ++j) M[i][j] = 0; } } ~MatrixGraph() { for ( NodeID i = 0; i < n; ++i) delete [] M[i]; delete [] M; } MatrixGraph( const MatrixGraph & m ) { n = m .getNumNodes(); M = new weight *[n]; for ( NodeID i = 0; i < n; ++i) { M = new weight *[n]; memcpy(M[i], m .M[i], sizeof ( int )*n); } } NodeID size() const { return n; } const weight & operator()( NodeID i , NodeID j ) const { return M[ i ][ j ]; } weight & operator()( NodeID i , NodeID j ) { return M[ i ][ j ]; } NodeID getNumNodes() const { return n; } private : NodeID n; weight **M; }; std:: ostream & operator << (std:: ostream & os , const MatrixGraph & g ) { for ( MatrixGraph :: NodeID i = 0; i < g .size(); ++i){ for ( MatrixGraph :: NodeID j = 0; j < g .size(); ++j) os << g (i, j) << ' ' ; os << std::endl; } return os ; } void test() { Graph G; G.addNode(10, "donald duck" ); G.addNode(1, "daisy duck" ); G.addNode(1, "antonio" ); G.addNode(1, "milena" ); G.addNode(1, "lorena" ); G.addNode(1, "mambo" ); G.addNode(1, "salsa" ); G.addNode(1, "adriana" ); G.addEdge(0, 2); G.addEdge(1, 2, 10, "important" ); G.addEdge(1, 3); G.addEdge(2, 3); G.addEdge(2, 5); G.addEdge(2, 6); G.addEdge(4, 5); G.addEdge(5, 5); G.addEdge(5, 4); G.addEdge(5, 100); std::cout << G; MatrixGraph mgA(5); mgA(0, 1) = 3; mgA(1, 2) = 2; mgA(1, 3) = 2; mgA(2, 3) = mgA(3, 4) = 1; mgA(4, 0) = 1; std::cout << mgA; }