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
TUNGraph Class Reference

#include <graph.h>

Collaboration diagram for TUNGraph:

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

typedef TUNGraph TNet
typedef TPt< TUNGraphPNet

Public Member Functions

 TUNGraph ()
 TUNGraph (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
 TUNGraph (const TUNGraph &Graph)
 TUNGraph (TSIn &SIn)
 Constructor that loads 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).
TUNGraphoperator= (const TUNGraph &Graph)
int GetNodes () const
 Returns the number of nodes in the graph.
int AddNode (int NId=-1)
 Adds a node of ID NId to the graph.
int AddNode (const TNodeI &NodeI)
 Adds a node of ID NodeI.GetId() to the graph.
int AddNode (const int &NId, const TIntV &NbrNIdV)
 Adds a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV.
int AddNode (const int &NId, const TVecPool< TInt > &Pool, const int &NIdVId)
 Adds a node of ID NId to the graph and create edges to all nodes in vector NIdVId in the vector pool Pool.
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.
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.
int GetMxNId () const
 Returns the maximum id of a any node in the graph.
int GetEdges () const
 Returns the number of edges in the graph.
int AddEdge (const int &SrcNId, const int &DstNId)
 Adds an edge between node IDs SrcNId and DstNId to the graph.
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
void DelEdge (const int &SrcNId, const int &DstNId)
 Deletes an edge between node IDs SrcNId and DstNId from the graph.
bool IsEdge (const int &SrcNId, const int &DstNId) const
 Tests whether an edge between node IDs SrcNId and DstNId 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 &SrcNId, const int &DstNId) const
 Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random 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 graph.
bool Empty () const
 Tests whether the graph is empty (has zero nodes).
void Clr ()
 Deletes all nodes and edges from the graph.
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a graph of Nodes nodes and Edges edges.
void ReserveNIdDeg (const int &NId, const int &Deg)
 Reserves memory for node ID NId having Deg edges.
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the graph.
bool IsOk (const bool &ThrowExcept=true) const
 Checks the graph data structure for internal consistency.
void Dump (FILE *OutF=stdout) const
 Print the graph in a human readable form to an output stream OutF.

Static Public Member Functions

static PUNGraph New ()
 Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
static PUNGraph 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 PUNGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it.
static PUNGraph GetSmallGraph ()
 Returns a small graph on 5 nodes and 5 edges.

Private Member Functions

TNodeGetNode (const int &NId)
const TNodeGetNode (const int &NId) const

Private Attributes

TCRef CRef
TInt MxNId
TInt NEdges
THash< TInt, TNodeNodeH

Friends

class TUNGraphMtx
class TPt< TUNGraph >

Detailed Description

Undirected graph. Node IDs can be arbitrary non-negative integers. Nodes and edges have no attributes/data associated with them. There is at most one undirected edge between a pair of nodes. Self loops (one per node) are allowed but multiple (parallel) edges are not. The undirected graph data structure is implemented using sorted adjacency lists. This means adding a node takes constant time, while adding an edge takes linear time (since adjacency list is kept sorted) in the node degree. Accessing arbitrary node takes constant time and accessing any edge takes logarithmic time in the node degree.

Definition at line 31 of file graph.h.


Member Typedef Documentation

Definition at line 34 of file graph.h.

Definition at line 33 of file graph.h.


Constructor & Destructor Documentation

TUNGraph::TUNGraph ( ) [inline]

Definition at line 139 of file graph.h.

Referenced by Load(), and New().

: CRef(), MxNId(0), NEdges(0), NodeH() { }

Here is the caller graph for this function:

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

Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.

Definition at line 141 of file graph.h.

References Reserve().

: MxNId(0), NEdges(0) { Reserve(Nodes, Edges); }

Here is the call graph for this function:

TUNGraph::TUNGraph ( const TUNGraph Graph) [inline]

Definition at line 142 of file graph.h.

: MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH) { }
TUNGraph::TUNGraph ( TSIn SIn) [inline]

Constructor that loads the graph from a (binary) stream SIn.

Definition at line 144 of file graph.h.

: MxNId(SIn), NEdges(SIn), NodeH(SIn) { }

Member Function Documentation

int TUNGraph::AddEdge ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge between node IDs SrcNId and DstNId to the graph.

If the edge already exists return -2. If the edge was successfully added return -1. Normally the function should return an ID of the edge added but since edges in TUNGraph have no IDs we return -1. The function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 81 of file graph.cpp.

References TVec< TVal >::AddSorted(), TStr::Fmt(), GetNode(), IAssertR, IsEdge(), IsNode(), NEdges, and TUNGraph::TNode::NIdV.

Referenced by TUndirFFire::AddNodes(), TCliqueOverlap::CalculateOverlapMtx(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), GetSmallGraph(), TSnap::GetSubGraph(), TTimeNENet::GetTriadEdges(), TAGM::RndConnectInsideCommunity(), and TNetConstraint< PGraph >::Test().

                                                          {
  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
  if (IsEdge(SrcNId, DstNId)) { return -2; } // edge already exists
  GetNode(SrcNId).NIdV.AddSorted(DstNId);
  if (SrcNId!=DstNId) { // not a self edge
    GetNode(DstNId).NIdV.AddSorted(SrcNId); }
  NEdges++;
  return -1; // edge id
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::AddEdge ( const TEdgeI EdgeI) [inline]

Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.

Definition at line 217 of file graph.h.

References AddEdge(), TUNGraph::TEdgeI::GetDstNId(), and TUNGraph::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 TUNGraph::AddNode ( int  NId = -1)

Adds a node of ID NId to the graph.

Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.

Definition at line 8 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), IAssertR, IsNode(), TMath::Mx(), MxNId, and NodeH.

Referenced by TUndirFFire::AddNodes(), TCliqueOverlap::CalculateOverlapMtx(), TAGM::GenAGM(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), GetSmallGraph(), TSnap::GetSubGraph(), TTimeNENet::GetTriadEdges(), and TNetConstraint< PGraph >::Test().

                             {
  if (NId == -1) {
    NId = MxNId;  MxNId++;
  } else {
    IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
    MxNId = TMath::Mx(NId+1, MxNId());
  }
  NodeH.AddDat(NId, TNode(NId));
  return NId;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::AddNode ( const TNodeI NodeI) [inline]

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

Definition at line 169 of file graph.h.

References AddNode(), and TUNGraph::TNodeI::GetId().

Referenced by AddNode().

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

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::AddNode ( const int &  NId,
const TIntV NbrNIdV 
)

Adds a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV.

Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.

The operation can create inconsistent graphs when the neighboring nodes in NbrNIdV vector do not exist. Use TUNGraph::IsOk to check that the resulting graph is consistent after the operation.

Definition at line 20 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TUNGraph::TNode::GetDeg(), IAssertR, TUNGraph::TNode::Id, IsNode(), TMath::Mx(), MxNId, NEdges, TUNGraph::TNode::NIdV, NodeH, and TVec< TVal >::Sort().

                                                          {
  int NewNId;
  if (NId == -1) {
    NewNId = MxNId;  MxNId++;
  } else {
    IAssertR(! IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
    NewNId = NId;
    MxNId = TMath::Mx(NewNId+1, MxNId());
  }
  TNode& Node = NodeH.AddDat(NewNId);
  Node.Id = NewNId;
  Node.NIdV = NbrNIdV;
  Node.NIdV.Sort();
  NEdges += Node.GetDeg();
  return NewNId;
}

Here is the call graph for this function:

int TUNGraph::AddNode ( const int &  NId,
const TVecPool< TInt > &  Pool,
const int &  NIdVId 
)

Adds a node of ID NId to the graph and create edges to all nodes in vector NIdVId in the vector pool Pool.

Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.

The operation can create inconsistent graphs when the neighboring nodes stored in the Pool vector are not explicitly added to the graph. Use TUNGraph::IsOk to check that the resulting graph is consistent.

Definition at line 38 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TVec< TVal >::GenExt(), TUNGraph::TNode::GetDeg(), TVecPool< TVal >::GetValVPt(), TVecPool< TVal >::GetVLen(), IAssertR, TUNGraph::TNode::Id, IsNode(), TMath::Mx(), MxNId, NEdges, TUNGraph::TNode::NIdV, NodeH, and TVec< TVal >::Sort().

                                                                                   {
  int NewNId;
  if (NId == -1) {
    NewNId = MxNId;  MxNId++;
  } else {
    IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
    NewNId = NId;
    MxNId = TMath::Mx(NewNId+1, MxNId());
  }
  TNode& Node = NodeH.AddDat(NewNId);
  Node.Id = NewNId;
  Node.NIdV.GenExt(Pool.GetValVPt(NIdVId), Pool.GetVLen(NIdVId));
  Node.NIdV.Sort();
  NEdges += Node.GetDeg();
  return NewNId;
}

Here is the call graph for this function:

TEdgeI TUNGraph::BegEI ( ) const [inline]

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

Definition at line 226 of file graph.h.

References BegNI(), EndNI(), TUNGraph::TNodeI::GetId(), GetNodes(), TUNGraph::TNodeI::GetOutDeg(), and TUNGraph::TNodeI::GetOutNId().

Referenced by IsOk().

{ TNodeI NI = BegNI(); TEdgeI EI(NI, EndNI(), 0); if (GetNodes() != 0 && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { EI++; } return EI; }

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TUNGraph::BegNI ( ) const [inline]

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

Definition at line 200 of file graph.h.

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

Referenced by BegEI(), TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN(), TLocClust::DrawWhiskers(), TCliqueOverlap::GetMaximalCliques(), TSnap::TSnapDetail::TCNMQMatrix::Init(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TTimeNet::PlotMissingPast(), TLocClust::SavePajek(), and TKronMomentsFit::TKronMomentsFit().

{ return TNodeI(NodeH.BegI()); }

Here is the call graph for this function:

Here is the caller graph for this function:

void TUNGraph::Clr ( ) [inline]

Deletes all nodes and edges from the graph.

Definition at line 246 of file graph.h.

References THash< TKey, TDat, THashFunc >::Clr(), MxNId, NEdges, and NodeH.

{ MxNId=0; NEdges=0; NodeH.Clr(); }

Here is the call graph for this function:

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

Defragments the graph.

After performing many node and edge insertions and deletions to a graph, the graph data structure will be fragmented in memory. This function compacts down the graph data structure and frees unneeded memory.

Definition at line 129 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::Defrag(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), THash< TKey, TDat, THashFunc >::IsKeyIdEqKeyN(), NodeH, and THash< TKey, TDat, THashFunc >::Pack().

Referenced by TSnap::GenSmallWorld(), and TTimeNet::PlotMissingPast().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TUNGraph::DelEdge ( const int &  SrcNId,
const int &  DstNId 
)

Deletes an edge between node IDs SrcNId and DstNId from the graph.

If the edge (SrcNId, DstNId) does not exist in the graph function still completes. But the function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 92 of file graph.cpp.

References TVec< TVal >::Del(), TStr::Fmt(), GetNode(), IAssertR, IsNode(), NEdges, TUNGraph::TNode::NIdV, and TVec< TVal >::SearchBin().

Referenced by TSnap::TSnapDetail::CmtyGirvanNewmanStep(), TSnap::GenDegSeq(), and TTimeNet::PlotMissingPast().

                                                           {
  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
  { TNode& N = GetNode(SrcNId);
  const int n = N.NIdV.SearchBin(DstNId);
  if (n!= -1) { N.NIdV.Del(n);  NEdges--; } }
  if (SrcNId != DstNId) { // not a self edge
    TNode& N = GetNode(DstNId);
    const int n = N.NIdV.SearchBin(SrcNId);
    if (n!= -1) { N.NIdV.Del(n); }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TUNGraph::DelNode ( const int &  NId)

Deletes node of ID NId from the graph.

If the node of ID NId does not exist the function aborts.

Definition at line 56 of file graph.cpp.

References AssertR, TVec< TVal >::Del(), THash< TKey, TDat, THashFunc >::DelKey(), TStr::Fmt(), TUNGraph::TNode::GetDeg(), TUNGraph::TNode::GetNbrNId(), GetNode(), IAssert, IsNode(), NEdges, TUNGraph::TNode::NIdV, NodeH, and TVec< TVal >::SearchBin().

                                     {
  { AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
  TNode& Node = GetNode(NId);
  NEdges -= Node.GetDeg();
  for (int e = 0; e < Node.GetDeg(); e++) {
    const int nbr = Node.GetNbrNId(e);
    if (nbr == NId) { continue; }
    TNode& N = GetNode(nbr);
    const int n = N.NIdV.SearchBin(NId);
    IAssert(n != -1); // if NId points to N, then N also should point back
    if (n!= -1) { N.NIdV.Del(n); }
  } }
  NodeH.DelKey(NId);
}

Here is the call graph for this function:

void TUNGraph::DelNode ( const TNode NodeI) [inline]

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

Definition at line 196 of file graph.h.

References DelNode(), and TUNGraph::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 TUNGraph::Dump ( FILE *  OutF = stdout) const

Print the graph in a human readable form to an output stream OutF.

Definition at line 176 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TUNGraph::TNode::GetDeg(), GetEdges(), TUNGraph::TNode::GetId(), TUNGraph::TNode::GetNbrNId(), GetNodes(), and NodeH.

                                    {
  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
  fprintf(OutF, "-------------------------------------------------\nUndirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    const TNode& Node = NodeH[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 TUNGraph::Empty ( ) const [inline]

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

Definition at line 244 of file graph.h.

References GetNodes().

{ return GetNodes()==0; }

Here is the call graph for this function:

TEdgeI TUNGraph::EndEI ( ) const [inline]

Returns an iterator referring to the past-the-end edge in the graph.

Definition at line 228 of file graph.h.

References EndNI().

Referenced by IsOk().

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

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TUNGraph::EndNI ( ) const [inline]

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

Definition at line 202 of file graph.h.

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

Referenced by BegEI(), TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN(), TLocClust::DrawWhiskers(), EndEI(), GetEI(), TCliqueOverlap::GetMaximalCliques(), TSnap::TSnapDetail::TCNMQMatrix::Init(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TTimeNet::PlotMissingPast(), TLocClust::SavePajek(), and TKronMomentsFit::TKronMomentsFit().

{ return TNodeI(NodeH.EndI()); }

Here is the call graph for this function:

Here is the caller graph for this function:

TEdgeI TUNGraph::GetEI ( const int &  EId) const

Not supported/implemented!

TUNGraph::TEdgeI TUNGraph::GetEI ( const int &  SrcNId,
const int &  DstNId 
) const

Returns an iterator referring to edge (SrcNId, DstNId) in the graph.

Note that since this is an undirected graph GetEI(SrcNId, DstNId) has the same effect as GetEI(DstNId, SrcNId).

Definition at line 111 of file graph.cpp.

References EndNI(), GetNI(), IAssert, TMath::Mn(), TMath::Mx(), MxNId, and TUNGraph::TNodeI::NodeHI.

                                                                         {
  const int MnNId = TMath::Mn(SrcNId, DstNId);
  const int MxNId = TMath::Mx(SrcNId, DstNId);
  const TNodeI SrcNI = GetNI(MnNId);
  const int NodeN = SrcNI.NodeHI.GetDat().NIdV.SearchBin(MxNId);
  IAssert(NodeN != -1);
  return TEdgeI(SrcNI, EndNI(), NodeN);
}

Here is the call graph for this function:

int TUNGraph::GetMxNId ( ) const [inline]

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

Definition at line 206 of file graph.h.

References MxNId.

{ return MxNId; }
void TUNGraph::GetNIdV ( TIntV NIdV) const

Gets a vector IDs of all nodes in the graph.

Definition at line 122 of file graph.cpp.

References TVec< TVal >::Add(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TVec< TVal >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), GetNodes(), and NodeH.

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

Here is the call graph for this function:

TNode& TUNGraph::GetNode ( const int &  NId) [inline, private]

Definition at line 136 of file graph.h.

References THash< TKey, TDat, THashFunc >::GetDat(), and NodeH.

Referenced by AddEdge(), DelEdge(), DelNode(), IsEdge(), and ReserveNIdDeg().

{ return NodeH.GetDat(NId); }

Here is the call graph for this function:

Here is the caller graph for this function:

const TNode& TUNGraph::GetNode ( const int &  NId) const [inline, private]

Definition at line 137 of file graph.h.

References THash< TKey, TDat, THashFunc >::GetDat(), and NodeH.

{ return NodeH.GetDat(NId); }

Here is the call graph for this function:

TNodeI TUNGraph::GetRndNI ( TRnd Rnd = TInt::Rnd) [inline]

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

Definition at line 239 of file graph.h.

References GetNI(), and GetRndNId().

{ return GetNI(GetRndNId(Rnd)); }

Here is the call graph for this function:

int TUNGraph::GetRndNId ( TRnd Rnd = TInt::Rnd) [inline]

Returns an ID of a random node in the graph.

Definition at line 237 of file graph.h.

References THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::GetRndKeyId(), and NodeH.

Referenced by GetRndNI(), and TLocClustStat::Run().

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

Here is the call graph for this function:

Here is the caller graph for this function:

Returns a small graph on 5 nodes and 5 edges.

  * Graph:   3--0--4
  *            /|
  *           1-2
  * 

Definition at line 190 of file graph.cpp.

References AddEdge(), AddNode(), and New().

                                 {
  PUNGraph Graph = TUNGraph::New();
  for (int i = 0; i < 5; i++) { Graph->AddNode(i); }
  Graph->AddEdge(0,1);  Graph->AddEdge(0,2);
  Graph->AddEdge(0,3);  Graph->AddEdge(0,4);
  Graph->AddEdge(1,2);
  return Graph;
}

Here is the call graph for this function:

bool TUNGraph::HasFlag ( const TGraphFlag Flag) const

Allows for run-time checking the type of the graph (see the TGraphFlag for flags).

Definition at line 3 of file graph.cpp.

References HasGraphFlag.

                                                   {
  return HasGraphFlag(TUNGraph::TNet, Flag);
}
bool TUNGraph::IsEdge ( const int &  SrcNId,
const int &  DstNId 
) const

Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.

Definition at line 105 of file graph.cpp.

References GetNode(), TUNGraph::TNode::IsNbrNId(), and IsNode().

Referenced by AddEdge(), TSnap::GenDegSeq(), and TTimeNENet::GetTriadEdges().

                                                                {
  if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
  return GetNode(SrcNId).IsNbrNId(DstNId);
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool TUNGraph::IsNode ( const int &  NId) const [inline]

Tests whether ID NId is a node.

Definition at line 198 of file graph.h.

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

Referenced by AddEdge(), AddNode(), TUNGraphMtx::CheckNodeIds(), DelEdge(), DelNode(), TLocClust::GetCutStat(), TTimeNENet::GetTriadEdges(), IsEdge(), IsOk(), and TTimeNet::PlotMissingPast().

{ return NodeH.IsKey(NId); }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TUNGraph::IsOk ( const bool &  ThrowExcept = true) const

Checks the graph data structure for internal consistency.

For each node in the graph check that its neighbors are also nodes in the graph.

Definition at line 139 of file graph.cpp.

References BegEI(), TStr::CStr(), EAssertR, EndEI(), ErrNotify(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TUNGraph::TNode::GetDeg(), GetEdges(), TUNGraph::TNode::GetId(), TUNGraph::TNode::GetNbrNId(), IsNode(), TVec< TVal >::IsSorted(), TUNGraph::TNode::NIdV, and NodeH.

                                                 {
  bool RetVal = true;
  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    const TNode& Node = NodeH[N];
    if (! Node.NIdV.IsSorted()) {
      const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", Node.GetId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
      RetVal=false;
    }
    int prevNId = -1;
    for (int e = 0; e < Node.GetDeg(); e++) {
      if (! IsNode(Node.GetNbrNId(e))) {
        const TStr Msg = TStr::Fmt("Edge %d --> %d: node %d does not exist.",
          Node.GetId(), Node.GetNbrNId(e), Node.GetNbrNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
        RetVal=false;
      }
      if (e > 0 && prevNId == Node.GetNbrNId(e)) {
        const TStr Msg = TStr::Fmt("Node %d has duplicate edge %d --> %d.",
          Node.GetId(), Node.GetId(), Node.GetNbrNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
        RetVal=false;
      }
      prevNId = Node.GetNbrNId(e);
    }
  }
  int EdgeCnt = 0;
  for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { EdgeCnt++; }
  if (EdgeCnt != GetEdges()) {
    const TStr Msg = TStr::Fmt("Number of edges counter is corrupted: GetEdges():%d, EdgeCount:%d.", GetEdges(), EdgeCnt);
    if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
    RetVal=false;
  }
  return RetVal;
}

Here is the call graph for this function:

static PUNGraph TUNGraph::Load ( TSIn SIn) [inline, static]

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

Definition at line 154 of file graph.h.

References TUNGraph().

{ return PUNGraph(new TUNGraph(SIn)); }

Here is the call graph for this function:

static PUNGraph TUNGraph::New ( ) [inline, static]

Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().

Definition at line 148 of file graph.h.

References TUNGraph().

Referenced by TCliqueOverlap::CalculateOverlapMtx(), TAGM::GenAGM(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenGeoPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), TSnap::Get1CnCom(), TSnap::Get1CnComSzCnt(), GetSmallGraph(), TSnap::GetSubGraph(), and TNetConstraint< PGraph >::Test().

{ return new TUNGraph(); }

Here is the call graph for this function:

Here is the caller graph for this function:

static PUNGraph TUNGraph::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.

Call: PUNGraph Graph = TUNGraph::New(Nodes, Edges).

Definition at line 152 of file graph.h.

References TUNGraph().

{ return new TUNGraph(Nodes, Edges); }

Here is the call graph for this function:

TUNGraph& TUNGraph::operator= ( const TUNGraph Graph) [inline]

Definition at line 157 of file graph.h.

References MxNId, NEdges, and NodeH.

                                               {
    if (this!=&Graph) { MxNId=Graph.MxNId; NEdges=Graph.NEdges; NodeH=Graph.NodeH; } return *this; }
void TUNGraph::Reserve ( const int &  Nodes,
const int &  Edges 
) [inline]

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

Definition at line 248 of file graph.h.

References THash< TKey, TDat, THashFunc >::Gen(), and NodeH.

Referenced by TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), TSnap::GetSubGraph(), and TUNGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TUNGraph::ReserveNIdDeg ( const int &  NId,
const int &  Deg 
) [inline]

Reserves memory for node ID NId having Deg edges.

Definition at line 250 of file graph.h.

References GetNode(), TUNGraph::TNode::NIdV, and TVec< TVal >::Reserve().

{ GetNode(NId).NIdV.Reserve(Deg); }

Here is the call graph for this function:

void TUNGraph::Save ( TSOut SOut) const [inline]

Saves the graph to a (binary) stream SOut.

Definition at line 146 of file graph.h.

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

{ MxNId.Save(SOut); NEdges.Save(SOut); NodeH.Save(SOut); }

Here is the call graph for this function:


Friends And Related Function Documentation

friend class TPt< TUNGraph > [friend]

Definition at line 273 of file graph.h.

friend class TUNGraphMtx [friend]

Definition at line 272 of file graph.h.


Member Data Documentation

TCRef TUNGraph::CRef [private]

Definition at line 132 of file graph.h.

TInt TUNGraph::MxNId [private]

Definition at line 133 of file graph.h.

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

Definition at line 133 of file graph.h.

Referenced by AddEdge(), AddNode(), Clr(), DelEdge(), DelNode(), GetEdges(), operator=(), and Save().


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