SNAP Library 2.4, Developer Reference: TBPGraph Class Reference

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

                                                              {
   const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
   const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
   IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
   IAssertR(LeftNId!=RightNId, "No self-edges are allowed."); 
   IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
   const int LNId = IsLL ? LeftNId : RightNId; // the real left node
   const int RNId = IsLL ? RightNId : LeftNId; // the real right node
   if (LeftH.GetDat(LNId).IsOutNId(RNId)) { return -2; } // edge already exists
   LeftH.GetDat(LNId).NIdV.AddSorted(RNId);
   RightH.GetDat(RNId).NIdV.AddSorted(LNId);
   return -1; // edge id
 }

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()); }

TBPGraph::AddEdge

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

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

Definition: graph.cpp:655

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

                                                    {
   if (NId == -1) { NId = MxNId;  MxNId++; }
   else if (IsLNode(NId)) { IAssertR(LeftNode, TStr::Fmt("Node with id %s already exists on the 'left'.", NId));  return NId; }
   else if (IsRNode(NId)) { IAssertR(! LeftNode, TStr::Fmt("Node with id %s already exists on the 'right'.", NId));  return NId; }
   else { MxNId = TMath::Mx(NId+1, MxNId()); }
   if (LeftNode) { LeftH.AddDat(NId, TNode(NId)); }
   else { RightH.AddDat(NId, TNode(NId)); }
   return NId;
 }

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()); }

TBPGraph::AddNode

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()); }

TBPGraph::BegLNI

TNodeI BegLNI() const

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

Definition: graph.h:1003

TBPGraph::EndLNI

TNodeI EndLNI() const

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

Definition: graph.h:1005

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()); }

THash::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:

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()); }

THash::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()); }

THash::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

THash::Clr

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.

                                                {
   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
     LeftH[n].NIdV.Pack(); }
   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
     RightH[n].NIdV.Pack(); }
   if (! OnlyNodeLinks && ! LeftH.IsKeyIdEqKeyN()) { LeftH.Defrag(); }
   if (! OnlyNodeLinks && ! RightH.IsKeyIdEqKeyN()) { RightH.Defrag(); }
 }

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

                                                               {
   const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
   const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
   IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
   IAssertR(LeftNId!=RightNId, "No self-edges are allowed."); 
   IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
   const int LNId = IsLL ? LeftNId : RightNId; // the real left node
   const int RNId = IsLL ? RightNId : LeftNId; // the real right node
   { TIntV& NIdV = LeftH.GetDat(LNId).NIdV;
   const int n = NIdV.SearchBin(RNId);
   if (n != -1) { NIdV.Del(n); } }
   { TIntV& NIdV = RightH.GetDat(RNId).NIdV;
   const int n = NIdV.SearchBin(LNId);
   if (n != -1) { NIdV.Del(n); } }
 }

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

                                      {
   AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
   THash<TInt, TNode>& SrcH = IsLNode(NId) ? LeftH : RightH;
   THash<TInt, TNode>& DstH = IsLNode(NId) ? RightH : LeftH;
   { TNode& Node = SrcH.GetDat(NId);
   for (int e = 0; e < Node.GetOutDeg(); e++) {
     const int nbr = Node.GetOutNId(e);
     IAssertR(nbr != NId, "Bipartite graph has a loop!");
     TNode& N = DstH.GetDat(nbr);
     const int n = N.NIdV.SearchBin(NId);
     IAssert(n!= -1); 
     N.NIdV.Del(n);
   } }
   SrcH.DelKey(NId);
 }

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()); }

TBPGraph::DelNode

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

                                     {
   const int NodePlaces = (int) ceil(log10((double) GetNodes()));
   fprintf(OutF, "-------------------------------------------------\nBipartite Graph: nodes: %d+%d=%d, edges: %d\n", GetLNodes(), GetRNodes(), GetNodes(), GetEdges());
   for (int N = LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
     const TNode& Node = LeftH[N];
     fprintf(OutF, "  %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
     for (int edge = 0; edge < Node.GetDeg(); edge++) {
       fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
     fprintf(OutF, "\n");
   }
   fprintf(OutF, "\n");
   /*// Also dump the 'right' side
   fprintf(OutF, "\n");
   for (int N = RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
     const TNode& Node = RightH[N];
     fprintf(OutF, "  %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
     for (int edge = 0; edge < Node.GetDeg(); edge++) {
       fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
     fprintf(OutF, "\n");
   }
   fprintf(OutF, "\n"); //*/
 }

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; }

TBPGraph::GetNodes

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()); }

TBPGraph::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(); }

TBPGraph::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(); }

TBPGraph::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.

                              {
   int Edges = 0;
   for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
     Edges += LeftH[N].GetDeg(); }
   return Edges;
 }

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.

                                                                             {
   const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
   const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
   IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
   IAssertR(LeftNId!=RightNId, "No self-edges are allowed."); 
   IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
   const int LNId = IsLL ? LeftNId : RightNId; // the real left node
   const int RNId = IsLL ? RightNId : LeftNId; // the real right node
   const TNodeI SrcNI = GetNI(LNId);
   const int NodeN = SrcNI.LeftHI.GetDat().NIdV.SearchBin(RNId);
   IAssertR(NodeN != -1, "Right edge endpoint does not exists!");
   return TEdgeI(SrcNI, EndNI(), NodeN);
 }

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

                                          {
   NIdV.Gen(GetLNodes(), 0);
   for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
     NIdV.Add(LeftH.GetKey(N)); }
 }

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

