SNAP Library , Developer Reference  2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Types | Public Member Functions | Static Public Member Functions | Private Attributes | Friends
TBPGraph Class Reference

#include <graph.h>

Collaboration diagram for TBPGraph:
Collaboration graph
[legend]

List of all members.

Classes

class  TEdgeI
 Edge iterator. Only forward iteration (operator++) is supported. More...
class  TNode
class  TNodeI
 Node iterator. Only forward iteration (operator++) is supported. More...

Public Types

enum  TNodeTy { bgsUndef, bgsLeft, bgsRight, bgsBoth }
typedef TBPGraph TNet
typedef TPt< TBPGraph > PNet

Public Member Functions

 TBPGraph ()
 TBPGraph (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a graph of Nodes (LeftNodes+RightNodes) nodes and Edges edges.
 TBPGraph (const TBPGraph &BPGraph)
 !! Reserve(Nodes, Edges); }
 TBPGraph (TSIn &SIn)
 Constructor for loading the graph from a (binary) stream SIn.
void Save (TSOut &SOut) const
 Saves the graph to a (binary) stream SOut.
bool HasFlag (const TGraphFlag &Flag) const
 Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
TBPGraph & operator= (const TBPGraph &BPGraph)
int GetNodes () const
 Returns the total number of nodes in the graph.
int GetLNodes () const
 Returns the number of nodes on the 'left' side of the biparite graph.
int GetRNodes () const
 Returns the number of nodes on the 'right' side of the biparite graph.
int AddNode (int NId=-1, const bool &LeftNode=true)
 Adds a node of ID NId to the graph.
int AddNode (const TNodeI &NodeI)
 Adds a node of ID NodeI.GetId() to the graph.
void DelNode (const int &NId)
 Deletes node of ID NId from the graph.
void DelNode (const TNode &NodeI)
 Deletes node of ID NodeI.GetId() from the graph.
bool IsNode (const int &NId) const
 Tests whether ID NId is a node.
bool IsLNode (const int &NId) const
 Tests whether ID NId is a 'left' side node.
bool IsRNode (const int &NId) const
 Tests whether ID NId is a 'right' side node.
int GetMxNId () const
 Returns the maximum id of a any node in the graph.
TNodeI BegNI () const
 Returns an iterator referring to the first node in the graph.
TNodeI EndNI () const
 Returns an iterator referring to the past-the-end node in the graph.
TNodeI GetNI (const int &NId) const
 Returns an iterator referring to the node of ID NId in the graph.
TNodeI BegLNI () const
 Returns an iterator referring to the first 'left' node in the graph.
TNodeI EndLNI () const
 Returns an iterator referring to the past-the-end 'left' node in the graph.
TNodeI BegRNI () const
 Returns an iterator referring to the first 'right' node in the graph.
TNodeI EndRNI () const
 Returns an iterator referring to the past-the-end 'right' node in the graph.
int GetEdges () const
 Returns the number of edges in the graph.
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.
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge between EdgeI.GetLNId() and EdgeI.GetRNId() to the graph.
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.
bool IsEdge (const int &LeftNId, const int &RightNId) const
 Tests whether an edge between node IDs LeftNId and RightNId exists in the graph.
TEdgeI BegEI () const
 Returns an iterator referring to the first edge in the graph.
TEdgeI EndEI () const
 Returns an iterator referring to the past-the-end edge in the graph.
TEdgeI GetEI (const int &EId) const
 Not supported/implemented!
TEdgeI GetEI (const int &LeftNId, const int &RightNId) const
 Returns an iterator referring to edge (LeftNId, RightNId) in the graph.
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random node in the graph.
int GetRndLNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random 'left' node in the graph.
int GetRndRNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random 'right' node in the graph.
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random node in the graph.
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the bipartite graph.
void GetLNIdV (TIntV &NIdV) const
 Gets a vector IDs of all 'left' nodes in the bipartite graph.
void GetRNIdV (TIntV &NIdV) const
 Gets a vector IDs of all 'right' nodes in the bipartite graph.
bool Empty () const
 Tests whether the bipartite graph is empty (has zero nodes).
void Clr ()
 Deletes all nodes and edges from the bipartite graph.
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a biparite graph of Nodes nodes and Edges edges.
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the biparite graph.
bool IsOk (const bool &ThrowExcept=true) const
 Checks the bipartite graph data structure for internal consistency.
void Dump (FILE *OutF=stdout) const
 Print the biparite graph in a human readable form to an output stream OutF.

Static Public Member Functions

static PBPGraph New ()
 Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
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.
static PBPGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it.
static PBPGraph GetSmallGraph ()
 Returns a small graph on 2 'left', 3 'right' nodes and 4 edges.

Private Attributes

TCRef CRef
TInt MxNId
THash< TInt, TNode > LeftH
THash< TInt, TNode > RightH

Friends

class TPt< TBPGraph >

Detailed Description

Bipartite graph.

Definition at line 819 of file graph.h.

Member Typedef Documentation

typedef TPt<TBPGraph> TBPGraph::PNet

Definition at line 822 of file graph.h.

typedef TBPGraph TBPGraph::TNet

Definition at line 821 of file graph.h.

Member Enumeration Documentation

enum TBPGraph::TNodeTy
Enumerator:
bgsUndef 
bgsLeft 
bgsRight 
bgsBoth 

Definition at line 823 of file graph.h.

{ bgsUndef, bgsLeft, bgsRight, bgsBoth } TNodeTy; // left or right hand side node

Constructor & Destructor Documentation

TBPGraph::TBPGraph ( ) [inline]

Definition at line 936 of file graph.h.

Referenced by Load(), and New().

: CRef(), MxNId(0), LeftH(), RightH() { }

Here is the caller graph for this function:

TBPGraph::TBPGraph ( const int &  Nodes,
const int &  Edges 
) [inline, explicit]

Constructor that reserves enough memory for a graph of Nodes (LeftNodes+RightNodes) nodes and Edges edges.

Definition at line 938 of file graph.h.

: MxNId(0) { }
TBPGraph::TBPGraph ( const TBPGraph &  BPGraph) [inline]

!! Reserve(Nodes, Edges); }

Definition at line 939 of file graph.h.

: MxNId(BPGraph.MxNId), LeftH(BPGraph.LeftH), RightH(BPGraph.RightH) { }
TBPGraph::TBPGraph ( TSIn &  SIn) [inline]

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

Definition at line 941 of file graph.h.

: MxNId(SIn), LeftH(SIn), RightH(SIn) { }

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

References TStr::Fmt(), and IAssertR.

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

int TBPGraph::AddEdge ( const TEdgeI &  EdgeI) [inline]

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

Definition at line 1002 of file graph.h.

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

Referenced by AddEdge().

{ return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }

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

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

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

int TBPGraph::AddNode ( const TNodeI &  NodeI) [inline]

Adds a node of ID NodeI.GetId() to the graph.

Definition at line 966 of file graph.h.

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

Referenced by AddNode().

{ return AddNode(NodeI.GetId(), NodeI.IsLeft()); }

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

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

{ TNodeI NI=BegLNI(); while (NI<EndLNI() && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { NI++; } return TEdgeI(NI, EndLNI()); }

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

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

Referenced by BegEI().

{ return TNodeI(LeftH.BegI(), RightH.EndI()); }

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

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

{ return TNodeI(LeftH.BegI(), RightH.BegI()); }

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

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

{ return TNodeI(LeftH.EndI(), RightH.BegI()); }

Here is the call graph for this function:

void TBPGraph::Clr ( ) [inline]

Deletes all nodes and edges from the bipartite graph.

Definition at line 1036 of file graph.h.

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

{ MxNId=0; LeftH.Clr(); RightH.Clr(); }

Here is the call graph for this function:

void TBPGraph::Defrag ( const bool &  OnlyNodeLinks = false)

Defragments the biparite graph.

Definition at line 733 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 658 of file graph.cpp.

References TVec< TVal >::Del(), TStr::Fmt(), TVec< TVal >::GetDat(), IAssertR, and TVec< TVal >::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 621 of file graph.cpp.

References AssertR, TVec< TVal >::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 >::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 971 of file graph.h.

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

Referenced by DelNode().

{ DelNode(NodeI.GetId()); }

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

References GetNodes().

{ return GetNodes()==0; }

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

References EndNI().

{ return TEdgeI(EndNI(), EndNI()); }

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

References EndNI().

Referenced by BegEI().

{ return EndNI(); }

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

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

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

{ return TNodeI(LeftH.EndI(), RightH.EndI()); }

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

References EndNI().

{ return EndNI(); }

Here is the call graph for this function:

int TBPGraph::GetEdges ( ) const

Returns the number of edges in the graph.

Definition at line 637 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 679 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 717 of file graph.cpp.

References TVec< TVal >::Add(), and TVec< TVal >::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 959 of file graph.h.

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

Referenced by GetNodes().

{ return LeftH.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

int TBPGraph::GetMxNId ( ) const [inline]

Returns the maximum id of a any node in the graph.

Definition at line 979 of file graph.h.

References MxNId.

{ return MxNId; }
TNodeI TBPGraph::GetNI ( const int &  NId) const [inline]

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

Definition at line 986 of file graph.h.

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

Referenced by GetRndNI().

{ return IsLNode(NId) ? TNodeI(LeftH.GetI(NId), RightH.EndI()) : TNodeI(LeftH.EndI(), RightH.GetI(NId)); }

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

References TVec< TVal >::Add(), TVec< TVal >::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 957 of file graph.h.

References GetLNodes(), and GetRNodes().

Referenced by Empty().

{ return GetLNodes() + GetRNodes(); }

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

References GetNI(), and GetRndNId().

{ return GetNI(GetRndNId(Rnd)); }

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 693 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 705 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 723 of file graph.cpp.

References TVec< TVal >::Add(), and TVec< TVal >::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 961 of file graph.h.

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

Referenced by GetNodes().

{ return RightH.Len(); }

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

References TNEGraph::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 674 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 975 of file graph.h.

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

Referenced by GetNI(), and IsNode().

{ return LeftH.IsKey(NId); }

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

References IsLNode(), and IsRNode().

{ return IsLNode(NId) || IsRNode(NId); }

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

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

Referenced by IsNode().

{ return RightH.IsKey(NId); }

Here is the call graph for this function:

Here is the caller graph for this function:

static PBPGraph TBPGraph::Load ( TSIn &  SIn) [inline, static]

Static constructor that loads the graph from a stream SIn and returns a pointer to it.

Definition at line 950 of file graph.h.

References TBPGraph().

{ return PBPGraph(new TBPGraph(SIn)); }

Here is the call graph for this function:

static PBPGraph TBPGraph::New ( ) [inline, static]

Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.

Definition at line 945 of file graph.h.

References TBPGraph().

Referenced by TSnap::GenRndBipart().

{ return new TBPGraph(); }

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 
) [inline, static]

Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges.

Definition at line 948 of file graph.h.

References TBPGraph().

{ return new TBPGraph(Nodes, Edges); }

Here is the call graph for this function:

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

Definition at line 953 of file graph.h.

References LeftH, MxNId, and RightH.

                                                 {
    if (this!=&BPGraph) { MxNId=BPGraph.MxNId; LeftH=BPGraph.LeftH; RightH=BPGraph.RightH; }  return *this; }
void TBPGraph::Reserve ( const int &  Nodes,
const int &  Edges 
)

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

Definition at line 729 of file graph.cpp.

                                                         { 
  if (Nodes>0) { LeftH.Gen(Nodes/2); RightH.Gen(Nodes/2); } 
}
void TBPGraph::Save ( TSOut &  SOut) const [inline]

Saves the graph to a (binary) stream SOut.

Definition at line 943 of file graph.h.

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

{ MxNId.Save(SOut); LeftH.Save(SOut); RightH.Save(SOut); }

Here is the call graph for this function:

Friends And Related Function Documentation

friend class TPt< TBPGraph > [friend]

Definition at line 1051 of file graph.h.

Member Data Documentation

TCRef TBPGraph::CRef [private]

Definition at line 928 of file graph.h.

THash<TInt, TNode> TBPGraph::LeftH [private]

Definition at line 930 of file graph.h.

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

TInt TBPGraph::MxNId [private]

Definition at line 929 of file graph.h.

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

THash<TInt, TNode> TBPGraph::RightH [private]

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