SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Classes | Public Types | Public Member Functions | Static Public Member Functions | Private Attributes | Friends | List of all members
TBPGraph Class Reference

Bipartite graph. More...

#include <graph.h>

Classes

class  TEdgeI
 Edge iterator. Only forward iteration (operator++) is supported. More...
 
class  TNode
 
class  TNodeI
 Node iterator. Only forward iteration (operator++) is supported. More...
 

Public Types

enum  TNodeTy { bgsUndef, bgsLeft, bgsRight, bgsBoth }
 
typedef TBPGraph TNet
 
typedef TPt< TBPGraph > PNet
 

Public Member Functions

 TBPGraph ()
 
 TBPGraph (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a graph of Nodes (LeftNodes+RightNodes) nodes and Edges edges. More...
 
 TBPGraph (const TBPGraph &BPGraph)
 !! Reserve(Nodes, Edges); } More...
 
 TBPGraph (TSIn &SIn)
 Constructor for loading the graph from a (binary) stream SIn. More...
 
void Save (TSOut &SOut) const
 Saves the graph to a (binary) stream SOut. More...
 
bool HasFlag (const TGraphFlag &Flag) const
 Allows for run-time checking the type of the graph (see the TGraphFlag for flags). More...
 
TBPGraph & operator= (const TBPGraph &BPGraph)
 
int GetNodes () const
 Returns the total number of nodes in the graph. More...
 
int GetLNodes () const
 Returns the number of nodes on the 'left' side of the biparite graph. More...
 
int GetRNodes () const
 Returns the number of nodes on the 'right' side of the biparite graph. More...
 
int AddNode (int NId=-1, const bool &LeftNode=true)
 Adds a node of ID NId to the graph. More...
 
int AddNode (const TNodeI &NodeI)
 Adds a node of ID NodeI.GetId() to the graph. More...
 
void DelNode (const int &NId)
 Deletes node of ID NId from the graph. More...
 
void DelNode (const TNode &NodeI)
 Deletes node of ID NodeI.GetId() from the graph. More...
 
bool IsNode (const int &NId) const
 Tests whether ID NId is a node. More...
 
bool IsLNode (const int &NId) const
 Tests whether ID NId is a 'left' side node. More...
 
bool IsRNode (const int &NId) const
 Tests whether ID NId is a 'right' side node. More...
 
int GetMxNId () const
 Returns an ID that is larger than any node ID in the graph. More...
 
TNodeI BegNI () const
 Returns an iterator referring to the first node in the graph. More...
 
TNodeI EndNI () const
 Returns an iterator referring to the past-the-end node in the graph. More...
 
TNodeI GetNI (const int &NId) const
 Returns an iterator referring to the node of ID NId in the graph. More...
 
TNodeI BegLNI () const
 Returns an iterator referring to the first 'left' node in the graph. More...
 
TNodeI EndLNI () const
 Returns an iterator referring to the past-the-end 'left' node in the graph. More...
 
TNodeI BegRNI () const
 Returns an iterator referring to the first 'right' node in the graph. More...
 
TNodeI EndRNI () const
 Returns an iterator referring to the past-the-end 'right' node in the graph. More...
 
int GetEdges () const
 Returns the number of edges in the graph. More...
 
int AddEdge (const int &LeftNId, const int &RightNId)
 Adds an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartite graph. More...
 
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge between EdgeI.GetLNId() and EdgeI.GetRNId() to the graph. More...
 
void DelEdge (const int &LeftNId, const int &RightNId)
 Deletes an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartite graph. More...
 
bool IsEdge (const int &LeftNId, const int &RightNId) const
 Tests whether an edge between node IDs LeftNId and RightNId exists in the graph. More...
 
TEdgeI BegEI () const
 Returns an iterator referring to the first edge in the graph. More...
 
TEdgeI EndEI () const
 Returns an iterator referring to the past-the-end edge in the graph. More...
 
TEdgeI GetEI (const int &EId) const
 Not supported/implemented! More...
 
TEdgeI GetEI (const int &LeftNId, const int &RightNId) const
 Returns an iterator referring to edge (LeftNId, RightNId) in the graph. More...
 
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random node in the graph. More...
 
int GetRndLNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random 'left' node in the graph. More...
 
int GetRndRNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random 'right' node in the graph. More...
 
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random node in the graph. More...
 
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the bipartite graph. More...
 
