SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
TSimpleGraph Class Reference

Simple directed/undirected graph defined by its edges. More...

#include <ghash.h>

Collaboration diagram for TSimpleGraph:

Public Member Functions

 TSimpleGraph ()
 
 TSimpleGraph (const TIntPrV &GEdgeV)
 
bool operator== (const TSimpleGraph &Graph) const
 
bool operator< (const TSimpleGraph &Graph) const
 
int GetEdges () const
 
void AddEdge (const int &SrcNId, const int &DstNId)
 
bool Join (const TSimpleGraph &G1, const TSimpleGraph &G2)
 
TIntPrVGetEdgeV ()
 
TIntPrVoperator() ()
 
void Dump (const TStr &Desc=TStr()) const
 

Private Attributes

TIntPrV EdgeV
 

Detailed Description

Simple directed/undirected graph defined by its edges.

Definition at line 539 of file ghash.h.

Constructor & Destructor Documentation

TSimpleGraph::TSimpleGraph ( )
inline

Definition at line 543 of file ghash.h.

543 { }
TSimpleGraph::TSimpleGraph ( const TIntPrV GEdgeV)
inline

Definition at line 544 of file ghash.h.

544 : EdgeV(GEdgeV) { }
TIntPrV EdgeV
Definition: ghash.h:541

Member Function Documentation

void TSimpleGraph::AddEdge ( const int &  SrcNId,
const int &  DstNId 
)
inline

Definition at line 549 of file ghash.h.

References TVec< TVal, TSizeTy >::Add(), and EdgeV.

Referenced by TSubGraphsEnum::RecurBfs().

549 { EdgeV.Add(TIntPr(SrcNId, DstNId)); }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TIntPrV EdgeV
Definition: ghash.h:541
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

void TSimpleGraph::Dump ( const TStr Desc = TStr()) const

Definition at line 274 of file ghash.cpp.

References TStr::CStr(), EdgeV, TStr::Empty(), and TVec< TVal, TSizeTy >::Len().

Referenced by TSubGraphsEnum::Gen2Graphs().

274  {
275  if (! Desc.Empty()) printf("%s. Edges: %d\n", Desc.CStr(), EdgeV.Len());
276  else printf("Edges: %d\n", EdgeV.Len());
277  for (int i = 0; i < EdgeV.Len(); i++) {
278  printf("\t%d\t%d\n", EdgeV[i].Val1(), EdgeV[i].Val2());
279  }
280 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntPrV EdgeV
Definition: ghash.h:541
bool Empty() const
Definition: dt.h:488
char * CStr()
Definition: dt.h:476

Here is the call graph for this function:

Here is the caller graph for this function:

int TSimpleGraph::GetEdges ( ) const
inline

Definition at line 548 of file ghash.h.

References EdgeV, and TVec< TVal, TSizeTy >::Len().

Referenced by Join().

548 { return EdgeV.Len(); }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntPrV EdgeV
Definition: ghash.h:541

Here is the call graph for this function:

Here is the caller graph for this function:

TIntPrV& TSimpleGraph::GetEdgeV ( )
inline

Definition at line 551 of file ghash.h.

References EdgeV.

Referenced by TSubGraphsEnum::EnumSubGraphs(), and TSubGraphsEnum::Gen2Graphs().

551 { return EdgeV; }
TIntPrV EdgeV
Definition: ghash.h:541

Here is the caller graph for this function:

bool TSimpleGraph::Join ( const TSimpleGraph G1,
const TSimpleGraph G2 
)

Definition at line 233 of file ghash.cpp.

References EdgeV, TVec< TVal, TSizeTy >::Gen(), GetEdges(), IAssert, and TVec< TVal, TSizeTy >::Last().

Referenced by TSubGraphsEnum::EnumSubGraphs().

233  {
234  const int Edges1 = G1.GetEdges();
235  const int Edges2 = G2.GetEdges();
236  const TIntPrV& EdgeV1 = G1.EdgeV;
237  const TIntPrV& EdgeV2 = G2.EdgeV;
238  const int MxEdges = Edges1+1;
239  if (GetEdges() != MxEdges) EdgeV.Gen(MxEdges);
240  IAssert(Edges1 == Edges2);
241 
242  int e=0, g1=0, g2=0;
243  while (g1 < Edges1 && g2 < Edges2) {
244  if (e == MxEdges) return false;
245  if (abs(g1 - g2) > 1) return false;
246  if (EdgeV1[g1] == EdgeV2[g2]) { e++; g1++; g2++; }
247  else if (EdgeV1[g1] < EdgeV2[g2]) { e++; g1++; }
248  else { e++; g2++; }
249  }
250 
251  e=0; g1=0; g2=0;
252  while (g1 < Edges1 && g2 < Edges2) {
253  if (EdgeV1[g1] == EdgeV2[g2]) {
254  EdgeV[e] = EdgeV1[g1]; e++; g1++; g2++; }
255  else if (EdgeV1[g1] < EdgeV2[g2]) {
256  EdgeV[e] = EdgeV1[g1]; e++; g1++; }
257  else {
258  EdgeV[e] = EdgeV2[g2]; e++; g2++; }
259  }
260  if (g1 == Edges1 && g2 == Edges2 && e == MxEdges) return true;
261  if (e+1 == MxEdges) {
262  if (g1+1 == Edges1 && g2 == Edges2) {
263  EdgeV[e] = EdgeV1.Last();
264  return true;
265  }
266  if (g1 == Edges1 && g2+1 == Edges2) {
267  EdgeV[e] = EdgeV2.Last();
268  return true;
269  }
270  }
271  return false;
272 }
#define IAssert(Cond)
Definition: bd.h:262
int GetEdges() const
Definition: ghash.h:548
TIntPrV EdgeV
Definition: ghash.h:541
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523

Here is the call graph for this function:

Here is the caller graph for this function:

TIntPrV& TSimpleGraph::operator() ( )
inline

Definition at line 552 of file ghash.h.

References EdgeV.

552 { return EdgeV; }
TIntPrV EdgeV
Definition: ghash.h:541
bool TSimpleGraph::operator< ( const TSimpleGraph Graph) const
inline

Definition at line 546 of file ghash.h.

References EdgeV.

546 { return EdgeV < Graph.EdgeV; }
TIntPrV EdgeV
Definition: ghash.h:541
bool TSimpleGraph::operator== ( const TSimpleGraph Graph) const
inline

Definition at line 545 of file ghash.h.

References EdgeV.

545 { return EdgeV == Graph.EdgeV; }
TIntPrV EdgeV
Definition: ghash.h:541

Member Data Documentation

TIntPrV TSimpleGraph::EdgeV
private

Definition at line 541 of file ghash.h.

Referenced by AddEdge(), Dump(), GetEdges(), GetEdgeV(), Join(), operator()(), operator<(), and operator==().


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