SNAP Library 2.4, Developer 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
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 834 of file graph.h.

Member Typedef Documentation

Definition at line 837 of file graph.h.

Definition at line 836 of file graph.h.

Member Enumeration Documentation

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

Constructor & Destructor Documentation

TBPGraph::TBPGraph ( )
inline

Definition at line 951 of file graph.h.

Referenced by Load(), and New().

951 : CRef(), MxNId(0), LeftH(), RightH() { }
TCRef CRef
Definition: graph.h:943
TInt MxNId
Definition: graph.h:944
THash< TInt, TNode > RightH
Definition: graph.h:946
THash< TInt, TNode > LeftH
Definition: graph.h:945

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

953 : MxNId(0) { }
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) { }
TInt MxNId
Definition: graph.h:944
THash< TInt, TNode > RightH
Definition: graph.h:946
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) { }
TInt MxNId
Definition: graph.h:944
THash< TInt, TNode > RightH
Definition: graph.h:946
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.

References TStr::Fmt(), and IAssertR.

Referenced by TSnap::GenRewire().

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 }
#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:990
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:1027
bool IsOutNId(const int &NId) const
Definition: graph.h:860
TIntV NIdV
Definition: graph.h:843
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:992
THash< TInt, TNode > RightH
Definition: graph.h:946
THash< TInt, TNode > LeftH
Definition: graph.h:945

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

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

Referenced by AddEdge().

1017 { 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:655

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

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

Referenced by TSnap::GenRewire().

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 }
#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:990
TInt MxNId
Definition: graph.h:944
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:992
THash< TInt, TNode > RightH
Definition: graph.h:946
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 981 of file graph.h.

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

Referenced by AddNode().

981 { 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:621

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

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

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

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

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

Referenced by BegEI().

1003 { 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:946
THash< TInt, TNode > LeftH
Definition: graph.h:945

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

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

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

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

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

1007 { 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:946
THash< TInt, TNode > LeftH
Definition: graph.h:945

Here is the call graph for this function:

void TBPGraph::Clr ( )
inline

Deletes all nodes and edges from the bipartite graph.

Definition at line 1051 of file graph.h.

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

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

Here is the call graph for this function:

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 }
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
void Defrag()
Definition: hash.h:509
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
int FFirstKeyId() const
Definition: hash.h:232
THash< TInt, TNode > RightH
Definition: graph.h:946
THash< TInt, TNode > LeftH
Definition: graph.h:945
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.

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

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 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TIntV NIdV
Definition: graph.h:843
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
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:992
THash< TInt, TNode > RightH
Definition: graph.h:946
THash< TInt, TNode > LeftH
Definition: graph.h:945

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 632 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().

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 }
#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:988
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
int GetOutNId(const int &NodeN) const
Definition: graph.h:856
void DelKey(const TKey &Key)
Definition: hash.h:358
TIntV NIdV
Definition: graph.h:843
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash< TInt, TNode > RightH
Definition: graph.h:946
THash< TInt, TNode > LeftH
Definition: graph.h:945
#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 986 of file graph.h.

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

Referenced by DelNode().

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

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

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

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 }
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:974
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:648
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:972
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:976
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
int FFirstKeyId() const
Definition: hash.h:232
THash< TInt, TNode > LeftH
Definition: graph.h:945

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

References GetNodes().

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

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

References EndNI().

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

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

References EndNI().

Referenced by BegEI().

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

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

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

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

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

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

References EndNI().

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

Here is the call graph for this function:

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

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

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 }
#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:1001
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:999
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:992

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

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

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

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

Referenced by GetNodes().

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

References MxNId.

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

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

Referenced by GetRndNI().

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

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

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 }
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:972
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
int FFirstKeyId() const
Definition: hash.h:232
THash< TInt, TNode > RightH
Definition: graph.h:946
THash< TInt, TNode > LeftH
Definition: graph.h:945
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 972 of file graph.h.

References GetLNodes(), and GetRNodes().

Referenced by Empty().

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

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

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

References GetNI(), and GetRndNId().

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

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

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

Referenced by GetRndNI().

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

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

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

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

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

Referenced by GetNodes().

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

References New().

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

References TNEGraph::IsNode().

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

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

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

Referenced by GetNI(), and IsNode().

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

References IsLNode(), and IsRNode().

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

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

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

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 }
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:782
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:432
int FFirstKeyId() const
Definition: hash.h:232
TIntV NIdV
Definition: graph.h:843
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash< TInt, TNode > RightH
Definition: graph.h:946
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
THash< TInt, TNode > LeftH
Definition: graph.h:945
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 992 of file graph.h.

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

Referenced by IsNode().

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

References TBPGraph().

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

References TBPGraph().

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

960 { return new TBPGraph(); }
TBPGraph()
Definition: graph.h:951

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

References TBPGraph().

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

Here is the call graph for this function:

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

Definition at line 968 of file graph.h.

References LeftH, MxNId, and RightH.

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

Referenced by TSnap::GenRewire().

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

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

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

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

Here is the call graph for this function:

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.

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

TInt TBPGraph::MxNId
private

Definition at line 944 of file graph.h.

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

THash<TInt, TNode> TBPGraph::RightH
private

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