void GetLNIdV (TIntV &NIdV) const
 Gets a vector IDs of all 'left' nodes in the bipartite graph. More...
 
void GetRNIdV (TIntV &NIdV) const
 Gets a vector IDs of all 'right' nodes in the bipartite graph. More...
 
bool Empty () const
 Tests whether the bipartite graph is empty (has zero nodes). More...
 
void Clr ()
 Deletes all nodes and edges from the bipartite graph. More...
 
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a biparite graph of Nodes nodes and Edges edges. More...
 
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the biparite graph. More...
 
bool IsOk (const bool &ThrowExcept=true) const
 Checks the bipartite graph data structure for internal consistency. More...
 
void Dump (FILE *OutF=stdout) const
 Print the biparite graph in a human readable form to an output stream OutF. More...
 

Static Public Member Functions

static PBPGraph New ()
 Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();. More...
 
static PBPGraph New (const int &Nodes, const int &Edges)
 Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges. More...
 
static PBPGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it. More...
 
static PBPGraph GetSmallGraph ()
 Returns a small graph on 2 'left', 3 'right' nodes and 4 edges. More...
 

Private Attributes

TCRef CRef
 
TInt MxNId
 
THash< TInt, TNode > LeftH
 
THash< TInt, TNode > RightH
 

Friends

class TPt< TBPGraph >
 

Detailed Description

Bipartite graph.

Definition at line 856 of file graph.h.

Member Typedef Documentation

typedef TPt<TBPGraph> TBPGraph::PNet

Definition at line 859 of file graph.h.

typedef TBPGraph TBPGraph::TNet

Definition at line 858 of file graph.h.

Member Enumeration Documentation

enum TBPGraph::TNodeTy
Enumerator
bgsUndef 
bgsLeft 
bgsRight 
bgsBoth 

Definition at line 860 of file graph.h.

860 { bgsUndef, bgsLeft, bgsRight, bgsBoth } TNodeTy; // left or right hand side node
TBPGraph::TNodeTy
TNodeTy
Definition: graph.h:860

Constructor & Destructor Documentation

TBPGraph::TBPGraph ( )
inline

Definition at line 973 of file graph.h.

973 : CRef(), MxNId(0), LeftH(), RightH() { }
TBPGraph::CRef
TCRef CRef
Definition: graph.h:965
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TBPGraph::TBPGraph ( const int &  Nodes,
const int &  Edges 
)
inlineexplicit

Constructor that reserves enough memory for a graph of Nodes (LeftNodes+RightNodes) nodes and Edges edges.

Definition at line 975 of file graph.h.

975 : MxNId(0) { }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TBPGraph::TBPGraph ( const TBPGraph &  BPGraph)
inline

!! Reserve(Nodes, Edges); }

Definition at line 976 of file graph.h.

976 : MxNId(BPGraph.MxNId), LeftH(BPGraph.LeftH), RightH(BPGraph.RightH) { }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TBPGraph::TBPGraph ( TSIn &  SIn)
inline

Constructor for loading the graph from a (binary) stream SIn.

Definition at line 978 of file graph.h.

978 : MxNId(SIn), LeftH(SIn), RightH(SIn) { }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967

Member Function Documentation

int TBPGraph::AddEdge ( const int &  LeftNId,
const int &  RightNId 
)

Adds an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartite graph.

Definition at line 705 of file graph.cpp.

