TNGraphMP Class Reference

Directed graph for multi-threaded operations. More...

#include <graphmp.h>

Collaboration diagram for TNGraphMP:

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 TNGraphMP	TNet
typedef TPt< TNGraphMP >	PNet

Public Member Functions
	TNGraphMP ()
	TNGraphMP (const int &Nodes, const int &Edges)
	Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges. More...
	TNGraphMP (const TNGraphMP &Graph)
	TNGraphMP (TSIn &SIn)
	Constructor that loads the graph from a (binary) stream SIn. More...
void	Save (TSOut &SOut) const
	Saves the graph to a (binary) stream SOut. More...
bool	HasFlag (const TGraphFlag &Flag) const
	Allows for run-time checking the type of the graph (see the TGraphFlag for flags). More...
TNGraphMP &	operator= (const TNGraphMP &Graph)
int	GetNodes () const
	Returns the number of nodes in the graph. More...
void	SetNodes (const int &Length)
	Sets the number of nodes in the graph. More...
int	AddNode (int NId=-1)
	Adds a node of ID NId to the graph. More...
int	AddNodeUnchecked (int NId=-1)
	Adds a node of ID NId to the graph without performing checks. More...
int	AddNode (const TNodeI &NodeId)
	Adds a node of ID NodeI.GetId() to the graph. More...
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. More...
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 . More...
void	DelNode (const int &NId)
	Deletes node of ID NId from the graph. More...
void	DelNode (const TNode &NodeI)
	Deletes node of ID NodeI.GetId() from the graph. More...
bool	IsNode (const int &NId) const
	Tests whether ID NId is a node. More...
TNodeI	BegNI () const
	Returns an iterator referring to the first node in the graph. More...
TNodeI	EndNI () const
	Returns an iterator referring to the past-the-end node in the graph. More...
TNodeI	GetNI (const int &NId) const
	Returns an iterator referring to the node of ID NId in the graph. More...
int	GetMxNId () const
	Returns the maximum id of a any node in the graph. More...
int	Reserved () const
int	GetEdges () const
	Returns the number of edges in the graph. More...
int	AddEdge (const int &SrcNId, const int &DstNId)
	Adds an edge from node IDs SrcNId to node DstNId to the graph. More...
int	AddEdgeUnchecked (const int &SrcNId, const int &DstNId)
	Adds an edge from node IDs SrcNId to node DstNId to the graph without performing checks. More...
int	AddEdge (const TEdgeI &EdgeI)
	Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph. More...
int	AddOutEdge1 (int &SrcIdx, const int &SrcNId, const int &DstNId)
int	AddInEdge1 (int &DstIdx, const int &SrcNId, const int &DstNId)
void	AddOutEdge2 (const int &SrcNId, const int &DstNId)
void	AddInEdge2 (const int &SrcNId, const int &DstNId)
void	AddNodeWithEdges (const TInt &NId, TIntV &InNIdV, 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. More...
void	DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true)
	Deletes an edge from node IDs SrcNId to DstNId from the graph. More...
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. More...
TEdgeI	BegEI () const
	Returns an iterator referring to the first edge in the graph. More...
TEdgeI	EndEI () const
	Returns an iterator referring to the past-the-end edge in the graph. More...
TEdgeI	GetEI (const int &SrcNId, const int &DstNId) const
	Returns an iterator referring to edge (SrcNId, DstNId) in the graph. More...
int	GetRndNId (TRnd &Rnd=TInt::Rnd)
	Returns an ID of a random node in the graph. More...
TNodeI	GetRndNI (TRnd &Rnd=TInt::Rnd)
	Returns an interator referring to a random node in the graph. More...
void	GetNIdV (TIntV &NIdV) const
	Gets a vector IDs of all nodes in the graph. More...
bool	Empty () const
	Tests whether the graph is empty (has zero nodes). More...
void	Clr ()
	Deletes all nodes and edges from the graph. More...
