SNAP Library 3.0, Developer 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
TBPGraph Class Reference

Bipartite graph. More...

#include <graph.h>

Collaboration diagram for TBPGraph:

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< TBPGraphPNet
 

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...
 
TBPGraphoperator= (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, TNodeLeftH
 
THash< TInt, TNodeRightH
 

Friends

class TPt< TBPGraph >
 

Detailed Description

Bipartite graph.

Definition at line 856 of file graph.h.

Member Typedef Documentation

Definition at line 859 of file graph.h.

Definition at line 858 of file graph.h.

Member Enumeration Documentation

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
TNodeTy
Definition: graph.h:860

Constructor & Destructor Documentation

TBPGraph::TBPGraph ( )
inline

Definition at line 973 of file graph.h.

Referenced by Load(), and New().

973 : CRef(), MxNId(0), LeftH(), RightH() { }
TCRef CRef
Definition: graph.h:965
TInt MxNId
Definition: graph.h:966
THash< TInt, TNode > RightH
Definition: graph.h:968
THash< TInt, TNode > LeftH
Definition: graph.h:967

Here is the caller graph for this function:

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) { }
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) { }
TInt MxNId
Definition: graph.h:966
THash< TInt, TNode > RightH
Definition: graph.h:968
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) { }
TInt MxNId
Definition: graph.h:966
THash< TInt, TNode > RightH
Definition: graph.h:968
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.

References TStr::Fmt(), and IAssertR.

Referenced by TSnap::GenRewire().

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 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1063
bool IsOutNId(const int &NId) const
Definition: graph.h:882
TIntV NIdV
Definition: graph.h:865
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
THash< TInt, TNode > RightH
Definition: graph.h:968
THash< TInt, TNode > LeftH
Definition: graph.h:967

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References AddEdge(), TBPGraph::TEdgeI::GetDstNId(), and TBPGraph::TEdgeI::GetSrcNId().

Referenced by AddEdge().

1039 { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References TStr::Fmt(), IAssertR, TMath::Mx(), and TNEGraph::MxNId.

Referenced by TSnap::GenRewire().

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 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
TInt MxNId
Definition: graph.h:966
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
THash< TInt, TNode > RightH
Definition: graph.h:968
THash< TInt, TNode > LeftH
Definition: graph.h:967
TDat & AddDat(const TKey &Key)
Definition: hash.h:196

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References AddNode(), TBPGraph::TNodeI::GetId(), and TBPGraph::TNodeI::IsLeft().

Referenced by AddNode().

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

Here is the call graph for this function:

Here is the caller graph for this function:

TEdgeI TBPGraph::BegEI ( ) const
inline

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

Definition at line 1046 of file graph.h.

References BegLNI(), EndLNI(), TBPGraph::TNodeI::GetId(), TBPGraph::TNodeI::GetOutDeg(), and TBPGraph::TNodeI::GetOutNId().

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

Here is the call graph for this function:

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.

References THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), LeftH, and RightH.

Referenced by BegEI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TBPGraph::BegNI ( ) const
inline

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

Definition at line 1019 of file graph.h.

References THash< TKey, TDat, THashFunc >::BegI(), LeftH, and RightH.

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

Here is the call graph for this function:

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.

References THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), LeftH, and RightH.

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

Here is the call graph for this function:

void TBPGraph::Clr ( )
inline

Deletes all nodes and edges from the bipartite graph.

Definition at line 1073 of file graph.h.

References THash< TKey, TDat, THashFunc >::Clr(), LeftH, MxNId, and RightH.

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

Here is the call graph for this function:

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 }
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
void Defrag()
Definition: hash.h:513
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
int FFirstKeyId() const
Definition: hash.h:236
THash< TInt, TNode > RightH
Definition: graph.h:968
THash< TInt, TNode > LeftH
Definition: graph.h:967
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.

References TVec< TVal, TSizeTy >::Del(), TStr::Fmt(), TVec< TVal, TSizeTy >::GetDat(), IAssertR, and TVec< TVal, TSizeTy >::SearchBin().

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 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1130
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TIntV NIdV
Definition: graph.h:865
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1454
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014
THash< TInt, TNode > RightH
Definition: graph.h:968
THash< TInt, TNode > LeftH
Definition: graph.h:967

Here is the call graph for this function:

void TBPGraph::DelNode ( const int &  NId)

Deletes node of ID NId from the graph.

Definition at line 682 of file graph.cpp.

References AssertR, TVec< TVal, TSizeTy >::Del(), THash< TKey, TDat, THashFunc >::DelKey(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::GetDat(), TBPGraph::TNode::GetOutDeg(), TBPGraph::TNode::GetOutNId(), IAssert, IAssertR, TNEGraph::IsNode(), TBPGraph::TNode::NIdV, and TVec< TVal, TSizeTy >::SearchBin().

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 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:1010
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
int GetOutNId(const int &NodeN) const
Definition: graph.h:878
void DelKey(const TKey &Key)
Definition: hash.h:362
TIntV NIdV
Definition: graph.h:865
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1454
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash< TInt, TNode > RightH
Definition: graph.h:968
THash< TInt, TNode > LeftH
Definition: graph.h:967
#define AssertR(Cond, Reason)
Definition: bd.h:258

Here is the call graph for this function:

void TBPGraph::DelNode ( const TNode NodeI)
inline

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

Definition at line 1008 of file graph.h.

References DelNode(), and TBPGraph::TNode::GetId().

Referenced by DelNode().

1008 { DelNode(NodeI.GetId()); }
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:682

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References edge, TBPGraph::TNode::GetDeg(), TNEGraph::GetEdges(), TBPGraph::TNode::GetId(), TBPGraph::TNode::GetNbrNId(), and TNEGraph::GetNodes().

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 }
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:996
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:698
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:994
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:998
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
int FFirstKeyId() const
Definition: hash.h:236
THash< TInt, TNode > LeftH
Definition: graph.h:967

