SNAP Library 2.4, User Reference  2015-05-11 19:40:56
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 834 of file graph.h.

Member Typedef Documentation

typedef TPt<TBPGraph> TBPGraph::PNet

Definition at line 837 of file graph.h.

typedef TBPGraph TBPGraph::TNet

Definition at line 836 of file graph.h.

Member Enumeration Documentation

enum TBPGraph::TNodeTy
Enumerator
bgsUndef 
bgsLeft 
bgsRight 
bgsBoth 

Definition at line 838 of file graph.h.

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

Constructor & Destructor Documentation

TBPGraph::TBPGraph ( )
inline

Definition at line 951 of file graph.h.

951 : CRef(), MxNId(0), LeftH(), RightH() { }
TBPGraph::CRef
TCRef CRef
Definition: graph.h:943
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:944
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 953 of file graph.h.

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

!! Reserve(Nodes, Edges); }

Definition at line 954 of file graph.h.

954 : MxNId(BPGraph.MxNId), LeftH(BPGraph.LeftH), RightH(BPGraph.RightH) { }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:944
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
TBPGraph::TBPGraph ( TSIn &  SIn)
inline

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

Definition at line 956 of file graph.h.

956 : MxNId(SIn), LeftH(SIn), RightH(SIn) { }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:944
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945

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 655 of file graph.cpp.

655  {
656  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
657  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
658  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
659  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
660  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
661  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
662  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
663  if (LeftH.GetDat(LNId).IsOutNId(RNId)) { return -2; } // edge already exists
664  LeftH.GetDat(LNId).NIdV.AddSorted(RNId);
665  RightH.GetDat(RNId).NIdV.AddSorted(LNId);
666  return -1; // edge id
667 }
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:990
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:1027
TBPGraph::TNode::IsOutNId
bool IsOutNId(const int &NId) const
Definition: graph.h:860
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:843
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:992
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
int TBPGraph::AddEdge ( const TEdgeI &  EdgeI)
inline

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

Definition at line 1017 of file graph.h.