705  {
706  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
707  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
708  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
709  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
710  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
711  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
712  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
713  if (LeftH.GetDat(LNId).IsOutNId(RNId)) { return -2; } // edge already exists
714  LeftH.GetDat(LNId).NIdV.AddSorted(RNId);
715  RightH.GetDat(RNId).NIdV.AddSorted(LNId);
716  return -1; // edge id
717 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TVec::AddSorted
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1063
TBPGraph::TNode::IsOutNId
bool IsOutNId(const int &NId) const
Definition: graph.h:882
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:865
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBPGraph::IsRNode
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
int TBPGraph::AddEdge ( const TEdgeI &  EdgeI)
inline

Adds an edge between EdgeI.GetLNId() and EdgeI.GetRNId() to the graph.

Definition at line 1039 of file graph.h.

1039 { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
TBPGraph::AddEdge
int AddEdge(const int &LeftNId, const int &RightNId)
Adds an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartit...
Definition: graph.cpp:705
int TBPGraph::AddNode ( int  NId = -1,
const bool &  LeftNode = true 
)

Adds a node of ID NId to the graph.

Definition at line 671 of file graph.cpp.

671  {
672  if (NId == -1) { NId = MxNId; MxNId++; }
673  else if (IsLNode(NId)) { IAssertR(LeftNode, TStr::Fmt("Node with id %s already exists on the 'left'.", NId)); return NId; }
674  else if (IsRNode(NId)) { IAssertR(! LeftNode, TStr::Fmt("Node with id %s already exists on the 'right'.", NId)); return NId; }
675  else { MxNId = TMath::Mx(NId+1, MxNId()); }
676  if (LeftNode) { LeftH.AddDat(NId, TNode(NId)); }
677  else { RightH.AddDat(NId, TNode(NId)); }
678  return NId;
679 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBPGraph::IsRNode
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
int TBPGraph::AddNode ( const TNodeI &  NodeI)
inline

Adds a node of ID NodeI.GetId() to the graph.

Definition at line 1003 of file graph.h.

1003 { return AddNode(NodeI.GetId(), NodeI.IsLeft()); }
TBPGraph::AddNode
int AddNode(int NId=-1, const bool &LeftNode=true)
Adds a node of ID NId to the graph.
Definition: graph.cpp:671
TEdgeI TBPGraph::BegEI ( ) const
inline

Returns an iterator referring to the first edge in the graph.

Definition at line 1046 of file graph.h.

1046 { TNodeI NI=BegLNI(); while (NI<EndLNI() && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { NI++; } return TEdgeI(NI, EndLNI()); }
TBPGraph::BegLNI
TNodeI BegLNI() const
Returns an iterator referring to the first 'left' node in the graph.
Definition: graph.h:1025
TBPGraph::EndLNI
TNodeI EndLNI() const
Returns an iterator referring to the past-the-end 'left' node in the graph.
Definition: graph.h:1027
TNodeI TBPGraph::BegLNI ( ) const
inline

Returns an iterator referring to the first 'left' node in the graph.

Definition at line 1025 of file graph.h.

1025 { return TNodeI(LeftH.BegI(), RightH.EndI()); }
THash::BegI
TIter BegI() const
Definition: hash.h:171
THash::EndI
TIter EndI() const
Definition: hash.h:176
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TNodeI TBPGraph::BegNI ( ) const
inline

Returns an iterator referring to the first node in the graph.

Definition at line 1019 of file graph.h.

1019 { return TNodeI(LeftH.BegI(), RightH.BegI()); }
THash::BegI
TIter BegI() const
Definition: hash.h:171
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TNodeI TBPGraph::BegRNI ( ) const
inline

Returns an iterator referring to the first 'right' node in the graph.

Definition at line 1029 of file graph.h.

1029 { return TNodeI(LeftH.EndI(), RightH.BegI()); }
THash::BegI
TIter BegI() const
Definition: hash.h:171
THash::EndI
TIter EndI() const
Definition: hash.h:176
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
void TBPGraph::Clr ( )
inline

Deletes all nodes and edges from the bipartite graph.

Definition at line 1073 of file graph.h.

1073 { MxNId=0; LeftH.Clr(); RightH.Clr(); }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
void TBPGraph::Defrag ( const bool &  OnlyNodeLinks = false)

Defragments the biparite graph.

Definition at line 794 of file graph.cpp.

794  {
795  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
796  LeftH[n].NIdV.Pack(); }
797  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
798  RightH[n].NIdV.Pack(); }
799  if (! OnlyNodeLinks && ! LeftH.IsKeyIdEqKeyN()) { LeftH.Defrag(); }
800  if (! OnlyNodeLinks && ! RightH.IsKeyIdEqKeyN()) { RightH.Defrag(); }
801 }
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
THash::Defrag
void Defrag()
Definition: hash.h:513
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
THash::Pack
void Pack()
Definition: hash.h:247
void TBPGraph::DelEdge ( const int &  LeftNId,
const int &  RightNId 
)

Deletes an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartite graph.

Definition at line 719 of file graph.cpp.

719  {
720  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
721  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
722  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
723  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
724  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
725  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
726  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
727  { TIntV& NIdV = LeftH.GetDat(LNId).NIdV;
728  const int n = NIdV.SearchBin(RNId);
729  if (n != -1) { NIdV.Del(n); } }
730  { TIntV& NIdV = RightH.GetDat(RNId).NIdV;
731  const int n = NIdV.SearchBin(LNId);
732  if (n != -1) { NIdV.Del(n); } }
733 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec::Del
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1130
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:865
TVec::SearchBin
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1454
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBPGraph::IsRNode
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
void TBPGraph::DelNode ( const int &  NId)

Deletes node of ID NId from the graph.

Definition at line 682 of file graph.cpp.

682  {
683  AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
684  THash<TInt, TNode>& SrcH = IsLNode(NId) ? LeftH : RightH;
685  THash<TInt, TNode>& DstH = IsLNode(NId) ? RightH : LeftH;
686  { TNode& Node = SrcH.GetDat(NId);
687  for (int e = 0; e < Node.GetOutDeg(); e++) {
688  const int nbr = Node.GetOutNId(e);
689  IAssertR(nbr != NId, "Bipartite graph has a loop!");
690  TNode& N = DstH.GetDat(nbr);
691  const int n = N.NIdV.SearchBin(NId);
692  IAssert(n!= -1);
693  N.NIdV.Del(n);
694  } }
695  SrcH.DelKey(NId);
696 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TBPGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:1010
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TBPGraph::TNode::GetOutNId
int GetOutNId(const int &NodeN) const
Definition: graph.h:878
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:362
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:865
TVec::SearchBin
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1454
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
void TBPGraph::DelNode ( const TNode &  NodeI)
inline

Deletes node of ID NodeI.GetId() from the graph.

Definition at line 1008 of file graph.h.

1008 { DelNode(NodeI.GetId()); }
TBPGraph::DelNode
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:682
void TBPGraph::Dump ( FILE *  OutF = stdout) const

Print the biparite graph in a human readable form to an output stream OutF.

Definition at line 845 of file graph.cpp.

845  {
846  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
847  fprintf(OutF, "-------------------------------------------------\nBipartite Graph: nodes: %d+%d=%d, edges: %d\n", GetLNodes(), GetRNodes(), GetNodes(), GetEdges());
848  for (int N = LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
849  const TNode& Node = LeftH[N];
850  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
851  for (int edge = 0; edge < Node.GetDeg(); edge++) {
852  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
853  fprintf(OutF, "\n");
854  }
855  fprintf(OutF, "\n");
856  /*// Also dump the 'right' side
857  fprintf(OutF, "\n");
858  for (int N = RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
859  const TNode& Node = RightH[N];
860  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
861  for (int edge = 0; edge < Node.GetDeg(); edge++) {
862  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
863  fprintf(OutF, "\n");
864  }
865  fprintf(OutF, "\n"); //*/
866 }
TBPGraph::GetLNodes
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:996
TBPGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:698
TBPGraph::GetNodes
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:994
TBPGraph::GetRNodes
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:998
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
bool TBPGraph::Empty ( ) const
inline

Tests whether the bipartite graph is empty (has zero nodes).

Definition at line 1071 of file graph.h.

1071 { return GetNodes()==0; }
TBPGraph::GetNodes
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:994
TEdgeI TBPGraph::EndEI ( ) const
inline

Returns an iterator referring to the past-the-end edge in the graph.

Definition at line 1048 of file graph.h.

1048 { return TEdgeI(EndNI(), EndNI()); }
TBPGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:1021
TNodeI TBPGraph::EndLNI ( ) const
inline

Returns an iterator referring to the past-the-end 'left' node in the graph.

Definition at line 1027 of file graph.h.

1027 { return EndNI(); }
TBPGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:1021
TNodeI TBPGraph::EndNI ( ) const
inline

Returns an iterator referring to the past-the-end node in the graph.

Definition at line 1021 of file graph.h.

1021 { return TNodeI(LeftH.EndI(), RightH.EndI()); }
THash::EndI
TIter EndI() const
Definition: hash.h:176
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TNodeI TBPGraph::EndRNI ( ) const
inline

Returns an iterator referring to the past-the-end 'right' node in the graph.

Definition at line 1031 of file graph.h.

1031 { return EndNI(); }
TBPGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:1021
int TBPGraph::GetEdges ( ) const

Returns the number of edges in the graph.

Definition at line 698 of file graph.cpp.

698  {
699  int Edges = 0;
700  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
701  Edges += LeftH[N].GetDeg(); }
702  return Edges;
703 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TEdgeI TBPGraph::GetEI ( const int &  EId) const

Not supported/implemented!

TBPGraph::TEdgeI TBPGraph::GetEI ( const int &  LeftNId,
const int &  RightNId 
) const

Returns an iterator referring to edge (LeftNId, RightNId) in the graph.

Definition at line 740 of file graph.cpp.

740  {
741  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
742  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
743  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
744  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
745  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
746  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
747  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
748  const TNodeI SrcNI = GetNI(LNId);
749  const int NodeN = SrcNI.LeftHI.GetDat().NIdV.SearchBin(RNId);
750  IAssertR(NodeN != -1, "Right edge endpoint does not exists!");
751  return TEdgeI(SrcNI, EndNI(), NodeN);
752 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TBPGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:1023
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
TBPGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:1021
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBPGraph::IsRNode
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
void TBPGraph::GetLNIdV ( TIntV &  NIdV) const

Gets a vector IDs of all 'left' nodes in the bipartite graph.

Definition at line 778 of file graph.cpp.

778  {
779  NIdV.Gen(GetLNodes(), 0);
780  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
781  NIdV.Add(LeftH.GetKey(N)); }
782 }
TBPGraph::GetLNodes
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:996
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
int TBPGraph::GetLNodes ( ) const
inline

Returns the number of nodes on the 'left' side of the biparite graph.

Definition at line 996 of file graph.h.

996 { return LeftH.Len(); }
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
THash::Len
int Len() const
Definition: hash.h:186
int TBPGraph::GetMxNId ( ) const
inline

Returns an ID that is larger than any node ID in the graph.

Definition at line 1016 of file graph.h.

1016 { return MxNId; }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TNodeI TBPGraph::GetNI ( const int &  NId) const
inline

Returns an iterator referring to the node of ID NId in the graph.

Definition at line 1023 of file graph.h.

1023 { return IsLNode(NId) ? TNodeI(LeftH.GetI(NId), RightH.EndI()) : TNodeI(LeftH.EndI(), RightH.GetI(NId)); }
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
THash::EndI
TIter EndI() const
Definition: hash.h:176
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
THash::GetI
TIter GetI(const TKey &Key) const
Definition: hash.h:178
void TBPGraph::GetNIdV ( TIntV &  NIdV) const

Gets a vector IDs of all nodes in the bipartite graph.

Definition at line 770 of file graph.cpp.

770  {
771  NIdV.Gen(GetNodes(), 0);
772  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
773  NIdV.Add(LeftH.GetKey(N)); }
774  for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
775  NIdV.Add(RightH.GetKey(N)); }
776 }
TBPGraph::GetNodes
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:994
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
int TBPGraph::GetNodes ( ) const
inline

Returns the total number of nodes in the graph.

Definition at line 994 of file graph.h.

994 { return GetLNodes() + GetRNodes(); }
TBPGraph::GetLNodes
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:996
TBPGraph::GetRNodes
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:998
int TBPGraph::GetRndLNId ( TRnd &  Rnd = TInt::Rnd)

Returns an ID of a random 'left' node in the graph.

Definition at line 762 of file graph.cpp.

762  {
763  return LeftH.GetKey(LeftH.GetRndKeyId(Rnd, 0.8));
764 }
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
THash::GetRndKeyId
int GetRndKeyId(TRnd &Rnd) const
Get an index of a random element. If the hash table has many deleted keys, this may take a long time...
Definition: hash.h:402
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
TNodeI TBPGraph::GetRndNI ( TRnd &  Rnd = TInt::Rnd)
inline

Returns an interator referring to a random node in the graph.

Definition at line 1062 of file graph.h.

1062 { return GetNI(GetRndNId(Rnd)); }
TBPGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:1023
TBPGraph::GetRndNId
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.cpp:754
int TBPGraph::GetRndNId ( TRnd &  Rnd = TInt::Rnd)

Returns an ID of a random node in the graph.

Definition at line 754 of file graph.cpp.

754  {
755  const int NNodes = GetNodes();
756  if (Rnd.GetUniDevInt(NNodes) < GetLNodes()) {
757  return GetRndLNId(Rnd); }
758  else {
759  return GetRndRNId(Rnd); }
760 }
TBPGraph::GetRndLNId
int GetRndLNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'left' node in the graph.
Definition: graph.cpp:762
TBPGraph::GetLNodes
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:996
TBPGraph::GetNodes
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:994
TBPGraph::GetRndRNId
int GetRndRNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'right' node in the graph.
Definition: graph.cpp:766
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
int TBPGraph::GetRndRNId ( TRnd &  Rnd = TInt::Rnd)

Returns an ID of a random 'right' node in the graph.

Definition at line 766 of file graph.cpp.

766  {
767  return RightH.GetKey(RightH.GetRndKeyId(Rnd, 0.8));
768 }
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
THash::GetRndKeyId
int GetRndKeyId(TRnd &Rnd) const
Get an index of a random element. If the hash table has many deleted keys, this may take a long time...
Definition: hash.h:402
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
void TBPGraph::GetRNIdV ( TIntV &  NIdV) const

Gets a vector IDs of all 'right' nodes in the bipartite graph.

Definition at line 784 of file graph.cpp.

784  {
785  NIdV.Gen(GetRNodes(), 0);
786  for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
787  NIdV.Add(RightH.GetKey(N)); }
788 }
TBPGraph::GetRNodes
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:998
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
int TBPGraph::GetRNodes ( ) const
inline

Returns the number of nodes on the 'right' side of the biparite graph.

Definition at line 998 of file graph.h.

998 { return RightH.Len(); }
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
THash::Len
int Len() const
Definition: hash.h:186
PBPGraph TBPGraph::GetSmallGraph ( )
static

Returns a small graph on 2 'left', 3 'right' nodes and 4 edges.

Definition at line 868 of file graph.cpp.

868  {
869  PBPGraph BP = TBPGraph::New();
870  BP->AddNode(0, true);
871  BP->AddNode(1, true);
872  BP->AddNode(2, false);
873  BP->AddNode(3, false);
874  BP->AddNode(4, false);
875  BP->AddEdge(0, 2);
876  BP->AddEdge(0, 3);
877  BP->AddEdge(1, 2);
878  BP->AddEdge(1, 3);
879  BP->AddEdge(1, 4);
880  return BP;
881 }
TBPGraph::New
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:982
TPt
Definition: bd.h:196
bool TBPGraph::HasFlag ( const TGraphFlag &  Flag) const

Allows for run-time checking the type of the graph (see the TGraphFlag for flags).

bool TBPGraph::IsEdge ( const int &  LeftNId,
const int &  RightNId 
) const

Tests whether an edge between node IDs LeftNId and RightNId exists in the graph.

Definition at line 735 of file graph.cpp.

735  {
736  if (! IsNode(LeftNId) || ! IsNode(RightNId)) { return false; }
737  return IsLNode(LeftNId) ? LeftH.GetDat(LeftNId).IsOutNId(RightNId) : RightH.GetDat(LeftNId).IsOutNId(RightNId);
738 }
TBPGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:1010
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TBPGraph::TNode::IsOutNId
bool IsOutNId(const int &NId) const
Definition: graph.h:882
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
bool TBPGraph::IsLNode ( const int &  NId) const
inline

Tests whether ID NId is a 'left' side node.

Definition at line 1012 of file graph.h.

1012 { return LeftH.IsKey(NId); }
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
bool TBPGraph::IsNode ( const int &  NId) const
inline

Tests whether ID NId is a node.

Definition at line 1010 of file graph.h.

1010 { return IsLNode(NId) || IsRNode(NId); }
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
TBPGraph::IsRNode
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
bool TBPGraph::IsOk ( const bool &  ThrowExcept = true) const

Checks the bipartite graph data structure for internal consistency.

Definition at line 803 of file graph.cpp.

803  {
804  bool RetVal = false;
805  // edge lists are sorted
806  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
807  if (! LeftH[n].NIdV.IsSorted()) {
808  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", LeftH[n].GetId());
809  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
810  }
811  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
812  if (! RightH[n].NIdV.IsSorted()) {
813  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", RightH[n].GetId());
814  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
815  }
816  // nodes only appear on one side
817  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
818  if (RightH.IsKey(LeftH[n].GetId())) {
819  const TStr Msg = TStr::Fmt("'Left' node %d also appears on the 'right'.", LeftH[n].GetId());
820  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
821  }
822  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
823  if (LeftH.IsKey(RightH[n].GetId())) {
824  const TStr Msg = TStr::Fmt("'Right' node %d also appears on the 'left'.", RightH[n].GetId());
825  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
826  }
827  // edges only point from left to right and right to left
828  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
829  for (int e = 0; e < LeftH[n].NIdV.Len(); e++) {
830  if (! RightH.IsKey(LeftH[n].NIdV[e]) || ! RightH.GetDat(LeftH[n].NIdV[e]).NIdV.IsIn(LeftH[n].GetId())) {
831  const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", LeftH[n].GetId(), LeftH[n].NIdV[e]());
832  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
833  }
834  }
835  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
836  for (int e = 0; e < RightH[n].NIdV.Len(); e++) {
837  if (! LeftH.IsKey(RightH[n].NIdV[e]) || ! LeftH.GetDat(RightH[n].NIdV[e]).NIdV.IsIn(RightH[n].GetId())) {
838  const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", RightH[n].GetId(), RightH[n].NIdV[e]());
839  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
840  }
841  }
842  return RetVal;
843 }
TVec::IsIn
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:797
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
ErrNotify
void ErrNotify(const char *NotifyCStr)
Definition: bd.h:74
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:865
TStr
Definition: dt.h:412
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
EAssertR
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
TStr::CStr
char * CStr()
Definition: dt.h:476
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
THash::Len
int Len() const
Definition: hash.h:186
bool TBPGraph::IsRNode ( const int &  NId) const
inline

Tests whether ID NId is a 'right' side node.

Definition at line 1014 of file graph.h.

1014 { return RightH.IsKey(NId); }
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
static PBPGraph TBPGraph::Load ( TSIn &  SIn)
inlinestatic

Static constructor that loads the graph from a stream SIn and returns a pointer to it.

Definition at line 987 of file graph.h.

987 { return PBPGraph(new TBPGraph(SIn)); }
TBPGraph::TBPGraph
TBPGraph()
Definition: graph.h:973
PBPGraph
TPt< TBPGraph > PBPGraph
Pointer to a bipartitegraph graph (TBPGraph)
Definition: graph.h:11
static PBPGraph TBPGraph::New ( )
inlinestatic

Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.

Definition at line 982 of file graph.h.

982 { return new TBPGraph(); }
TBPGraph::TBPGraph
TBPGraph()
Definition: graph.h:973
static PBPGraph TBPGraph::New ( const int &  Nodes,
const int &  Edges 
)
inlinestatic

Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges.

Definition at line 985 of file graph.h.

985 { return new TBPGraph(Nodes, Edges); }
TBPGraph::TBPGraph
TBPGraph()
Definition: graph.h:973
TBPGraph& TBPGraph::operator= ( const TBPGraph &  BPGraph)
inline

Definition at line 990 of file graph.h.

990  {
991  if (this!=&BPGraph) { MxNId=BPGraph.MxNId; LeftH=BPGraph.LeftH; RightH=BPGraph.RightH; } return *this; }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
void TBPGraph::Reserve ( const int &  Nodes,
const int &  Edges 
)

Reserves memory for a biparite graph of Nodes nodes and Edges edges.

Definition at line 790 of file graph.cpp.

790  {
791  if (Nodes>0) { LeftH.Gen(Nodes/2); RightH.Gen(Nodes/2); }
792 }
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:180
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967
void TBPGraph::Save ( TSOut &  SOut) const
inline

Saves the graph to a (binary) stream SOut.

Definition at line 980 of file graph.h.

980 { MxNId.Save(SOut); LeftH.Save(SOut); RightH.Save(SOut); }
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1060
THash::Save
void Save(TSOut &SOut) const
Definition: hash.h:141
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:966
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:968
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:967

Friends And Related Function Documentation

friend class TPt< TBPGraph >
friend

Definition at line 1088 of file graph.h.

Member Data Documentation

TCRef TBPGraph::CRef
private

Definition at line 965 of file graph.h.

THash<TInt, TNode> TBPGraph::LeftH
private

Definition at line 967 of file graph.h.

TInt TBPGraph::MxNId
private

Definition at line 966 of file graph.h.

THash<TInt, TNode> TBPGraph::RightH
private

Definition at line 968 of file graph.h.

The documentation for this class was generated from the following files: