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

Directed graph. More...

#include <graph.h>

Collaboration diagram for TNGraph:

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 TNGraph TNet
typedef TPt< TNGraphPNet

Public Member Functions

 TNGraph ()
 TNGraph (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
 TNGraph (const TNGraph &Graph)
 TNGraph (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).
TNGraphoperator= (const TNGraph &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 &NodeId)
 Adds a node of ID NodeI.GetId() to the graph.
int AddNode (const int &NId, const TIntV &InNIdV, const TIntV &OutNIdV)
 Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV, creates edges from the node to all nodes in vector OutNIdV.
int AddNode (const int &NId, const TVecPool< TInt > &Pool, const int &SrcVId, const int &DstVId)
 Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV in the vector pool Pool, creates edges from the node to all nodes in vector OutNIdVin 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 from node IDs SrcNId to node DstNId to the graph.
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph.
void DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true)
 Deletes an edge from node IDs SrcNId to DstNId from the graph.
bool IsEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
 Tests whether an edge from node IDs SrcNId to 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 ReserveNIdInDeg (const int &NId, const int &InDeg)
 Reserves memory for node ID NId having InDeg in-edges.
void ReserveNIdOutDeg (const int &NId, const int &OutDeg)
 Reserves memory for node ID NId having OutDeg out-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 PNGraph New ()
 Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
static PNGraph 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 PNGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it.
static PNGraph GetSmallGraph ()
 Returns a small graph on 5 nodes and 6 edges.

Private Member Functions

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

Private Attributes

TCRef CRef
TInt MxNId
THash< TInt, TNodeNodeH

Friends

class TPt< TNGraph >
class TNGraphMtx

Detailed Description

Directed graph.

Node IDs can be arbitrary non-negative integers. Nodes and edges have no attributes/data associated with them. There is at most one directed edge from one source node to a destination node. There can be an edge between the same pair of nodes in the opposite direction. Self loops (one per node) are allowed but multiple (parallel) edges are not. The directed 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 294 of file graph.h.


Member Typedef Documentation

Definition at line 297 of file graph.h.

Definition at line 296 of file graph.h.


Constructor & Destructor Documentation

TNGraph::TNGraph ( ) [inline]

Definition at line 397 of file graph.h.

Referenced by Load(), and New().

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

Here is the caller graph for this function:

TNGraph::TNGraph ( 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 399 of file graph.h.

References Reserve().

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

Here is the call graph for this function:

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

Definition at line 400 of file graph.h.

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

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

Definition at line 402 of file graph.h.

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

Member Function Documentation

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

Adds an edge from node IDs SrcNId to node 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 TNGraph have no IDs we return -1. Function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 283 of file graph.cpp.

References TVec< TVal >::AddSorted(), TStr::Fmt(), GetNode(), IAssertR, TNGraph::TNode::InNIdV, IsEdge(), IsNode(), and TNGraph::TNode::OutNIdV.

Referenced by TFfGGen::AddNodes(), TKronNoise::FlipEdgeNoise(), TMAGParam< TNodeAttr >::GenAttrMAG(), TSnap::GenCopyModel(), TKronMtx::GenDetKronecker(), TKronMtx::GenFastKronecker(), TKronMtx::GenKronecker(), TSnap::GenRMat(), TKronMtx::GenRndGraph(), TKronMtx::GenThreshGraph(), TSnap::GetBfsTree(), TGraphEnumUtils::GetGraph(), TNIBs::GetGroundTruthGraphAtT(), TGraphEnumUtils::GetIndGraph(), TNIBs::GetInferredGraphAtT(), TGraphKey::GetNGraph(), TGraphEnumUtils::GetNormalizedGraph(), GetSmallGraph(), TBigNet< TNodeData, IsDir >::GetSubNGraph(), TNetInfBs::GreedyOpt(), TSnap::LoadDyNet(), TSnap::LoadDyNetGraphV(), TNetInfBs::LoadGroundTruthTxt(), main(), and TKroneckerLL::SetRandomEdges().

                                                         {
  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
  //IAssert(! IsEdge(SrcNId, DstNId));
  if (IsEdge(SrcNId, DstNId)) { return -2; }
  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
  return -1; // edge id
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 479 of file graph.h.

References AddEdge(), TNGraph::TEdgeI::GetDstNId(), and TNGraph::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 TNGraph::AddNode ( int  NId = -1)
int TNGraph::AddNode ( const TNodeI NodeId) [inline]

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

Definition at line 427 of file graph.h.

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

Referenced by AddNode().

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

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraph::AddNode ( const int &  NId,
const TIntV InNIdV,
const TIntV OutNIdV 
)

Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV, creates edges from the node to all nodes in vector OutNIdV.

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 vectors InNIdV and OutNIdV do not exist. Use TNGraph::IsOk to check that the resulting graph is consistent after the operation.

Definition at line 218 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), IAssertR, TNGraph::TNode::Id, TNGraph::TNode::InNIdV, IsNode(), TMath::Mx(), MxNId, NodeH, TNGraph::TNode::OutNIdV, 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.InNIdV = InNIdV;
  Node.OutNIdV = OutNIdV;
  Node.InNIdV.Sort();
  Node.OutNIdV.Sort();
  return NewNId;
}

