graphmp.h

Go to the documentation of this file.

#ifndef GRAPHMP_H
#define GRAPHMP_H

#ifdef GCC_ATOMIC
//#//////////////////////////////////////////////
class TNGraphMP;

typedef TPt<TNGraphMP> PNGraphMP;

//#//////////////////////////////////////////////

class TNGraphMP {
public:
  typedef TNGraphMP TNet;
  typedef TPt<TNGraphMP> PNet;
public:
  class TNode {
  private:
    TInt Id;
    TIntV InNIdV, OutNIdV;
  public:
    TNode() : Id(-1), InNIdV(), OutNIdV() { }
    TNode(const int& NId) : Id(NId), InNIdV(), OutNIdV() { }
    TNode(const TNode& Node) : Id(Node.Id), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { }
    TNode(TSIn& SIn) : Id(SIn), InNIdV(SIn), OutNIdV(SIn) { }
    void Save(TSOut& SOut) const { Id.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); }
    int GetId() const { return Id; }
    int GetDeg() const { return GetInDeg() + GetOutDeg(); }
    int GetInDeg() const { return InNIdV.Len(); }
    int GetOutDeg() const { return OutNIdV.Len(); }
    int GetInNId(const int& NodeN) const { return InNIdV[NodeN]; }
    int GetOutNId(const int& NodeN) const { return OutNIdV[NodeN]; }
    int GetNbrNId(const int& NodeN) const { return NodeN<GetOutDeg()?GetOutNId(NodeN):GetInNId(NodeN-GetOutDeg()); }
    bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId) != -1; }
    bool IsOutNId(const int& NId) const { return OutNIdV.SearchBin(NId) != -1; }
    bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
    void PackOutNIdV() { OutNIdV.Pack(); }
    void PackNIdV() { InNIdV.Pack(); }
    void SortNIdV() { InNIdV.Sort(); OutNIdV.Sort();}
    friend class TNGraphMP;
  };
  class TNodeI {
  private:
    typedef THashMP<TInt, TNode>::TIter THashIter;
    THashIter NodeHI;
  public:
    TNodeI() : NodeHI() { }
    TNodeI(const THashIter& NodeHIter) : NodeHI(NodeHIter) { }
    TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI) { }
    TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; return *this; }
    TNodeI& operator++ (int) { NodeHI++; return *this; }
    bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
    bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
    int GetId() const { return NodeHI.GetDat().GetId(); }
    int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
    int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
    int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
    void SortNIdV() { NodeHI.GetDat().SortNIdV(); }

    int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }

    int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }

    int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
    bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
    bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
    bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
    friend class TNGraphMP;
  };
  class TEdgeI {
  private:
    TNodeI CurNode, EndNode;
    int CurEdge;
  public:
    TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
    TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
    TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
    TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; }  return *this; }
    TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++;
      while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } }  return *this; }
    bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
    bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
    int GetId() const { return -1; }
    int GetSrcNId() const { return CurNode.GetId(); }
    int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
    friend class TNGraphMP;
  };
private:
  TCRef CRef;
  TInt MxNId;
  THashMP<TInt, TNode> NodeH;
private:
  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
public:
  TNGraphMP() : CRef(), MxNId(0), NodeH() { }
  explicit TNGraphMP(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); }
  TNGraphMP(const TNGraphMP& Graph) : MxNId(Graph.MxNId), NodeH(Graph.NodeH) { }
  TNGraphMP(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { }
  void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); }
  static PNGraphMP New() { return new TNGraphMP(); }

  static PNGraphMP New(const int& Nodes, const int& Edges) { return new TNGraphMP(Nodes, Edges); }
  static PNGraphMP Load(TSIn& SIn) { return PNGraphMP(new TNGraphMP(SIn)); }
  bool HasFlag(const TGraphFlag& Flag) const;
  TNGraphMP& operator = (const TNGraphMP& Graph) {
    if (this!=&Graph) { MxNId=Graph.MxNId; NodeH=Graph.NodeH; }  return *this; }
  
  int GetNodes() const { return NodeH.Len(); }
  void SetNodes(const int& Length) { NodeH.SetLen(Length); }

  int AddNode(int NId = -1);
  int AddNodeUnchecked(int NId = -1);
  int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }

  int AddNode(const int& NId, const TIntV& InNIdV, const TIntV& OutNIdV);

  int AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& SrcVId, const int& DstVId);

  void DelNode(const int& NId);
  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
  TNodeI BegNI() const { return TNodeI(NodeH.BegI()); }
  TNodeI EndNI() const { return TNodeI(NodeH.EndI()); }
  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId)); }
  // GetNodeC() has been commented out. It was a quick shortcut, do not use.
  //const TNode& GetNodeC(const int& NId) const { return NodeH.GetDat(NId); }
  int GetMxNId() const { return MxNId; }
  int Reserved() const {return NodeH.GetReservedKeyIds();}

  int GetEdges() const;

  int AddEdge(const int& SrcNId, const int& DstNId);
  int AddEdgeUnchecked(const int& SrcNId, const int& DstNId);
  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
  int AddOutEdge1(int& SrcIdx, const int& SrcNId, const int& DstNId);
  int AddInEdge1(int& DstIdx, const int& SrcNId, const int& DstNId);
  void AddOutEdge2(const int& SrcNId, const int& DstNId);
  void AddInEdge2(const int& SrcNId, const int& DstNId);

  void AddNodeWithEdges(const TInt& NId, TIntV& InNIdV, TIntV& OutNIdV);


  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const;
  TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0){NI++;} return TEdgeI(NI, EndNI()); }
  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
  // /// Not supported/implemented!
  // TEdgeI GetEI(const int& EId) const; // not supported
  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;

  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
  void GetNIdV(TIntV& NIdV) const;

  bool Empty() const { return GetNodes()==0; }
  void Clr() { MxNId=0; NodeH.Clr(); }
  void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes); } }
  void ReserveNodeDegs(const int& Idx, const int& InDeg, const int& OutDeg) { if (InDeg > 0) NodeH[Idx].InNIdV.Reserve(InDeg); if (OutDeg > 0) NodeH[Idx].OutNIdV.Reserve(OutDeg); }
  void ReserveNIdInDeg(const int& NId, const int& InDeg) { GetNode(NId).InNIdV.Reserve(InDeg); }
  void ReserveNIdOutDeg(const int& NId, const int& OutDeg) { GetNode(NId).OutNIdV.Reserve(OutDeg); }
  void SortEdges(const int& Idx, const int& InDeg, const int& OutDeg) { if (InDeg > 0) NodeH[Idx].InNIdV.Sort(); if (OutDeg > 0) NodeH[Idx].OutNIdV.Sort(); }
  void SortNodeAdjV() { for (TNodeI NI = BegNI(); NI < EndNI(); NI++) { NI.SortNIdV();} }

  void Defrag(const bool& OnlyNodeLinks=false);

  bool IsOk(const bool& ThrowExcept=true) const;
  void Dump(FILE *OutF=stdout) const;

  static PNGraphMP GetSmallGraph();
  friend class TPt<TNGraphMP>;
  friend class TNGraphMPMtx;
};

// set flags
namespace TSnap {
template <> struct IsDirected<TNGraphMP> { enum { Val = 1 }; };
}

#else

// substitute TNGraph for TNGraphMP on non-gcc platforms
//typedef TNGraph TNGraphMP;
//typedef TPt<TNGraphMP> PNGraphMP;

#endif // GCC_ATOMIC

#endif // GRAPHMP_H