TUNGraph Class Reference

List of all members.

Classes
class	TEdgeI
	Edge iterator. Only forward iteration (operator++) is supported. More...
class	TNode
class	TNodeI
	Node iterator. Only forward iteration (operator++) is supported. More...
Public Types
typedef TUNGraph	TNet
typedef TPt< TUNGraph >	PNet
Public Member Functions
	TUNGraph ()
	TUNGraph (const int &Nodes, const int &Edges)
	Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
	TUNGraph (const TUNGraph &Graph)
	TUNGraph (TSIn &SIn)
	Constructor that loads the graph from a (binary) stream SIn.
void	Save (TSOut &SOut) const
	Saves the graph to a (binary) stream SOut.
bool	HasFlag (const TGraphFlag &Flag) const
	Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
TUNGraph &	operator= (const TUNGraph &Graph)
int	GetNodes () const
	Returns the number of nodes in the graph.
int	AddNode (int NId=-1)
	Adds a node of ID NId to the graph.
int	AddNode (const TNodeI &NodeI)
	Adds a node of ID NodeI.GetId() to the graph.
int	AddNode (const int &NId, const TIntV &NbrNIdV)
	Adds a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV.
int	AddNode (const int &NId, const TVecPool< TInt > &Pool, const int &NIdVId)
	Adds a node of ID NId to the graph and create edges to all nodes in vector NIdVId in the vector pool Pool.
void	DelNode (const int &NId)
	Deletes node of ID NId from the graph.
void	DelNode (const TNode &NodeI)
	Deletes node of ID NodeI.GetId() from the graph.
bool	IsNode (const int &NId) const
	Tests whether ID NId is a node.
TNodeI	BegNI () const
	Returns an iterator referring to the first node in the graph.
TNodeI	EndNI () const
	Returns an iterator referring to the past-the-end node in the graph.
TNodeI	GetNI (const int &NId) const
	Returns an iterator referring to the node of ID NId in the graph.
int	GetMxNId () const
	Returns the maximum id of a any node in the graph.
int	GetEdges () const
	Returns the number of edges in the graph.
int	AddEdge (const int &SrcNId, const int &DstNId)
	Adds an edge between node IDs SrcNId and DstNId to the graph.
int	AddEdge (const TEdgeI &EdgeI)
	Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
void	DelEdge (const int &SrcNId, const int &DstNId)
	Deletes an edge between node IDs SrcNId and DstNId from the graph.
bool	IsEdge (const int &SrcNId, const int &DstNId) const
	Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
TEdgeI	BegEI () const
	Returns an iterator referring to the first edge in the graph.
TEdgeI	EndEI () const
	Returns an iterator referring to the past-the-end edge in the graph.
TEdgeI	GetEI (const int &EId) const
	Not supported/implemented!
TEdgeI	GetEI (const int &SrcNId, const int &DstNId) const
	Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
int	GetRndNId (TRnd &Rnd=TInt::Rnd)
	Returns an ID of a random node in the graph.
TNodeI	GetRndNI (TRnd &Rnd=TInt::Rnd)
	Returns an interator referring to a random node in the graph.
void	GetNIdV (TIntV &NIdV) const
	Gets a vector IDs of all nodes in the graph.
bool	Empty () const
	Tests whether the graph is empty (has zero nodes).
void	Clr ()
	Deletes all nodes and edges from the graph.
void	Reserve (const int &Nodes, const int &Edges)
	Reserves memory for a graph of Nodes nodes and Edges edges.
void	ReserveNIdDeg (const int &NId, const int &Deg)
	Reserves memory for node ID NId having Deg edges.
void	Defrag (const bool &OnlyNodeLinks=false)
	Defragments the graph.
bool	IsOk (const bool &ThrowExcept=true) const
	Checks the graph data structure for internal consistency.
void	Dump (FILE *OutF=stdout) const
	Print the graph in a human readable form to an output stream OutF.
Static Public Member Functions
static PUNGraph	New ()
	Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
static PUNGraph	New (const int &Nodes, const int &Edges)
	Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges.
static PUNGraph	Load (TSIn &SIn)
	Static constructor that loads the graph from a stream SIn and returns a pointer to it.