Here is the call graph for this function:

int TNGraph::AddNode ( const int &  NId,
const TVecPool< TInt > &  Pool,
const int &  SrcVId,
const int &  DstVId 
)

Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV in the vector pool Pool, creates edges from the node to all nodes in vector OutNIdVin 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 TNGraph::IsOk to check that the resulting graph is consistent.

Definition at line 238 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TVec< TVal >::GenExt(), TVecPool< TVal >::GetValVPt(), TVecPool< TVal >::GetVLen(), IAssertR, TNGraph::TNode::Id, TNGraph::TNode::InNIdV, IsNode(), TMath::Mx(), MxNId, NodeH, TNGraph::TNode::OutNIdV, 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.InNIdV.GenExt(Pool.GetValVPt(SrcVId), Pool.GetVLen(SrcVId));
  Node.OutNIdV.GenExt(Pool.GetValVPt(DstVId), Pool.GetVLen(DstVId));
  Node.InNIdV.Sort();
  Node.OutNIdV.Sort();
  return NewNId;
}

Here is the call graph for this function:

TEdgeI TNGraph::BegEI ( ) const [inline]

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

Definition at line 489 of file graph.h.

References BegNI(), EndNI(), and TNGraph::TNodeI::GetOutDeg().

Referenced by TKronNoise::FlipEdgeNoise(), TGraphEnumUtils::GetIsoGraphs(), TGraphEnumUtils::GetNormalizedGraph(), TMAGFitBern::GradApxAffMtx(), TGraphEnumUtils::GraphId(), TKronNoise::RemoveEdgeNoise(), TNetInfBs::SaveGroundTruth(), TNetInfBs::SavePajek(), TNetInfBs::SavePlaneTextNet(), and TKroneckerLL::SetGraph().

{ TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0){NI++;} return TEdgeI(NI, EndNI()); }

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::Clr ( ) [inline]

Deletes all nodes and edges from the graph.

Definition at line 507 of file graph.h.

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

Referenced by TFfGGen::Clr(), and TGraphEnumUtils::GetGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::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 329 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::Defrag(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TNGraph::TNode::InNIdV, THash< TKey, TDat, THashFunc >::IsKeyIdEqKeyN(), NodeH, TNGraph::TNode::OutNIdV, and TVec< TVal >::Pack().

Referenced by TSnap::GenRMat(), and TGraphKey::GetNGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::DelEdge ( const int &  SrcNId,
const int &  DstNId,
const bool &  IsDir = true 
)

Deletes an edge from node IDs SrcNId to 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 292 of file graph.cpp.

References TVec< TVal >::Del(), TStr::Fmt(), GetNode(), IAssertR, TNGraph::TNode::InNIdV, IsNode(), TNGraph::TNode::OutNIdV, and TVec< TVal >::SearchBin().

Referenced by TKronNoise::FlipEdgeNoise(), TKroneckerLL::MetroGibbsSampleNext(), TKronNoise::RemoveEdgeNoise(), and TKroneckerLL::RestoreGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::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 256 of file graph.cpp.

References TVec< TVal >::Del(), THash< TKey, TDat, THashFunc >::DelKey(), TNGraph::TNode::GetInDeg(), TNGraph::TNode::GetInNId(), GetNode(), TNGraph::TNode::GetOutDeg(), TNGraph::TNode::GetOutNId(), TNGraph::TNode::InNIdV, NodeH, TNGraph::TNode::OutNIdV, and TVec< TVal >::SearchBin().

Referenced by TKronNoise::RemoveNodeNoise(), and TKroneckerLL::RestoreGraph().

                                    {
  { TNode& Node = GetNode(NId);
  for (int e = 0; e < Node.GetOutDeg(); e++) {
  const int nbr = Node.GetOutNId(e);
  if (nbr == NId) { continue; }
    TNode& N = GetNode(nbr);
    const int n = N.InNIdV.SearchBin(NId);
    if (n!= -1) { N.InNIdV.Del(n); }
  }
  for (int e = 0; e < Node.GetInDeg(); e++) {
  const int nbr = Node.GetInNId(e);
  if (nbr == NId) { continue; }
    TNode& N = GetNode(nbr);
    const int n = N.OutNIdV.SearchBin(NId);
    if (n!= -1) { N.OutNIdV.Del(n); }
  } }
  NodeH.DelKey(NId);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 454 of file graph.h.

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

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

Definition at line 384 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), GetEdges(), TNGraph::TNode::GetId(), TNGraph::TNode::GetInDeg(), TNGraph::TNode::GetInNId(), GetNodes(), TNGraph::TNode::GetOutDeg(), TNGraph::TNode::GetOutNId(), and NodeH.

                                   {
  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
  fprintf(OutF, "-------------------------------------------------\nDirected 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]\n", NodePlaces, Node.GetId());
    fprintf(OutF, "    in [%d]", Node.GetInDeg());
    for (int edge = 0; edge < Node.GetInDeg(); edge++) {
      fprintf(OutF, " %*d", NodePlaces, Node.GetInNId(edge)); }
    fprintf(OutF, "\n    out[%d]", Node.GetOutDeg());
    for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
      fprintf(OutF, " %*d", NodePlaces, Node.GetOutNId(edge)); }
    fprintf(OutF, "\n");
  }
  fprintf(OutF, "\n");
}

Here is the call graph for this function:

bool TNGraph::Empty ( ) const [inline]

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

Definition at line 505 of file graph.h.

References GetNodes().

{ return GetNodes()==0; }

Here is the call graph for this function:

TEdgeI TNGraph::EndEI ( ) const [inline]

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

Definition at line 491 of file graph.h.

References EndNI().

Referenced by TKronNoise::FlipEdgeNoise(), TGraphEnumUtils::GetIsoGraphs(), TGraphEnumUtils::GetNormalizedGraph(), TMAGFitBern::GradApxAffMtx(), TGraphEnumUtils::GraphId(), TKronNoise::RemoveEdgeNoise(), TNetInfBs::SaveGroundTruth(), TNetInfBs::SavePajek(), TNetInfBs::SavePlaneTextNet(), and TKroneckerLL::SetGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Not supported/implemented!

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

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

Definition at line 316 of file graph.cpp.

References EndNI(), GetNI(), IAssert, and TNGraph::TNodeI::NodeHI.

                                                                       {
  const TNodeI SrcNI = GetNI(SrcNId);
  const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
  IAssert(NodeN != -1);
  return TEdgeI(SrcNI, EndNI(), NodeN);
}

Here is the call graph for this function:

int TNGraph::GetMxNId ( ) const [inline]

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

Definition at line 466 of file graph.h.

References MxNId.

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

Gets a vector IDs of all nodes in the graph.

Definition at line 323 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.

Referenced by TKronNoise::FlipEdgeNoise(), TKronNoise::RemoveNodeNoise(), TKroneckerLL::SetGraph(), and TMAGFitBern::SetGraph().

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

Here is the caller graph for this function:

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

Definition at line 394 of file graph.h.

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

Referenced by AddEdge(), DelEdge(), DelNode(), IsEdge(), ReserveNIdInDeg(), and ReserveNIdOutDeg().

{ return NodeH.GetDat(NId); }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 395 of file graph.h.

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

{ return NodeH.GetDat(NId); }

Here is the call graph for this function:

int TNGraph::GetNodes ( ) const [inline]

Returns the number of nodes in the graph.

Definition at line 419 of file graph.h.

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

Referenced by TGStatVec::Add(), TFfGGen::AddNodes(), TKroneckerLL::AppendIsoNodes(), TNGraphMtx::CheckNodeIds(), Dump(), Empty(), TKronNoise::FlipEdgeNoise(), TNetInfBs::GenCascade(), TFfGGen::GenGraph(), TGraphEnumUtils::GetIsoGraphs(), GetNIdV(), TGHash< TDat >::GetNodeMap(), TNetInfBs::GetNodes(), TGraphEnumUtils::GetNormalizedGraph(), TKronMtx::GetNZeroK(), TSnap::GetSngVals(), TSnap::GetSngVec(), TSubGraphEnum< TGraphCounter >::GetSubGraphs(), TKroneckerLL::GradDescent(), TKroneckerLL::GradDescent2(), TKroneckerLL::GradDescentConvergence(), TGraphEnumUtils::GraphId(), TForestFire::InfectAll(), TForestFire::InfectRnd(), TNetInfBs::LoadGroundTruthTxt(), TNGraphMtx::PGetCols(), TNGraphMtx::PGetRows(), TKronMtx::PlotCmpGraphs(), TTimeNENet::PlotEffDiam(), TForestFire::PlotFire(), TFfGGen::PlotFireSize(), TTimeNet::PlotMedianDegOverTm(), TSnap::PlotSngValDistr(), TSnap::PlotSngValRank(), TSnap::PlotSngVec(), TKronNoise::RemoveNodeNoise(), TKroneckerLL::RestoreGraph(), TKroneckerLL::RunMStep(), TKroneckerLL::SetGraph(), TMAGFitBern::SetGraph(), TKroneckerLL::SetOrderPerm(), TKroneckerLL::SetRndPerm(), TGraphKey::TakeGraph(), TGraphKey::TakeSig(), TGStat::TakeSpectral(), TGStat::TakeStat(), TKroneckerLL::TestBicCriterion(), TKroneckerLL::TestGradDescent(), TKroneckerLL::TestSamplePerm(), and TMAGFitBern::TMAGFitBern().