1017 { 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:655
int TBPGraph::AddNode ( int  NId = -1,
const bool &  LeftNode = true 
)

Adds a node of ID NId to the graph.

Definition at line 621 of file graph.cpp.

621  {
622  if (NId == -1) { NId = MxNId; MxNId++; }
623  else if (IsLNode(NId)) { IAssertR(LeftNode, TStr::Fmt("Node with id %s already exists on the 'left'.", NId)); return NId; }
624  else if (IsRNode(NId)) { IAssertR(! LeftNode, TStr::Fmt("Node with id %s already exists on the 'right'.", NId)); return NId; }
625  else { MxNId = TMath::Mx(NId+1, MxNId()); }
626  if (LeftNode) { LeftH.AddDat(NId, TNode(NId)); }
627  else { RightH.AddDat(NId, TNode(NId)); }
628  return NId;
629 }
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:990
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:944
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:992
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 981 of file graph.h.

981 { 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:621
TEdgeI TBPGraph::BegEI ( ) const
inline

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

Definition at line 1024 of file graph.h.

1024 { 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:1003
TBPGraph::EndLNI
TNodeI EndLNI() const
Returns an iterator referring to the past-the-end 'left' node in the graph.
Definition: graph.h:1005
TNodeI TBPGraph::BegLNI ( ) const
inline

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

Definition at line 1003 of file graph.h.

1003 { 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:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
TNodeI TBPGraph::BegNI ( ) const
inline

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

Definition at line 997 of file graph.h.

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

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

Definition at line 1007 of file graph.h.

1007 { 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:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
void TBPGraph::Clr ( )
inline

Deletes all nodes and edges from the bipartite graph.

Definition at line 1051 of file graph.h.

1051 { MxNId=0; LeftH.Clr(); RightH.Clr(); }
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:944
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:315
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
void TBPGraph::Defrag ( const bool &  OnlyNodeLinks = false)

Defragments the biparite graph.

Definition at line 744 of file graph.cpp.

744  {
745  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
746  LeftH[n].NIdV.Pack(); }
747  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
748  RightH[n].NIdV.Pack(); }
749  if (! OnlyNodeLinks && ! LeftH.IsKeyIdEqKeyN()) { LeftH.Defrag(); }
750  if (! OnlyNodeLinks && ! RightH.IsKeyIdEqKeyN()) { RightH.Defrag(); }
751 }
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
THash::Defrag
void Defrag()
Definition: hash.h:509
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
THash::Pack
void Pack()
Definition: hash.h:243
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 669 of file graph.cpp.

669  {
670  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
671  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
672  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
673  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
674  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
675  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
676  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
677  { TIntV& NIdV = LeftH.GetDat(LNId).NIdV;
678  const int n = NIdV.SearchBin(RNId);
679  if (n != -1) { NIdV.Del(n); } }
680  { TIntV& NIdV = RightH.GetDat(RNId).NIdV;
681  const int n = NIdV.SearchBin(LNId);
682  if (n != -1) { NIdV.Del(n); } }
683 }
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:1094
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:843
TVec::SearchBin
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
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:992
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
void TBPGraph::DelNode ( const int &  NId)

Deletes node of ID NId from the graph.

Definition at line 632 of file graph.cpp.

632  {
633  AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
634  THash<TInt, TNode>& SrcH = IsLNode(NId) ? LeftH : RightH;
635  THash<TInt, TNode>& DstH = IsLNode(NId) ? RightH : LeftH;
636  { TNode& Node = SrcH.GetDat(NId);
637  for (int e = 0; e < Node.GetOutDeg(); e++) {
638  const int nbr = Node.GetOutNId(e);
639  IAssertR(nbr != NId, "Bipartite graph has a loop!");
640  TNode& N = DstH.GetDat(nbr);
641  const int n = N.NIdV.SearchBin(NId);
642  IAssert(n!= -1);
643  N.NIdV.Del(n);
644  } }
645  SrcH.DelKey(NId);
646 }
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:988
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
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:856
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:358
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:843
TVec::SearchBin
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 986 of file graph.h.

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

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

Definition at line 795 of file graph.cpp.

795  {
796  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
797  fprintf(OutF, "-------------------------------------------------\nBipartite Graph: nodes: %d+%d=%d, edges: %d\n", GetLNodes(), GetRNodes(), GetNodes(), GetEdges());
798  for (int N = LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
799  const TNode& Node = LeftH[N];
800  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
801  for (int edge = 0; edge < Node.GetDeg(); edge++) {
802  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
803  fprintf(OutF, "\n");
804  }
805  fprintf(OutF, "\n");
806  /*// Also dump the 'right' side
807  fprintf(OutF, "\n");
808  for (int N = RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
809  const TNode& Node = RightH[N];
810  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
811  for (int edge = 0; edge < Node.GetDeg(); edge++) {
812  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
813  fprintf(OutF, "\n");
814  }
815  fprintf(OutF, "\n"); //*/
816 }
TBPGraph::GetLNodes
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:974
TBPGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:648
TBPGraph::GetNodes
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:972
TBPGraph::GetRNodes
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:976
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
bool TBPGraph::Empty ( ) const
inline

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

Definition at line 1049 of file graph.h.

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

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

Definition at line 1026 of file graph.h.

1026 { 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:999
TNodeI TBPGraph::EndLNI ( ) const
inline

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

Definition at line 1005 of file graph.h.

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

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

Definition at line 999 of file graph.h.

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

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

Definition at line 1009 of file graph.h.

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

Returns the number of edges in the graph.

Definition at line 648 of file graph.cpp.

648  {
649  int Edges = 0;
650  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
651  Edges += LeftH[N].GetDeg(); }
652  return Edges;
653 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 690 of file graph.cpp.

690  {
691  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
692  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
693  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
694  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
695  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
696  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
697  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
698  const TNodeI SrcNI = GetNI(LNId);
699  const int NodeN = SrcNI.LeftHI.GetDat().NIdV.SearchBin(RNId);
700  IAssertR(NodeN != -1, "Right edge endpoint does not exists!");
701  return TEdgeI(SrcNI, EndNI(), NodeN);
702 }
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:1001
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
TBPGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:999
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:992
void TBPGraph::GetLNIdV ( TIntV &  NIdV) const

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

Definition at line 728 of file graph.cpp.

728  {
729  NIdV.Gen(GetLNodes(), 0);
730  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
731  NIdV.Add(LeftH.GetKey(N)); }
732 }
TBPGraph::GetLNodes
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:974
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 974 of file graph.h.

974 { return LeftH.Len(); }
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 994 of file graph.h.

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

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

Definition at line 1001 of file graph.h.

1001 { 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:990
THash::EndI
TIter EndI() const
Definition: hash.h:176
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 720 of file graph.cpp.

720  {
721  NIdV.Gen(GetNodes(), 0);
722  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
723  NIdV.Add(LeftH.GetKey(N)); }
724  for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
725  NIdV.Add(RightH.GetKey(N)); }
726 }
TBPGraph::GetNodes
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:972
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 972 of file graph.h.

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

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

Definition at line 712 of file graph.cpp.

712  {
713  return LeftH.GetKey(LeftH.GetRndKeyId(Rnd, 0.8));
714 }
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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:398
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 1040 of file graph.h.

1040 { 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:1001
TBPGraph::GetRndNId
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.cpp:704
int TBPGraph::GetRndNId ( TRnd &  Rnd = TInt::Rnd)

Returns an ID of a random node in the graph.

Definition at line 704 of file graph.cpp.

704  {
705  const int NNodes = GetNodes();
706  if (Rnd.GetUniDevInt(NNodes) < GetLNodes()) {
707  return GetRndLNId(Rnd); }
708  else {
709  return GetRndRNId(Rnd); }
710 }
TBPGraph::GetRndLNId
int GetRndLNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'left' node in the graph.
Definition: graph.cpp:712
TBPGraph::GetLNodes
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:974
TBPGraph::GetNodes
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:972
TBPGraph::GetRndRNId
int GetRndRNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'right' node in the graph.
Definition: graph.cpp:716
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 716 of file graph.cpp.

716  {
717  return RightH.GetKey(RightH.GetRndKeyId(Rnd, 0.8));
718 }
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
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:398
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 734 of file graph.cpp.

734  {
735  NIdV.Gen(GetRNodes(), 0);
736  for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
737  NIdV.Add(RightH.GetKey(N)); }
738 }
TBPGraph::GetRNodes
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:976
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 976 of file graph.h.

976 { return RightH.Len(); }
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
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 818 of file graph.cpp.

818  {
819  PBPGraph BP = TBPGraph::New();
820  BP->AddNode(0, true);
821  BP->AddNode(1, true);
822  BP->AddNode(2, false);
823  BP->AddNode(3, false);
824  BP->AddNode(4, false);
825  BP->AddEdge(0, 2);
826  BP->AddEdge(0, 3);
827  BP->AddEdge(1, 2);
828  BP->AddEdge(1, 3);
829  BP->AddEdge(1, 4);
830  return BP;
831 }
TBPGraph::New
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:960
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 685 of file graph.cpp.

685  {
686  if (! IsNode(LeftNId) || ! IsNode(RightNId)) { return false; }
687  return IsLNode(LeftNId) ? LeftH.GetDat(LeftNId).IsOutNId(RightNId) : RightH.GetDat(LeftNId).IsOutNId(RightNId);
688 }
TBPGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:988
TBPGraph::IsLNode
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
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:860
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
bool TBPGraph::IsLNode ( const int &  NId) const
inline

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

Definition at line 990 of file graph.h.

990 { return LeftH.IsKey(NId); }
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 988 of file graph.h.

988 { 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:990
TBPGraph::IsRNode
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:992
bool TBPGraph::IsOk ( const bool &  ThrowExcept = true) const

Checks the bipartite graph data structure for internal consistency.

Definition at line 753 of file graph.cpp.

753  {
754  bool RetVal = false;
755  // edge lists are sorted
756  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
757  if (! LeftH[n].NIdV.IsSorted()) {
758  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", LeftH[n].GetId());
759  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
760  }
761  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
762  if (! RightH[n].NIdV.IsSorted()) {
763  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", RightH[n].GetId());
764  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
765  }
766  // nodes only appear on one side
767  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
768  if (RightH.IsKey(LeftH[n].GetId())) {
769  const TStr Msg = TStr::Fmt("'Left' node %d also appears on the 'right'.", LeftH[n].GetId());
770  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
771  }
772  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
773  if (LeftH.IsKey(RightH[n].GetId())) {
774  const TStr Msg = TStr::Fmt("'Right' node %d also appears on the 'left'.", RightH[n].GetId());
775  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
776  }
777  // edges only point from left to right and right to left
778  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
779  for (int e = 0; e < LeftH[n].NIdV.Len(); e++) {
780  if (! RightH.IsKey(LeftH[n].NIdV[e]) || ! RightH.GetDat(LeftH[n].NIdV[e]).NIdV.IsIn(LeftH[n].GetId())) {
781  const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", LeftH[n].GetId(), LeftH[n].NIdV[e]());
782  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
783  }
784  }
785  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
786  for (int e = 0; e < RightH[n].NIdV.Len(); e++) {
787  if (! LeftH.IsKey(RightH[n].NIdV[e]) || ! LeftH.GetDat(RightH[n].NIdV[e]).NIdV.IsIn(RightH[n].GetId())) {
788  const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", RightH[n].GetId(), RightH[n].NIdV[e]());
789  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
790  }
791  }
792  return RetVal;
793 }
TVec::IsIn
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:782
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:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TBPGraph::TNode::NIdV
TIntV NIdV
Definition: graph.h:843
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:946
EAssertR
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 992 of file graph.h.

992 { return RightH.IsKey(NId); }
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
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 965 of file graph.h.

965 { return PBPGraph(new TBPGraph(SIn)); }
TBPGraph::TBPGraph
TBPGraph()
Definition: graph.h:951
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 960 of file graph.h.

960 { return new TBPGraph(); }
TBPGraph::TBPGraph
TBPGraph()
Definition: graph.h:951
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 963 of file graph.h.

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

Definition at line 968 of file graph.h.

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

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

Definition at line 740 of file graph.cpp.

740  {
741  if (Nodes>0) { LeftH.Gen(Nodes/2); RightH.Gen(Nodes/2); }
742 }
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:180
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945
void TBPGraph::Save ( TSOut &  SOut) const
inline

Saves the graph to a (binary) stream SOut.

Definition at line 958 of file graph.h.

958 { MxNId.Save(SOut); LeftH.Save(SOut); RightH.Save(SOut); }
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1058
THash::Save
void Save(TSOut &SOut) const
Definition: hash.h:141
TBPGraph::MxNId
TInt MxNId
Definition: graph.h:944
TBPGraph::RightH
THash< TInt, TNode > RightH
Definition: graph.h:946
TBPGraph::LeftH
THash< TInt, TNode > LeftH
Definition: graph.h:945

Friends And Related Function Documentation

friend class TPt< TBPGraph >
friend

Definition at line 1066 of file graph.h.

Member Data Documentation

TCRef TBPGraph::CRef
private

Definition at line 943 of file graph.h.

THash<TInt, TNode> TBPGraph::LeftH
private

Definition at line 945 of file graph.h.

TInt TBPGraph::MxNId
private

Definition at line 944 of file graph.h.

THash<TInt, TNode> TBPGraph::RightH
private

Definition at line 946 of file graph.h.

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