void	Reserve (const int &Nodes, const int &Edges)
	Reserves memory for a graph of Nodes nodes and Edges edges. More...
void	ReserveNodeDegs (const int &Idx, const int &InDeg, const int &OutDeg)
	Reserves memory for node Idx having InDeg in-edges and OutDeg out-edges. More...
void	ReserveNIdInDeg (const int &NId, const int &InDeg)
	Reserves memory for node ID NId having InDeg in-edges. More...
void	ReserveNIdOutDeg (const int &NId, const int &OutDeg)
	Reserves memory for node ID NId having OutDeg out-edges. More...
void	SortEdges (const int &Idx, const int &InDeg, const int &OutDeg)
	Sorts in-edges and out-edges. More...
void	SortNodeAdjV ()
	Sorts the adjacency lists of each node. More...
void	Defrag (const bool &OnlyNodeLinks=false)
	Defragments the graph. More...
bool	IsOk (const bool &ThrowExcept=true) const
	Checks the graph data structure for internal consistency. More...
void	Dump (FILE *OutF=stdout) const
	Print the graph in a human readable form to an output stream OutF. More...

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

Private Member Functions
TNode &	GetNode (const int &NId)
const TNode &	GetNode (const int &NId) const

Private Attributes
TCRef	CRef
TInt	MxNId
THashMP< TInt, TNode >	NodeH

Friends
class	TPt< TNGraphMP >
class	TNGraphMPMtx

Detailed Description

Directed graph for multi-threaded operations.

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 27 of file graphmp.h.

Member Typedef Documentation

typedef TPt<TNGraphMP> TNGraphMP::PNet

Definition at line 30 of file graphmp.h.

typedef TNGraphMP TNGraphMP::TNet

Definition at line 29 of file graphmp.h.

Constructor & Destructor Documentation

TNGraphMP::TNGraphMP ( )

inline

Definition at line 132 of file graphmp.h.

Referenced by Load(), and New().

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

Here is the caller graph for this function:

TNGraphMP::TNGraphMP ( const int &  Nodes, const int &  Edges  )

inlineexplicit

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

Definition at line 134 of file graphmp.h.

References Reserve().

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

Here is the call graph for this function:

TNGraphMP::TNGraphMP ( const TNGraphMP &  Graph )

inline

Definition at line 135 of file graphmp.h.

: MxNId(Graph.MxNId), NodeH(Graph.NodeH) { }

TNGraphMP::TNGraphMP ( TSIn &  SIn )

inline

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

Definition at line 137 of file graphmp.h.

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

Member Function Documentation

int TNGraphMP::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 TNGraphMP have no IDs we return -1. Function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 97 of file graphmp.cpp.

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

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

int TNGraphMP::AddEdge ( const TEdgeI &  EdgeI )

inline

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

Definition at line 221 of file graphmp.h.

References AddEdge(), TNGraphMP::TEdgeI::GetDstNId(), and TNGraphMP::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 TNGraphMP::AddEdgeUnchecked	(	const int &	SrcNId,
		const int &	DstNId
	)

Adds an edge from node IDs SrcNId to node DstNId to the graph without performing checks.

Definition at line 106 of file graphmp.cpp.

References TVec< TVal, TSizeTy >::Add(), GetNode(), TNGraphMP::TNode::InNIdV, and TNGraphMP::TNode::OutNIdV.

                                                                    {
  GetNode(SrcNId).OutNIdV.Add(DstNId);
  GetNode(DstNId).InNIdV.Add(SrcNId);
  return -1; // edge id
}

Here is the call graph for this function:

int TNGraphMP::AddInEdge1	(	int &	DstIdx,
		const int &	SrcNId,
		const int &	DstNId
	)