{ return NodeH.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 500 of file graph.h.

References GetNI(), and GetRndNId().

{ return GetNI(GetRndNId(Rnd)); }

Here is the call graph for this function:

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

Returns an ID of a random node in the graph.

Definition at line 498 of file graph.h.

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

Referenced by TNetInfBs::GenCascade(), TSnap::GenCopyModel(), and GetRndNI().

{ 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 6 edges.

  * Edges:  0 -> 1, 1 -> 2, 0 -> 2, 1 -> 3, 3 -> 4, 2 -> 3
  * 

Definition at line 401 of file graph.cpp.

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

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

Here is the call graph for this function:

bool TNGraph::HasFlag ( const TGraphFlag Flag) const

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

Definition at line 201 of file graph.cpp.

References HasGraphFlag.

                                                  {
  return HasGraphFlag(TNGraph::TNet, Flag);
}
bool TNGraph::IsEdge ( const int &  SrcNId,
const int &  DstNId,
const bool &  IsDir = true 
) const
bool TNGraph::IsNode ( const int &  NId) const [inline]
bool TNGraph::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 338 of file graph.cpp.

References TStr::CStr(), EAssertR, ErrNotify(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TNGraph::TNode::GetId(), TNGraph::TNode::GetInDeg(), TNGraph::TNode::GetInNId(), TNGraph::TNode::GetOutDeg(), TNGraph::TNode::GetOutNId(), TNGraph::TNode::InNIdV, IsNode(), TVec< TVal >::IsSorted(), NodeH, and TNGraph::TNode::OutNIdV.

                                                {
  bool RetVal = true;
  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    const TNode& Node = NodeH[N];
    if (! Node.OutNIdV.IsSorted()) {
      const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
    }
    if (! Node.InNIdV.IsSorted()) {
      const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
    }
    // check out-edges
    int prevNId = -1;
    for (int e = 0; e < Node.GetOutDeg(); e++) {
      if (! IsNode(Node.GetOutNId(e))) {
        const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
          Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      if (e > 0 && prevNId == Node.GetOutNId(e)) {
        const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
          Node.GetId(), Node.GetId(), Node.GetOutNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      prevNId = Node.GetOutNId(e);
    }
    // check in-edges
    prevNId = -1;
    for (int e = 0; e < Node.GetInDeg(); e++) {
      if (! IsNode(Node.GetInNId(e))) {
        const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
          Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      if (e > 0 && prevNId == Node.GetInNId(e)) {
        const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
          Node.GetId(), Node.GetId(), Node.GetInNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      prevNId = Node.GetInNId(e);
    }
  }
  return RetVal;
}

Here is the call graph for this function:

static PNGraph TNGraph::Load ( TSIn SIn) [inline, static]

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

Definition at line 412 of file graph.h.

References TNGraph().

Referenced by TKronMomentsFit::Test().

{ return PNGraph(new TNGraph(SIn)); }

Here is the call graph for this function:

Here is the caller graph for this function:

static PNGraph TNGraph::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: PNGraph Graph = TNGraph::New(Nodes, Edges).

Definition at line 410 of file graph.h.

References TNGraph().

{ return new TNGraph(Nodes, Edges); }

Here is the call graph for this function:

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

Definition at line 415 of file graph.h.

References MxNId, and NodeH.

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

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

Definition at line 509 of file graph.h.

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

Referenced by TSnap::GenCopyModel(), TSnap::GenRMat(), TBigNet< TNodeData, IsDir >::GetNGraph(), and TNGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::ReserveNIdInDeg ( const int &  NId,
const int &  InDeg 
) [inline]

Reserves memory for node ID NId having InDeg in-edges.

Definition at line 511 of file graph.h.

References GetNode(), TNGraph::TNode::InNIdV, and TVec< TVal >::Reserve().

Referenced by TBigNet< TNodeData, IsDir >::GetSubNGraph().

{ GetNode(NId).InNIdV.Reserve(InDeg); }

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::ReserveNIdOutDeg ( const int &  NId,
const int &  OutDeg 
) [inline]

Reserves memory for node ID NId having OutDeg out-edges.

Definition at line 513 of file graph.h.

References GetNode(), TNGraph::TNode::OutNIdV, and TVec< TVal >::Reserve().

Referenced by TBigNet< TNodeData, IsDir >::GetSubNGraph().

{ GetNode(NId).OutNIdV.Reserve(OutDeg); }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Saves the graph to a (binary) stream SOut.

Definition at line 404 of file graph.h.

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

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

Here is the call graph for this function:


Friends And Related Function Documentation

friend class TNGraphMtx [friend]

Definition at line 535 of file graph.h.

friend class TPt< TNGraph > [friend]

Definition at line 534 of file graph.h.


Member Data Documentation

TCRef TNGraph::CRef [private]

Definition at line 390 of file graph.h.

TInt TNGraph::MxNId [private]

Definition at line 391 of file graph.h.

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


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