THash::Len

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)); }

TBPGraph::IsLNode

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

THash::GetI

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

                                         {
   NIdV.Gen(GetNodes(), 0);
   for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
     NIdV.Add(LeftH.GetKey(N)); }
   for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
     NIdV.Add(RightH.GetKey(N)); }
 }

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(); }

TBPGraph::GetLNodes

int GetLNodes() const

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

Definition: graph.h:974

TBPGraph::GetRNodes

int GetRNodes() const

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

Definition: graph.h:976

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.

                                   { 
   return LeftH.GetKey(LeftH.GetRndKeyId(Rnd, 0.8)); 
 }

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)); }

TBPGraph::GetNI

TNodeI GetNI(const int &NId) const

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

Definition: graph.h:1001

TBPGraph::GetRndNId

int GetRndNId(TRnd &Rnd=TInt::Rnd)

Returns an ID of a random node in the graph.

Definition: graph.cpp:704

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

                                  { 
   const int NNodes = GetNodes();
   if (Rnd.GetUniDevInt(NNodes) < GetLNodes()) {
     return GetRndLNId(Rnd); }
   else {
     return GetRndRNId(Rnd); }
 }

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.

                                   { 
   return RightH.GetKey(RightH.GetRndKeyId(Rnd, 0.8)); 
 }

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

                                          {
   NIdV.Gen(GetRNodes(), 0);
   for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
     NIdV.Add(RightH.GetKey(N)); }
 }

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

THash::Len

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

                                  {
   PBPGraph BP = TBPGraph::New();
   BP->AddNode(0, true);
   BP->AddNode(1, true);
   BP->AddNode(2, false);
   BP->AddNode(3, false);
   BP->AddNode(4, false);
   BP->AddEdge(0, 2);
   BP->AddEdge(0, 3);
   BP->AddEdge(1, 2);
   BP->AddEdge(1, 3);
   BP->AddEdge(1, 4);
   return BP;
 }

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

                                                                    {
   if (! IsNode(LeftNId) || ! IsNode(RightNId)) { return false; }
   return IsLNode(LeftNId) ? LeftH.GetDat(LeftNId).IsOutNId(RightNId) : RightH.GetDat(LeftNId).IsOutNId(RightNId);
 }

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

THash::IsKey

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); }

TBPGraph::IsLNode

bool IsLNode(const int &NId) const

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

Definition: graph.h:990

TBPGraph::IsRNode

bool IsRNode(const int &NId) const

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

Definition: graph.h:992

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

                                                  {
   bool RetVal = false;
   // edge lists are sorted
   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
     if (! LeftH[n].NIdV.IsSorted()) {
       const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", LeftH[n].GetId());
       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
   }
   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
     if (! RightH[n].NIdV.IsSorted()) {
       const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", RightH[n].GetId());
       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
   }
   // nodes only appear on one side
   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
     if (RightH.IsKey(LeftH[n].GetId())) {
       const TStr Msg = TStr::Fmt("'Left' node %d also appears on the 'right'.", LeftH[n].GetId());
       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
   } 
   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
     if (LeftH.IsKey(RightH[n].GetId())) {
       const TStr Msg = TStr::Fmt("'Right' node %d also appears on the 'left'.", RightH[n].GetId());
       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
   }
   // edges only point from left to right and right to left
   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
     for (int e = 0; e < LeftH[n].NIdV.Len(); e++) {
       if (! RightH.IsKey(LeftH[n].NIdV[e]) || ! RightH.GetDat(LeftH[n].NIdV[e]).NIdV.IsIn(LeftH[n].GetId())) {
         const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", LeftH[n].GetId(), LeftH[n].NIdV[e]());
         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
     }
   }
   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
     for (int e = 0; e < RightH[n].NIdV.Len(); e++) {
       if (! LeftH.IsKey(RightH[n].NIdV[e]) || ! LeftH.GetDat(RightH[n].NIdV[e]).NIdV.IsIn(RightH[n].GetId())) {
         const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", RightH[n].GetId(), RightH[n].NIdV[e]());
         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
     }
   }
   return RetVal;
 }

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

THash::IsKey

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::TBPGraph

TBPGraph()

Definition: graph.h:951

PBPGraph

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::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::TBPGraph

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

                                                          { 
   if (Nodes>0) { LeftH.Gen(Nodes/2); RightH.Gen(Nodes/2); } 
 }

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); }

TInt::Save

void Save(TSOut &SOut) const

Definition: dt.h:1058

THash::Save

void Save(TSOut &SOut) const

Definition: hash.h:141

TInt MxNId

Definition: graph.h:944

THash< TInt, TNode > RightH

Definition: graph.h:946