Here is the call graph for this function:

bool TBPGraph::Empty ( ) const
inline

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

Definition at line 1071 of file graph.h.

References GetNodes().

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

Here is the call graph for this function:

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.

References EndNI().

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

Here is the call graph for this function:

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.

References EndNI().

Referenced by BegEI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References THash< TKey, TDat, THashFunc >::EndI(), LeftH, and RightH.

Referenced by EndEI(), EndLNI(), and EndRNI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References EndNI().

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

Here is the call graph for this function:

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 }
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
int FFirstKeyId() const
Definition: hash.h:236
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.

References TNEGraph::EndNI(), TStr::Fmt(), TNEGraph::GetNI(), IAssertR, and TBPGraph::TNodeI::LeftHI.

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 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:1023
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1012
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:1021
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1014

Here is the call graph for this function:

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.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Gen().

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

Here is the call graph for this function:

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.

References LeftH, and THash< TKey, TDat, THashFunc >::Len().

Referenced by GetNodes().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References MxNId.

1016 { return 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.

References THash< TKey, TDat, THashFunc >::EndI(), THash< TKey, TDat, THashFunc >::GetI(), IsLNode(), LeftH, and RightH.

Referenced by GetRndNI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), and TNEGraph::GetNodes().

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 }
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:994
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
int FFirstKeyId() const
Definition: hash.h:236
THash< TInt, TNode > RightH
Definition: graph.h:968
THash< TInt, TNode > LeftH
Definition: graph.h:967
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210

Here is the call graph for this function:

int TBPGraph::GetNodes ( ) const
inline

Returns the total number of nodes in the graph.

Definition at line 994 of file graph.h.

References GetLNodes(), and GetRNodes().

Referenced by Empty().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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 }
THash< TInt, TNode > LeftH
Definition: graph.h:967
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
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.

References GetNI(), and GetRndNId().

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

Here is the call graph for this function:

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.

References TNEGraph::GetNodes(), and TRnd::GetUniDevInt().

Referenced by GetRndNI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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 }
THash< TInt, TNode > RightH
Definition: graph.h:968
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
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.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Gen().

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

Here is the call graph for this function:

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.

References THash< TKey, TDat, THashFunc >::Len(), and RightH.

Referenced by GetNodes().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References New().

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 }
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:982
Definition: bd.h:196

Here is the call graph for this function:

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.

References TNEGraph::IsNode().

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

Here is the call graph for this function:

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.

References THash< TKey, TDat, THashFunc >::IsKey(), and LeftH.

Referenced by GetNI(), and IsNode().

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

Here is the call graph for this function:

Here is the caller graph for this function:

bool TBPGraph::IsNode ( const int &  NId) const
inline

Tests whether ID NId is a node.

Definition at line 1010 of file graph.h.

References IsLNode(), and IsRNode().

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

Here is the call graph for this function:

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.

References TStr::CStr(), EAssertR, ErrNotify(), and TStr::Fmt().

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 }
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:797
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
void ErrNotify(const char *NotifyCStr)
Definition: bd.h:74
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
int FFirstKeyId() const
Definition: hash.h:236
TIntV NIdV
Definition: graph.h:865
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash< TInt, TNode > RightH
Definition: graph.h:968
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
THash< TInt, TNode > LeftH
Definition: graph.h:967
char * CStr()
Definition: dt.h:476
bool IsKey(const TKey &Key) const
Definition: hash.h:216
int Len() const
Definition: hash.h:186

Here is the call graph for this function:

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.

References THash< TKey, TDat, THashFunc >::IsKey(), and RightH.

Referenced by IsNode().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References TBPGraph().

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

Here is the call graph for this function:

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.

References TBPGraph().

Referenced by TSnap::GenRewire(), TSnap::GenRndBipart(), and GetSmallGraph().

982 { return new TBPGraph(); }
TBPGraph()
Definition: graph.h:973

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References TBPGraph().

985 { return new TBPGraph(Nodes, Edges); }
TBPGraph()
Definition: graph.h:973

Here is the call graph for this function:

TBPGraph& TBPGraph::operator= ( const TBPGraph BPGraph)
inline

Definition at line 990 of file graph.h.

References LeftH, MxNId, and RightH.

990  {
991  if (this!=&BPGraph) { MxNId=BPGraph.MxNId; LeftH=BPGraph.LeftH; RightH=BPGraph.RightH; } return *this; }
TInt MxNId
Definition: graph.h:966
THash< TInt, TNode > RightH
Definition: graph.h:968
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.

Referenced by TSnap::GenRewire().

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

Here is the caller graph for this function:

void TBPGraph::Save ( TSOut SOut) const
inline

Saves the graph to a (binary) stream SOut.

Definition at line 980 of file graph.h.

References LeftH, MxNId, RightH, THash< TKey, TDat, THashFunc >::Save(), and TInt::Save().

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

Here is the call graph for this function:

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.

Referenced by BegLNI(), BegNI(), BegRNI(), Clr(), EndNI(), GetLNodes(), GetNI(), IsLNode(), operator=(), and Save().

TInt TBPGraph::MxNId
private

Definition at line 966 of file graph.h.

Referenced by Clr(), GetMxNId(), operator=(), and Save().

THash<TInt, TNode> TBPGraph::RightH
private

Definition at line 968 of file graph.h.

Referenced by BegLNI(), BegNI(), BegRNI(), Clr(), EndNI(), GetNI(), GetRNodes(), IsRNode(), operator=(), and Save().


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