static PUNGraph	GetSmallGraph ()
	Returns a small graph on 5 nodes and 5 edges.
Friends
class	TUNGraphMtx
class	TPt< TUNGraph >

---

Detailed Description

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

---

Member Typedef Documentation

typedef TPt<TUNGraph> TUNGraph::PNet

typedef TUNGraph TUNGraph::TNet

---

Constructor & Destructor Documentation

TUNGraph::TUNGraph

(

)

[inline]

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

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

TUNGraph::TUNGraph

(

const TUNGraph &

Graph

)

[inline]

TUNGraph::TUNGraph

(

TSIn &

SIn

)

[inline]

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

---

Member Function Documentation

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

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

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

int TUNGraph::AddEdge

(

const TEdgeI &

EdgeI

)

[inline]

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

int TUNGraph::AddNode

(

int

NId = -1

)

Adds a node of ID NId to the graph.

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

int TUNGraph::AddNode

(

const TNodeI &

NodeI

)

[inline]

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

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

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

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

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

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

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

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

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

TEdgeI TUNGraph::BegEI

(

)

const [inline]

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

TNodeI TUNGraph::BegNI

(

)

const [inline]

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

void TUNGraph::Clr

(

)

[inline]

Deletes all nodes and edges from the graph.

void TUNGraph::Defrag

(

const bool &

OnlyNodeLinks = false

)

Defragments the graph.

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

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

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

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

void TUNGraph::DelNode

(

const int &

NId

)

Deletes node of ID NId from the graph.

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

void TUNGraph::DelNode

(

const TNode &

NodeI

)

[inline]

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

void TUNGraph::Dump

(

FILE *

OutF = stdout

)

const

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

bool TUNGraph::Empty

(

)

const [inline]

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

TEdgeI TUNGraph::EndEI

(

)

const [inline]

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

TNodeI TUNGraph::EndNI

(

)

const [inline]

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

int TUNGraph::GetEdges

(

)

const

Returns the number of edges in the graph.

TEdgeI TUNGraph::GetEI

(

const int &

EId

)

const

Not supported/implemented!

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

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

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

int TUNGraph::GetMxNId

(

)

const [inline]

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

TNodeI TUNGraph::GetNI

(

const int &

NId

)

const [inline]

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

void TUNGraph::GetNIdV

(

TIntV &

NIdV

)

const

Gets a vector IDs of all nodes in the graph.

int TUNGraph::GetNodes

(

)

const [inline]

Returns the number of nodes in the graph.

TNodeI TUNGraph::GetRndNI

(

TRnd &

Rnd = TInt::Rnd

)

[inline]

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

int TUNGraph::GetRndNId

(

TRnd &

Rnd = TInt::Rnd

)

[inline]

Returns an ID of a random node in the graph.

PUNGraph TUNGraph::GetSmallGraph

(

)

[static]

Returns a small graph on 5 nodes and 5 edges.

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

bool TUNGraph::HasFlag

(

const TGraphFlag &

Flag

)

const

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

bool TUNGraph::IsEdge	(	const int &	SrcNId,
		const int &	DstNId
	)		const

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

bool TUNGraph::IsNode

(

const int &

NId

)

const [inline]

Tests whether ID NId is a node.

bool TUNGraph::IsOk

(

const bool &

ThrowExcept = true

)

const

Checks the graph data structure for internal consistency.

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

static PUNGraph TUNGraph::Load

(

TSIn &

SIn

)

[inline, static]

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

static PUNGraph TUNGraph::New

(

)

[inline, static]

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

static PUNGraph TUNGraph::New	(	const int &	Nodes,
		const int &	Edges
	)		[inline, static]

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

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

TUNGraph& TUNGraph::operator=

(

const TUNGraph &

Graph

)

[inline]

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

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

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

Reserves memory for node ID NId having Deg edges.

void TUNGraph::Save

(

TSOut &

SOut

)

const [inline]

Saves the graph to a (binary) stream SOut.

---

Friends And Related Function Documentation

friend class TPt< TUNGraph > [friend]

friend class TUNGraphMtx [friend]

---

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

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