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

Directed multigraph. More...

#include <graph.h>

Collaboration diagram for TNEGraph:

List of all members.

Classes

class  TEdge
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 TNEGraph TNet
typedef TPt< TNEGraphPNet

Public Member Functions

 TNEGraph ()
 TNEGraph (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
 TNEGraph (const TNEGraph &Graph)
 TNEGraph (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).
TNEGraphoperator= (const TNEGraph &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.
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, int EId=-1)
 Adds an edge with ID EId 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 &EId)
 Deletes an edge with edge ID EId from the graph.
void DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true)
 Deletes all edges between node IDs SrcNId and DstNId from the graph.
bool IsEdge (const int &EId) const
 Tests whether an edge with edge ID EId exists in the graph.
bool IsEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
 Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
bool IsEdge (const int &SrcNId, const int &DstNId, int &EId, const bool &IsDir=true) const
 Tests whether an edge between node IDs SrcNId and DstNId exists in the graph. if an edge exists, return its edge ID in EId.
int GetEId (const int &SrcNId, const int &DstNId) const
 Returns an edge ID between node IDs SrcNId and DstNId, if such an edge exists. Otherwise, return -1.
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
TEdgeI GetEI (const int &SrcNId, const int &DstNId) const
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.
int GetRndEId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random edge in the graph.
TEdgeI GetRndEI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random edge in the graph.
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the graph.
void GetEIdV (TIntV &EIdV) const
 Gets a vector IDs of all edges 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 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 PNEGraph New ()
 Static constructor that returns a pointer to the graph. Call: PNEGraph Graph = TNEGraph::New().
static PNEGraph 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 PNEGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it.
static PNEGraph GetSmallGraph ()

Private Member Functions

TNodeGetNode (const int &NId)
const TNodeGetNode (const int &NId) const
TEdgeGetEdge (const int &EId)
const TEdgeGetEdge (const int &EId) const

Private Attributes

TCRef CRef
TInt MxNId
TInt MxEId
THash< TInt, TNodeNodeH
THash< TInt, TEdgeEdgeH

Friends

class TPt< TNEGraph >

Detailed Description

Directed multigraph.

Node IDs can be arbitrary non-negative integers. Nodes and edges have no attributes/data associated with them. There can be more than one directed edge from one source node to a destination node. Self loops (one per node) are allowed as well as multiple (parallel) edges.

Definition at line 555 of file graph.h.


Member Typedef Documentation

Definition at line 558 of file graph.h.

Definition at line 557 of file graph.h.


Constructor & Destructor Documentation

TNEGraph::TNEGraph ( ) [inline]

Definition at line 687 of file graph.h.

Referenced by Load(), and New().

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

Here is the caller graph for this function:

TNEGraph::TNEGraph ( 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 689 of file graph.h.

References Reserve().

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

Here is the call graph for this function:

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

Definition at line 690 of file graph.h.

: MxNId(Graph.MxNId), MxEId(Graph.MxEId), NodeH(Graph.NodeH), EdgeH(Graph.EdgeH) { }
TNEGraph::TNEGraph ( TSIn SIn) [inline]

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

Definition at line 692 of file graph.h.

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

Member Function Documentation

int TNEGraph::AddEdge ( const int &  SrcNId,
const int &  DstNId,
int  EId = -1 
)

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

Returns the ID of the edge being added. If EId is -1, edge ID is automatically assigned. Aborts, if an edge with ID EId already exists. Aborts, if SrcNId or DstNId are not nodes in the graph.

Definition at line 465 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal >::AddSorted(), EdgeH, TStr::Fmt(), GetNode(), IAssertR, TNEGraph::TNode::InEIdV, IsEdge(), IsNode(), TMath::Mx(), MxEId, and TNEGraph::TNode::OutEIdV.

                                                                   {
  if (EId == -1) { EId = MxEId;  MxEId++; }
  else { MxEId = TMath::Mx(EId+1, MxEId()); }
  IAssertR(!IsEdge(EId), TStr::Fmt("EdgeId %d already exists", EId));
  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
  EdgeH.AddDat(EId, TEdge(EId, SrcNId, DstNId));
  GetNode(SrcNId).OutEIdV.AddSorted(EId);
  GetNode(DstNId).InEIdV.AddSorted(EId);
  return EId;
}

Here is the call graph for this function:

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

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

Definition at line 745 of file graph.h.

References AddEdge(), TNEGraph::TEdgeI::GetDstNId(), TNEGraph::TEdgeI::GetId(), and TNEGraph::TEdgeI::GetSrcNId().

Referenced by AddEdge().

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

Here is the call graph for this function:

Here is the caller graph for this function:

int TNEGraph::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 435 of file graph.cpp.

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

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

int TNEGraph::AddNode ( const TNodeI NodeId) [inline]

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

Definition at line 717 of file graph.h.

References AddNode(), and TNEGraph::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:

TEdgeI TNEGraph::BegEI ( ) const [inline]

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

Definition at line 763 of file graph.h.

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

Referenced by Dump().

{ return TEdgeI(EdgeH.BegI(), this); }

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TNEGraph::BegNI ( ) const [inline]

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

Definition at line 727 of file graph.h.

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

Referenced by Dump().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TNEGraph::Clr ( ) [inline]

Deletes all nodes and edges from the graph.

Definition at line 787 of file graph.h.

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

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

Here is the call graph for this function:

void TNEGraph::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 526 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::Defrag(), EdgeH, THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TNEGraph::TNode::InEIdV, THash< TKey, TDat, THashFunc >::IsKeyIdEqKeyN(), NodeH, TNEGraph::TNode::OutEIdV, and TVec< TVal >::Pack().

                                               {
  for (int kid = NodeH.FFirstKeyId(); NodeH.FNextKeyId(kid); ) {
    TNode& Node = NodeH[kid];
    Node.InEIdV.Pack();  Node.OutEIdV.Pack();
  }
  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
  if (! OnlyNodeLinks && ! EdgeH.IsKeyIdEqKeyN()) { EdgeH.Defrag(); }
}

Here is the call graph for this function:

void TNEGraph::DelEdge ( const int &  EId)

Deletes an edge with edge ID EId from the graph.

Definition at line 476 of file graph.cpp.

References TVec< TVal >::DelIfIn(), THash< TKey, TDat, THashFunc >::DelKey(), EdgeH, TNEGraph::TEdge::GetDstNId(), GetEdge(), GetNode(), TNEGraph::TEdge::GetSrcNId(), IAssert, TNEGraph::TNode::InEIdV, IsEdge(), and TNEGraph::TNode::OutEIdV.

                                     {
  IAssert(IsEdge(EId));
  const int SrcNId = GetEdge(EId).GetSrcNId();
  const int DstNId = GetEdge(EId).GetDstNId();
  GetNode(SrcNId).OutEIdV.DelIfIn(EId);
  GetNode(DstNId).InEIdV.DelIfIn(EId);
  EdgeH.DelKey(EId);
}

Here is the call graph for this function:

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

Deletes all edges 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 486 of file graph.cpp.

References TVec< TVal >::DelIfIn(), THash< TKey, TDat, THashFunc >::DelKey(), EdgeH, GetNode(), IAssert, TNEGraph::TNode::InEIdV, IsEdge(), and TNEGraph::TNode::OutEIdV.

                                                                              {
  int EId;
  IAssert(IsEdge(SrcNId, DstNId, EId, IsDir)); // there is at least one edge
  while (IsEdge(SrcNId, DstNId, EId, IsDir)) {
    GetNode(SrcNId).OutEIdV.DelIfIn(EId);
    GetNode(DstNId).InEIdV.DelIfIn(EId);
  }
  EdgeH.DelKey(EId);
}

Here is the call graph for this function:

void TNEGraph::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 446 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::DelKey(), EdgeH, TNEGraph::TEdge::GetDstNId(), GetEdge(), TNEGraph::TNode::GetInDeg(), TNEGraph::TNode::GetInEId(), GetNode(), TNEGraph::TNode::GetOutDeg(), TNEGraph::TNode::GetOutEId(), TNEGraph::TEdge::GetSrcNId(), IAssert, and NodeH.

                                     {
  const TNode& Node = GetNode(NId);
  for (int out = 0; out < Node.GetOutDeg(); out++) {
    const int EId = Node.GetOutEId(out);
    const TEdge& Edge = GetEdge(EId);
    IAssert(Edge.GetSrcNId() == NId);
    GetNode(Edge.GetDstNId()).InEIdV.DelIfIn(EId);
    EdgeH.DelKey(EId);
  }
  for (int in = 0; in < Node.GetInDeg(); in++) {
    const int EId = Node.GetInEId(in);
    const TEdge& Edge = GetEdge(EId);
    IAssert(Edge.GetDstNId() == NId);
    GetNode(Edge.GetSrcNId()).OutEIdV.DelIfIn(EId);
    EdgeH.DelKey(EId);
  }
  NodeH.DelKey(NId);
}

Here is the call graph for this function:

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

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

Definition at line 723 of file graph.h.

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

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

Definition at line 588 of file graph.cpp.

References BegEI(), BegNI(), EndEI(), EndNI(), GetEdges(), and GetNodes().

                                    {
  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
  const int EdgePlaces = (int) ceil(log10((double) GetEdges()));
  fprintf(OutF, "-------------------------------------------------\nDirected Node-Edge Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
  for (TNodeI NodeI = BegNI(); NodeI < EndNI(); NodeI++) {
    fprintf(OutF, "  %*d]\n", NodePlaces, NodeI.GetId());
    fprintf(OutF, "    in[%d]", NodeI.GetInDeg());
    for (int edge = 0; edge < NodeI.GetInDeg(); edge++) {
      fprintf(OutF, " %*d", EdgePlaces, NodeI.GetInEId(edge)); }
    fprintf(OutF, "\n    out[%d]", NodeI.GetOutDeg());
    for (int edge = 0; edge < NodeI.GetOutDeg(); edge++) {
      fprintf(OutF, " %*d", EdgePlaces, NodeI.GetOutEId(edge)); }
    fprintf(OutF, "\n");
  }
  for (TEdgeI EdgeI = BegEI(); EdgeI < EndEI(); EdgeI++) {
    fprintf(OutF, "  %*d]  %*d  ->  %*d\n", EdgePlaces, EdgeI.GetId(), NodePlaces, EdgeI.GetSrcNId(), NodePlaces, EdgeI.GetDstNId());
  }
  fprintf(OutF, "\n");
}

Here is the call graph for this function:

bool TNEGraph::Empty ( ) const [inline]

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

Definition at line 785 of file graph.h.

References GetNodes().

{ return GetNodes()==0; }

Here is the call graph for this function:

TEdgeI TNEGraph::EndEI ( ) const [inline]

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

Definition at line 765 of file graph.h.

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

Referenced by Dump().

{ return TEdgeI(EdgeH.EndI(), this); }

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TNEGraph::EndNI ( ) const [inline]

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

Definition at line 729 of file graph.h.

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

Referenced by Dump(), and TBPGraph::GetEI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

TEdge& TNEGraph::GetEdge ( const int &  EId) [inline, private]

Definition at line 679 of file graph.h.

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

Referenced by DelEdge(), DelNode(), TNEGraph::TNodeI::GetInNId(), TNEGraph::TNodeI::GetNbrNId(), TNEGraph::TNodeI::GetOutNId(), IsEdge(), and TNEGraph::TNodeI::IsInNId().

{ return EdgeH.GetDat(EId); }

Here is the call graph for this function:

Here is the caller graph for this function:

const TEdge& TNEGraph::GetEdge ( const int &  EId) const [inline, private]

Definition at line 680 of file graph.h.

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

{ return EdgeH.GetDat(EId); }

Here is the call graph for this function:

int TNEGraph::GetEdges ( ) const [inline]

Returns the number of edges in the graph.

Definition at line 736 of file graph.h.

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

Referenced by Dump(), TBPGraph::Dump(), and GetEIdV().

{ return EdgeH.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

TEdgeI TNEGraph::GetEI ( const int &  EId) const [inline]

Definition at line 767 of file graph.h.

References EdgeH, and THash< TKey, TDat, THashFunc >::GetI().

Referenced by GetRndEI().

{ return TEdgeI(EdgeH.GetI(EId), this); }

Here is the call graph for this function:

Here is the caller graph for this function:

TEdgeI TNEGraph::GetEI ( const int &  SrcNId,
const int &  DstNId 
) const [inline]

Definition at line 769 of file graph.h.

References GetEI(), and GetEId().

Referenced by GetEI().

{ return GetEI(GetEId(SrcNId, DstNId)); }

Here is the call graph for this function:

Here is the caller graph for this function:

int TNEGraph::GetEId ( const int &  SrcNId,
const int &  DstNId 
) const [inline]

Returns an edge ID between node IDs SrcNId and DstNId, if such an edge exists. Otherwise, return -1.

Definition at line 761 of file graph.h.

References IsEdge().

Referenced by GetEI().

{ int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; }

Here is the call graph for this function:

Here is the caller graph for this function:

void TNEGraph::GetEIdV ( TIntV EIdV) const

Gets a vector IDs of all edges in the graph.

Definition at line 519 of file graph.cpp.

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

                                        {
  EIdV.Gen(GetEdges(), 0);
  for (int E=EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) {
    EIdV.Add(EdgeH.GetKey(E));
  }
}

Here is the call graph for this function:

int TNEGraph::GetMxNId ( ) const [inline]

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

Definition at line 733 of file graph.h.

References MxNId.

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

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

Definition at line 731 of file graph.h.

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

Referenced by TBPGraph::GetEI(), and GetRndNI().

{ return TNodeI(NodeH.GetI(NId), this); }

Here is the call graph for this function:

Here is the caller graph for this function:

void TNEGraph::GetNIdV ( TIntV NIdV) const

Gets a vector IDs of all nodes in the graph.

Definition at line 513 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& TNEGraph::GetNode ( const int &  NId) [inline, private]

Definition at line 677 of file graph.h.

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

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

{ return NodeH.GetDat(NId); }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 678 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 TNEGraph::GetNodes ( ) const [inline]

Returns the number of nodes in the graph.

Definition at line 709 of file graph.h.

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

Referenced by Dump(), TBPGraph::Dump(), Empty(), GetNIdV(), TBPGraph::GetNIdV(), and TBPGraph::GetRndNId().

{ return NodeH.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

TEdgeI TNEGraph::GetRndEI ( TRnd Rnd = TInt::Rnd) [inline]

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

Definition at line 778 of file graph.h.

References GetEI(), and GetRndEId().

{ return GetEI(GetRndEId(Rnd)); }

Here is the call graph for this function:

int TNEGraph::GetRndEId ( TRnd Rnd = TInt::Rnd) [inline]

Returns an ID of a random edge in the graph.

Definition at line 776 of file graph.h.

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

Referenced by GetRndEI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 774 of file graph.h.

References GetNI(), and GetRndNId().

{ return GetNI(GetRndNId(Rnd)); }

Here is the call graph for this function:

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

Returns an ID of a random node in the graph.

Definition at line 772 of file graph.h.

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

Referenced by 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:

static PNEGraph TNEGraph::GetSmallGraph ( ) [static]
bool TNEGraph::HasFlag ( const TGraphFlag Flag) const

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

Definition at line 413 of file graph.cpp.

References HasGraphFlag.

                                                   {
  return HasGraphFlag(TNEGraph::TNet, Flag);
}
bool TNEGraph::IsEdge ( const int &  EId) const [inline]

Tests whether an edge with edge ID EId exists in the graph.

Definition at line 755 of file graph.h.

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

Referenced by AddEdge(), DelEdge(), GetEId(), and IsOk().

{ return EdgeH.IsKey(EId); }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TNEGraph::IsEdge ( const int &  SrcNId,
const int &  DstNId,
const bool &  IsDir = true 
) const [inline]

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

Definition at line 757 of file graph.h.

References IsEdge().

Referenced by IsEdge().

{ int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TNEGraph::IsEdge ( const int &  SrcNId,
const int &  DstNId,
int &  EId,
const bool &  IsDir = true 
) const

Tests whether an edge between node IDs SrcNId and DstNId exists in the graph. if an edge exists, return its edge ID in EId.

Definition at line 496 of file graph.cpp.

References TNEGraph::TEdge::GetDstNId(), GetEdge(), TNEGraph::TEdge::GetId(), TNEGraph::TNode::GetInDeg(), TNEGraph::TNode::GetInEId(), GetNode(), TNEGraph::TNode::GetOutDeg(), TNEGraph::TNode::GetOutEId(), and TNEGraph::TEdge::GetSrcNId().

                                                                                             {
  const TNode& SrcNode = GetNode(SrcNId);
  for (int edge = 0; edge < SrcNode.GetOutDeg(); edge++) {
    const TEdge& Edge = GetEdge(SrcNode.GetOutEId(edge));
    if (DstNId == Edge.GetDstNId()) {
      EId = Edge.GetId();  return true; }
  }
  if (! IsDir) {
    for (int edge = 0; edge < SrcNode.GetInDeg(); edge++) {
    const TEdge& Edge = GetEdge(SrcNode.GetInEId(edge));
    if (DstNId == Edge.GetSrcNId()) {
      EId = Edge.GetId();  return true; }
    }
  }
  return false;
}

Here is the call graph for this function:

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

Tests whether ID NId is a node.

Definition at line 725 of file graph.h.

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

Referenced by AddEdge(), AddNode(), TBPGraph::DelNode(), TBPGraph::IsEdge(), and IsOk().

{ return NodeH.IsKey(NId); }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TNEGraph::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 535 of file graph.cpp.

References TStr::CStr(), EAssertR, EdgeH, ErrNotify(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TNEGraph::TEdge::GetDstNId(), TNEGraph::TNode::GetId(), TNEGraph::TEdge::GetId(), TNEGraph::TNode::GetInDeg(), TNEGraph::TNode::GetInEId(), TNEGraph::TNode::GetOutDeg(), TNEGraph::TNode::GetOutEId(), TNEGraph::TEdge::GetSrcNId(), TNEGraph::TNode::InEIdV, IsEdge(), IsNode(), TVec< TVal >::IsSorted(), NodeH, and TNEGraph::TNode::OutEIdV.

                                                 {
bool RetVal = true;
  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    const TNode& Node = NodeH[N];
    if (! Node.OutEIdV.IsSorted()) {
      const TStr Msg = TStr::Fmt("Out-edge list of node %d is not sorted.", Node.GetId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
    }
    if (! Node.InEIdV.IsSorted()) {
      const TStr Msg = TStr::Fmt("In-edge list of node %d is not sorted.", Node.GetId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
    }
    // check out-edge ids
    int prevEId = -1;
    for (int e = 0; e < Node.GetOutDeg(); e++) {
      if (! IsEdge(Node.GetOutEId(e))) {
        const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.",  Node.GetOutEId(e), Node.GetId());
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      if (e > 0 && prevEId == Node.GetOutEId(e)) {
        const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetOutEId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      prevEId = Node.GetOutEId(e);
    }
    // check in-edge ids
    prevEId = -1;
    for (int e = 0; e < Node.GetInDeg(); e++) {
      if (! IsEdge(Node.GetInEId(e))) {
        const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.",  Node.GetInEId(e), Node.GetId());
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      if (e > 0 && prevEId == Node.GetInEId(e)) {
        const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetInEId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
      }
      prevEId = Node.GetInEId(e);
    }
  }
  for (int E = EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) {
    const TEdge& Edge = EdgeH[E];
    if (! IsNode(Edge.GetSrcNId())) {
      const TStr Msg = TStr::Fmt("Edge %d source node %d does not exist.", Edge.GetId(), Edge.GetSrcNId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
    }
    if (! IsNode(Edge.GetDstNId())) {
      const TStr Msg = TStr::Fmt("Edge %d destination node %d does not exist.", Edge.GetId(), Edge.GetDstNId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
    }
  }
  return RetVal;
}

Here is the call graph for this function:

static PNEGraph TNEGraph::Load ( TSIn SIn) [inline, static]

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

Definition at line 702 of file graph.h.

References TNEGraph().

{ return PNEGraph(new TNEGraph(SIn)); }

Here is the call graph for this function:

static PNEGraph TNEGraph::New ( ) [inline, static]

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

Definition at line 696 of file graph.h.

References TNEGraph().

Referenced by TBPGraph::GetSmallGraph().

{ return PNEGraph(new TNEGraph()); }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 700 of file graph.h.

References TNEGraph().

{ return PNEGraph(new TNEGraph(Nodes, Edges)); }

Here is the call graph for this function:

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

Definition at line 705 of file graph.h.

References EdgeH, MxEId, MxNId, and NodeH.

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

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

Definition at line 789 of file graph.h.

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

Referenced by TNEGraph().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Saves the graph to a (binary) stream SOut.

Definition at line 694 of file graph.h.

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

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

Here is the call graph for this function:


Friends And Related Function Documentation

friend class TPt< TNEGraph > [friend]

Definition at line 807 of file graph.h.


Member Data Documentation

TCRef TNEGraph::CRef [private]

Definition at line 682 of file graph.h.

TInt TNEGraph::MxEId [private]

Definition at line 683 of file graph.h.

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

TInt TNEGraph::MxNId [private]

Definition at line 683 of file graph.h.

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


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