Definition at line 253 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::AddKey12(), and NodeH.

                                                                           {
  bool Found;
  int DstKeyId;

  //DstKeyId = NodeH.AddKey2(DstIdx, DstNId, Found);
  DstKeyId = NodeH.AddKey12(DstIdx, DstNId, Found);
  if (!Found) {
    NodeH[DstKeyId] = TNode(DstNId);
    //MxNId = TMath::Mx(DstNId+1, MxNId());
  }
  //GetNode(DstNId).InNIdV.Add(SrcNId);
  //NodeH[DstKeyId].InNIdV.Add1(SrcNId);

  // TODO:RS, edge lists need to be sorted at the end

  DstIdx = DstKeyId;
  return Found;
}

Here is the call graph for this function:

void TNGraphMP::AddInEdge2	(	const int &	SrcNId,
		const int &	DstNId
	)

Definition at line 276 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::GetKeyId(), and NodeH.

                                                               {
  NodeH[NodeH.GetKeyId(DstNId)].InNIdV.AddMP(SrcNId);
}

Here is the call graph for this function:

int TNGraphMP::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 10 of file graphmp.cpp.

References THashMP< 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 TNGraphMP::AddNode ( const TNodeI &  NodeId )

inline

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

Definition at line 166 of file graphmp.h.

References AddNode(), and TNGraphMP::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 TNGraphMP::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 TNGraphMP::IsOk to check that the resulting graph is consistent after the operation.

Definition at line 30 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), IAssertR, TNGraphMP::TNode::Id, TNGraphMP::TNode::InNIdV, IsNode(), TMath::Mx(), MxNId, NodeH, TNGraphMP::TNode::OutNIdV, and TVec< TVal, TSizeTy >::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 TNGraphMP::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 TNGraphMP::IsOk to check that the resulting graph is consistent.

Definition at line 50 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TVec< TVal, TSizeTy >::GenExt(), TVecPool< TVal, TSizeTy >::GetValVPt(), TVecPool< TVal, TSizeTy >::GetVLen(), IAssertR, TNGraphMP::TNode::Id, TNGraphMP::TNode::InNIdV, IsNode(), TMath::Mx(), MxNId, NodeH, TNGraphMP::TNode::OutNIdV, and TVec< TVal, TSizeTy >::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:

int TNGraphMP::AddNodeUnchecked

(

int

NId = -1

)

Adds a node of ID NId to the graph without performing checks.

Definition at line 21 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::AddDat(), IsNode(), TMath::Mx(), MxNId, and NodeH.

                                       {
  if (IsNode(NId)) { return NId;}
  MxNId = TMath::Mx(NId+1, MxNId());
  NodeH.AddDat(NId, TNode(NId));
  return NId;
}

Here is the call graph for this function:

void TNGraphMP::AddNodeWithEdges	(	const TInt &	NId,
		TIntV &	InNIdV,
		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.

Definition at line 282 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::AddKey13(), TInt::GetPrimHashCd(), NodeH, and Reserved().

                                                                               {
  int NodeIdx = abs((NId.GetPrimHashCd()) % Reserved());
  int NodeKeyId = NodeH.AddKey13(NodeIdx, NId);
  NodeH[NodeKeyId] = TNode(NId);
  NodeH[NodeKeyId].InNIdV.MoveFrom(InNIdV);
  NodeH[NodeKeyId].OutNIdV.MoveFrom(OutNIdV);  
}

Here is the call graph for this function:

int TNGraphMP::AddOutEdge1	(	int &	SrcIdx,
		const int &	SrcNId,
		const int &	DstNId
	)

Definition at line 234 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::AddKey12(), and NodeH.

                                                                            {
  bool Found;
  int SrcKeyId;

  //SrcKeyId = NodeH.AddKey2(SrcIdx, SrcNId, Found);
  SrcKeyId = NodeH.AddKey12(SrcIdx, SrcNId, Found);
  if (!Found) {
    NodeH[SrcKeyId] = TNode(SrcNId);
    //MxNId = TMath::Mx(SrcNId+1, MxNId());
  }
  //GetNode(SrcNId).OutNIdV.Add(DstNId);
  //NodeH[SrcKeyId].OutNIdV.Add1(DstNId);

  // TODO:RS, edge lists need to be sorted at the end

  SrcIdx = SrcKeyId;
  return Found;
}

Here is the call graph for this function:

void TNGraphMP::AddOutEdge2	(	const int &	SrcNId,
		const int &	DstNId
	)

Definition at line 272 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::GetKeyId(), and NodeH.

                                                                {
  NodeH[NodeH.GetKeyId(SrcNId)].OutNIdV.AddMP(DstNId);
}

Here is the call graph for this function:

TEdgeI TNGraphMP::BegEI ( ) const

inline

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

Definition at line 239 of file graphmp.h.

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

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

Here is the call graph for this function:

TNodeI TNGraphMP::BegNI ( ) const

inline

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

Definition at line 197 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::BegI().

Referenced by BegEI(), and SortNodeAdjV().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraphMP::Clr ( )

inline

Deletes all nodes and edges from the graph.

Definition at line 257 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::Clr().

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

Here is the call graph for this function:

void TNGraphMP::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 149 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::FFirstKeyId(), THashMP< TKey, TDat, THashFunc >::FNextKeyId(), TNGraphMP::TNode::InNIdV, NodeH, TNGraphMP::TNode::OutNIdV, and TVec< TVal, TSizeTy >::Pack().

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

Here is the call graph for this function:

void TNGraphMP::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 112 of file graphmp.cpp.

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

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

void TNGraphMP::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 68 of file graphmp.cpp.

References TVec< TVal, TSizeTy >::Del(), TNGraphMP::TNode::GetInDeg(), TNGraphMP::TNode::GetInNId(), GetNode(), TNGraphMP::TNode::GetOutDeg(), TNGraphMP::TNode::GetOutNId(), TNGraphMP::TNode::InNIdV, NodeH, TNGraphMP::TNode::OutNIdV, and TVec< TVal, TSizeTy >::SearchBin().

                                      {
#if 0
  { 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);
#endif
}

Here is the call graph for this function:

void TNGraphMP::DelNode ( const TNode &  NodeI )

inline

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

Definition at line 193 of file graphmp.h.

References DelNode(), and TNGraphMP::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 TNGraphMP::Dump

(

FILE *

OutF = stdout

)

const

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

Definition at line 206 of file graphmp.cpp.

References edge, THashMP< TKey, TDat, THashFunc >::FFirstKeyId(), THashMP< TKey, TDat, THashFunc >::FNextKeyId(), GetEdges(), TNGraphMP::TNode::GetId(), TNGraphMP::TNode::GetInDeg(), TNGraphMP::TNode::GetInNId(), GetNodes(), TNGraphMP::TNode::GetOutDeg(), TNGraphMP::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 TNGraphMP::Empty ( ) const

inline

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

Definition at line 255 of file graphmp.h.

References GetNodes().

{ return GetNodes()==0; }

Here is the call graph for this function:

TEdgeI TNGraphMP::EndEI ( ) const

inline

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

Definition at line 241 of file graphmp.h.

References EndNI().

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

Here is the call graph for this function:

TNodeI TNGraphMP::EndNI ( ) const

inline

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

Definition at line 199 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::EndI().

Referenced by BegEI(), EndEI(), GetEI(), and SortNodeAdjV().

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

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraphMP::GetEdges

(

)

const

Returns the number of edges in the graph.

Definition at line 89 of file graphmp.cpp.

References THashMP< TKey, TDat, THashFunc >::FFirstKeyId(), THashMP< TKey, TDat, THashFunc >::FNextKeyId(), and NodeH.

Referenced by Dump().

                              {
  int edges=0;
  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    edges+=NodeH[N].GetOutDeg();
  }
  return edges;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 136 of file graphmp.cpp.

References EndNI(), GetNI(), IAssert, and TNGraphMP::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 TNGraphMP::GetMxNId ( ) const

inline

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

Definition at line 205 of file graphmp.h.

References MxNId.

{ return MxNId; }

TNodeI TNGraphMP::GetNI ( const int &  NId ) const

inline

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

Definition at line 201 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::GetI().

Referenced by GetEI(), and GetRndNI().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraphMP::GetNIdV

(

TIntV &

NIdV

)

const

Gets a vector IDs of all nodes in the graph.

Definition at line 143 of file graphmp.cpp.

References TVec< TVal, TSizeTy >::Add(), THashMP< TKey, TDat, THashFunc >::FFirstKeyId(), THashMP< TKey, TDat, THashFunc >::FNextKeyId(), TVec< TVal, TSizeTy >::Gen(), THashMP< 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& TNGraphMP::GetNode ( const int &  NId )

inlineprivate

Definition at line 129 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::GetDat().

Referenced by AddEdge(), AddEdgeUnchecked(), 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& TNGraphMP::GetNode ( const int &  NId ) const

inlineprivate

Definition at line 130 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::GetDat().

{ return NodeH.GetDat(NId); }

Here is the call graph for this function:

int TNGraphMP::GetNodes ( ) const

inline

Returns the number of nodes in the graph.

Definition at line 154 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::Len().

Referenced by Dump(), Empty(), and GetNIdV().

{ return NodeH.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TNGraphMP::GetRndNI ( TRnd &  Rnd = TInt::Rnd )

inline

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

Definition at line 250 of file graphmp.h.

References GetNI(), and GetRndNId().

{ return GetNI(GetRndNId(Rnd)); }

Here is the call graph for this function:

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

inline

Returns an ID of a random node in the graph.

Definition at line 248 of file graphmp.h.

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

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:

PNGraphMP TNGraphMP::GetSmallGraph ( )

static

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 223 of file graphmp.cpp.

References New().

                                   {
  PNGraphMP G = TNGraphMP::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 TNGraphMP::HasFlag

(

const TGraphFlag &

Flag

)

const

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

Definition at line 6 of file graphmp.cpp.

References HasGraphFlag.

                                                    {
  return HasGraphFlag(TNGraphMP::TNet, Flag);
}

bool TNGraphMP::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.

Definition at line 130 of file graphmp.cpp.

References GetNode(), IsNode(), and TNGraphMP::TNode::IsOutNId().

Referenced by AddEdge().

                                                                                    {
  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool TNGraphMP::IsNode ( const int &  NId ) const

inline

Tests whether ID NId is a node.

Definition at line 195 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::IsKey().

Referenced by AddEdge(), AddNode(), AddNodeUnchecked(), DelEdge(), IsEdge(), and IsOk().

{ return NodeH.IsKey(NId); }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TNGraphMP::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 160 of file graphmp.cpp.

References TStr::CStr(), EAssertR, ErrNotify(), THashMP< TKey, TDat, THashFunc >::FFirstKeyId(), TStr::Fmt(), THashMP< TKey, TDat, THashFunc >::FNextKeyId(), TNGraphMP::TNode::GetId(), TNGraphMP::TNode::GetInDeg(), TNGraphMP::TNode::GetInNId(), TNGraphMP::TNode::GetOutDeg(), TNGraphMP::TNode::GetOutNId(), TNGraphMP::TNode::InNIdV, IsNode(), TVec< TVal, TSizeTy >::IsSorted(), NodeH, and TNGraphMP::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 PNGraphMP TNGraphMP::Load ( TSIn &  SIn )

inlinestatic

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

Definition at line 147 of file graphmp.h.

References TNGraphMP().

{ return PNGraphMP(new TNGraphMP(SIn)); }

Here is the call graph for this function:

static PNGraphMP TNGraphMP::New ( )

inlinestatic

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

Definition at line 141 of file graphmp.h.

References TNGraphMP().

Referenced by GetSmallGraph(), TSnap::ToGraphMP(), and TSnap::ToGraphMP3().

{ return new TNGraphMP(); }

Here is the call graph for this function:

Here is the caller graph for this function:

static PNGraphMP TNGraphMP::New ( const int &  Nodes, const int &  Edges  )

inlinestatic

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

Call: PNGraphMP Graph = TNGraphMP::New(Nodes, Edges).

Definition at line 145 of file graphmp.h.

References TNGraphMP().

{ return new TNGraphMP(Nodes, Edges); }

Here is the call graph for this function:

TNGraphMP& TNGraphMP::operator= ( const TNGraphMP &  Graph )

inline

Definition at line 150 of file graphmp.h.

References MxNId, and NodeH.

                                                 {
    if (this!=&Graph) { MxNId=Graph.MxNId; NodeH=Graph.NodeH; }  return *this; }

void TNGraphMP::Reserve ( const int &  Nodes, const int &  Edges  )

inline

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

Definition at line 259 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::Gen().

Referenced by TNGraphMP().

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

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraphMP::Reserved ( ) const

inline

Definition at line 206 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::GetReservedKeyIds().

Referenced by AddNodeWithEdges().

{return NodeH.GetReservedKeyIds();}

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraphMP::ReserveNIdInDeg ( const int &  NId, const int &  InDeg  )

inline

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

Definition at line 263 of file graphmp.h.

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

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

Here is the call graph for this function:

void TNGraphMP::ReserveNIdOutDeg ( const int &  NId, const int &  OutDeg  )

inline

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

Definition at line 265 of file graphmp.h.

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

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

Here is the call graph for this function:

void TNGraphMP::ReserveNodeDegs ( const int &  Idx, const int &  InDeg, const int &  OutDeg  )

inline

Reserves memory for node Idx having InDeg in-edges and OutDeg out-edges.

Definition at line 261 of file graphmp.h.

{ if (InDeg > 0) NodeH[Idx].InNIdV.Reserve(InDeg); if (OutDeg > 0) NodeH[Idx].OutNIdV.Reserve(OutDeg); }

void TNGraphMP::Save ( TSOut &  SOut ) const

inline

Saves the graph to a (binary) stream SOut.

Definition at line 139 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::Save(), and TInt::Save().

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

Here is the call graph for this function:

void TNGraphMP::SetNodes ( const int &  Length )

inline

Sets the number of nodes in the graph.

Definition at line 156 of file graphmp.h.

References THashMP< TKey, TDat, THashFunc >::SetLen().

{ NodeH.SetLen(Length); }

Here is the call graph for this function:

void TNGraphMP::SortEdges ( const int &  Idx, const int &  InDeg, const int &  OutDeg  )

inline

Sorts in-edges and out-edges.

Definition at line 267 of file graphmp.h.

{ if (InDeg > 0) NodeH[Idx].InNIdV.Sort(); if (OutDeg > 0) NodeH[Idx].OutNIdV.Sort(); }

void TNGraphMP::SortNodeAdjV ( )

inline

Sorts the adjacency lists of each node.

Definition at line 269 of file graphmp.h.

References BegNI(), and EndNI().

{ for (TNodeI NI = BegNI(); NI < EndNI(); NI++) { NI.SortNIdV();} }

Here is the call graph for this function:

Friends And Related Function Documentation

friend class TNGraphMPMtx

friend

Definition at line 291 of file graphmp.h.

friend class TPt< TNGraphMP >

friend

Definition at line 290 of file graphmp.h.

Member Data Documentation

TCRef TNGraphMP::CRef

private

Definition at line 125 of file graphmp.h.

TInt TNGraphMP::MxNId

private

Definition at line 126 of file graphmp.h.

Referenced by AddNode(), AddNodeUnchecked(), GetMxNId(), and operator=().

THashMP<TInt, TNode> TNGraphMP::NodeH

private

Definition at line 127 of file graphmp.h.

Referenced by AddInEdge1(), AddInEdge2(), AddNode(), AddNodeUnchecked(), AddNodeWithEdges(), AddOutEdge1(), AddOutEdge2(), Defrag(), DelNode(), Dump(), GetEdges(), GetNIdV(), IsOk(), and operator=().

---

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

• snap-core/graphmp.h
• snap-core/graphmp.cpp