SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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 928 of file graph.h.

Member Typedef Documentation

Definition at line 931 of file graph.h.

Definition at line 930 of file graph.h.

Member Enumeration Documentation

Enumerator
bgsUndef 
bgsLeft 
bgsRight 
bgsBoth 

Definition at line 932 of file graph.h.

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

Constructor & Destructor Documentation

TBPGraph::TBPGraph ( )
inline

Definition at line 1045 of file graph.h.

Referenced by Load(), and New().

1045 : CRef(), MxNId(0), LeftH(), RightH() { }
TCRef CRef
Definition: graph.h:1037
TInt MxNId
Definition: graph.h:1038
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1047 of file graph.h.

1047 : MxNId(0) { }
TInt MxNId
Definition: graph.h:1038
TBPGraph::TBPGraph ( const TBPGraph BPGraph)
inline

!! Reserve(Nodes, Edges); }

Definition at line 1048 of file graph.h.

1048 : MxNId(BPGraph.MxNId), LeftH(BPGraph.LeftH), RightH(BPGraph.RightH) { }
TInt MxNId
Definition: graph.h:1038
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039
TBPGraph::TBPGraph ( TSIn SIn)
inline

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

Definition at line 1050 of file graph.h.

1050 : MxNId(SIn), LeftH(SIn), RightH(SIn) { }
TInt MxNId
Definition: graph.h:1038
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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; // no 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:1084
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
bool IsOutNId(const int &NId) const
Definition: graph.h:954
TIntV NIdV
Definition: graph.h:937
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:1086
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1111 of file graph.h.

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

Referenced by AddEdge().

1111 { 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:1084
TInt MxNId
Definition: graph.h:1038
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:1086
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

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 1075 of file graph.h.

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

Referenced by AddNode().

1075 { 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 1118 of file graph.h.

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

1118 { 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:1097
TNodeI EndLNI() const
Returns an iterator referring to the past-the-end 'left' node in the graph.
Definition: graph.h:1099

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 1097 of file graph.h.

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

Referenced by BegEI().

1097 { return TNodeI(LeftH.BegI(), RightH.EndI()); }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1091 of file graph.h.

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

1091 { return TNodeI(LeftH.BegI(), RightH.BegI()); }
TIter BegI() const
Definition: hash.h:213
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1101 of file graph.h.

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

1101 { return TNodeI(LeftH.EndI(), RightH.BegI()); }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

Here is the call graph for this function:

void TBPGraph::Clr ( )
inline

Deletes all nodes and edges from the bipartite graph.

Definition at line 1145 of file graph.h.

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

1145 { MxNId=0; LeftH.Clr(); RightH.Clr(); }
TInt MxNId
Definition: graph.h:1038
THash< TInt, TNode > RightH
Definition: graph.h:1040
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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:233
void Defrag()
Definition: hash.h:555
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039
void Pack()
Definition: hash.h:289
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:1189
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1084
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIntV NIdV
Definition: graph.h:937
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
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:1086
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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:1082
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1084
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
int GetOutNId(const int &NodeN) const
Definition: graph.h:950
void DelKey(const TKey &Key)
Definition: hash.h:404
TIntV NIdV
Definition: graph.h:937
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039
#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 1080 of file graph.h.

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

Referenced by DelNode().

1080 { 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:1068
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:1066
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:1070
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1143 of file graph.h.

References GetNodes().

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

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 1120 of file graph.h.

References EndNI().

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

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 1099 of file graph.h.

References EndNI().

Referenced by BegEI().

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

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 1093 of file graph.h.

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

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

1093 { return TNodeI(LeftH.EndI(), RightH.EndI()); }
TIter EndI() const
Definition: hash.h:218
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1103 of file graph.h.

References EndNI().

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

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:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > LeftH
Definition: graph.h:1039
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:1095
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1084
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:1093
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:1086

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:1068
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > LeftH
Definition: graph.h:1039
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252

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 1068 of file graph.h.

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

Referenced by GetNodes().

1068 { return LeftH.Len(); }
THash< TInt, TNode > LeftH
Definition: graph.h:1039
int Len() const
Definition: hash.h:228

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 1088 of file graph.h.

References MxNId.

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

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

Definition at line 1095 of file graph.h.

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

Referenced by GetRndNI().

1095 { 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:1084
TIter EndI() const
Definition: hash.h:218
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039
TIter GetI(const TKey &Key) const
Definition: hash.h:220

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:1066
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252

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 1066 of file graph.h.

References GetLNodes(), and GetRNodes().

Referenced by Empty().

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

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:1039
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:444
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
TNodeI TBPGraph::GetRndNI ( TRnd Rnd = TInt::Rnd)
inline

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

Definition at line 1134 of file graph.h.

References GetNI(), and GetRndNId().

1134 { 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:1095
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:1068
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:1066
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:1040
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:444
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
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:1070
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > RightH
Definition: graph.h:1040
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252

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 1070 of file graph.h.

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

Referenced by GetNodes().

1070 { return RightH.Len(); }
THash< TInt, TNode > RightH
Definition: graph.h:1040
int Len() const
Definition: hash.h:228

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:1054
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:1082
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1084
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
bool IsOutNId(const int &NId) const
Definition: graph.h:954
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1084 of file graph.h.

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

Referenced by GetNI(), and IsNode().

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

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 1082 of file graph.h.

References IsLNode(), and IsRNode().

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

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:828
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void ErrNotify(const char *NotifyCStr)
Definition: bd.h:74
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
TIntV NIdV
Definition: graph.h:937
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash< TInt, TNode > RightH
Definition: graph.h:1040
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
THash< TInt, TNode > LeftH
Definition: graph.h:1039
char * CStr()
Definition: dt.h:476
bool IsKey(const TKey &Key) const
Definition: hash.h:258
int Len() const
Definition: hash.h:228

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 1086 of file graph.h.

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

Referenced by IsNode().

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

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 1059 of file graph.h.

References TBPGraph().

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

References TBPGraph().

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

1054 { return new TBPGraph(); }
TBPGraph()
Definition: graph.h:1045

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 1057 of file graph.h.

References TBPGraph().

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

Here is the call graph for this function:

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

Definition at line 1062 of file graph.h.

References LeftH, MxNId, and RightH.

1062  {
1063  if (this!=&BPGraph) { MxNId=BPGraph.MxNId; LeftH=BPGraph.LeftH; RightH=BPGraph.RightH; } return *this; }
TInt MxNId
Definition: graph.h:1038
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039
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:222
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

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 1052 of file graph.h.

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

1052 { MxNId.Save(SOut); LeftH.Save(SOut); RightH.Save(SOut); }
void Save(TSOut &SOut) const
Definition: dt.h:1150
void Save(TSOut &SOut) const
Definition: hash.h:183
TInt MxNId
Definition: graph.h:1038
THash< TInt, TNode > RightH
Definition: graph.h:1040
THash< TInt, TNode > LeftH
Definition: graph.h:1039

Here is the call graph for this function:

Friends And Related Function Documentation

friend class TPt< TBPGraph >
friend

Definition at line 1160 of file graph.h.

Member Data Documentation

TCRef TBPGraph::CRef
private

Definition at line 1037 of file graph.h.

THash<TInt, TNode> TBPGraph::LeftH
private

Definition at line 1039 of file graph.h.

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

TInt TBPGraph::MxNId
private

Definition at line 1038 of file graph.h.

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

THash<TInt, TNode> TBPGraph::RightH
private

Definition at line 1040 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: