data-structures/Graph.h at master · juancho11gm/data-structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#ifndef __GRAPH__H__
#define __GRAPH__H__

#include <map>
#include <string>
#include <vector>
#include <fstream>


template< class T, class C >
class Graph
{
public:
  typedef std::vector< T >                TVertices;
  typedef std::map< unsigned long, C >    TRow;
  typedef std::map< unsigned long, TRow > TMatrix;
  typedef std::vector< bool >             TMarks;

protected:
  struct DijkstraNode
  {
    unsigned long Vertex;
    unsigned long Parent;
    C Cost;
    bool operator<( const DijkstraNode& b ) const
    {
      return( b.Cost < this->Cost );
    }
  };

  struct PrimNode
  {
    unsigned long Orig;
    unsigned long Dest;
    C Cost;
    bool operator<( const PrimNode& b ) const
    {
      return( b.Cost < this->Cost );
    }
  };


public:
  Graph( );
  virtual ~Graph( );

  unsigned long AddVertex( const T& v );
  void SetArc( unsigned long i, unsigned long j, const C& c );

  unsigned long GetNumberOfVertices( ) const;
  const T& GetVertex( unsigned long i ) const;

  bool HasArc( unsigned long i, unsigned long j ) const;
  C& GetCost( unsigned long i, unsigned long j ) ;

  void PrintPlaneGraph( ) const;
  void PrintPreorderGraph( unsigned long i ) const;
  void PrintLevelsGraph( unsigned long i ) const;
  void PrintGraphAsPNG( const std::string& filename ) const;
  Graph< T, C > operator*( const Graph< T, C >& other );
  std::vector< std::vector<unsigned long> >Dijkstra( const unsigned long& start);
  std::vector< std::vector<unsigned long>  > Prim( const unsigned long& start);
  std::vector< unsigned long > FloydWarshall( const unsigned long& start, const unsigned long& end );
protected:
  void PrintPreorderGraph_Dummy( unsigned long i, TMarks& m ) const;

public:
  TVertices m_Vertices;
  TMatrix   m_Costs;
};

#include "Graph.hxx"

#endif // __GRAPH__H__

// eof - Graph.h