Triangle counting using liblemon
Namespaces | Classes | Typedefs | Functions | Variables
lemon Namespace Reference

lemon original namespace More...

Namespaces

Classes

class  AbsMap
 
class  AddMap
 
class  AllArcLookUp
 
class  AndMap
 
class  ArcLookUp
 
class  ArgParser
 
class  ArgParserException
 
class  BackwardMap
 
class  BellmanFord
 
struct  BellmanFordDefaultOperationTraits
 
struct  BellmanFordDefaultTraits
 
class  BellmanFordWizard
 
class  BellmanFordWizardBase
 
struct  BellmanFordWizardDefaultTraits
 
class  Bfs
 
struct  BfsDefaultTraits
 
class  BfsVisit
 
struct  BfsVisitDefaultTraits
 
struct  BfsVisitor
 
class  BfsWizard
 
class  BfsWizardBase
 
struct  BfsWizardDefaultTraits
 
class  BinHeap
 
class  BinomialHeap
 
class  BpGraphCopy
 
class  BpGraphReader
 
class  BpGraphWriter
 
class  BucketHeap
 
class  CapacityScaling
 
struct  CapacityScalingDefaultTraits
 
class  CbcMip
 
class  ChristofidesTsp
 
class  Circulation
 
struct  CirculationDefaultTraits
 
class  ClpLp
 
class  Color
 
class  CombineMap
 
class  ComposeMap
 
class  ConArcIt
 
class  ConEdgeIt
 
class  ConstMap
 
class  ConstMap< K, Const< V, v > >
 
class  ConvertMap
 
class  CostScaling
 
struct  CostScalingDefaultTraits
 
class  Counter
 
class  CplexBase
 
class  CplexEnv
 
class  CplexLp
 
class  CplexMip
 
class  CrossRefMap
 
class  CycleCanceling
 
struct  DefaultGraphToEpsTraits
 
class  Dfs
 
struct  DfsDefaultTraits
 
class  DfsVisit
 
struct  DfsVisitDefaultTraits
 
struct  DfsVisitor
 
class  DfsWizard
 
class  DfsWizardBase
 
struct  DfsWizardDefaultTraits
 
class  DHeap
 
class  DiEulerIt
 
class  DigraphCopy
 
class  DigraphReader
 
class  DigraphWriter
 
class  Dijkstra
 
struct  DijkstraDefaultOperationTraits
 
struct  DijkstraDefaultTraits
 
class  DijkstraWizard
 
class  DijkstraWizardBase
 
struct  DijkstraWizardDefaultTraits
 
struct  DimacsDescriptor
 
class  DivMap
 
class  DynArcLookUp
 
class  EdmondsKarp
 
struct  EdmondsKarpDefaultTraits
 
class  Elevator
 
class  EqualMap
 
class  EulerIt
 
class  Exception
 
class  ExtendFindEnum
 
class  FalseMap
 
class  FibHeap
 
class  FilterArcs
 
class  FilterEdges
 
class  FilterNodes
 
class  ForkMap
 
class  FormatError
 
class  ForwardMap
 
class  FullBpGraph
 
class  FullDigraph
 
class  FullGraph
 
class  FunctorToMap
 
class  GlpkBase
 
class  GlpkLp
 
class  GlpkMip
 
class  GomoryHu
 
class  GraphCopy
 
class  GraphReader
 
class  GraphToEps
 
class  GraphWriter
 
class  GreedyTsp
 
class  GridGraph
 
class  GrossoLocatelliPullanMc
 
class  HaoOrlin
 
class  HartmannOrlinMmc
 
struct  HartmannOrlinMmcDefaultTraits
 
class  HeapUnionFind
 
class  HowardMmc
 
struct  HowardMmcDefaultTraits
 
class  HypercubeGraph
 
class  IdentityMap
 
class  IdMap
 
class  InDegMap
 
class  InsertionTsp
 
struct  Invalid
 
class  IoError
 
class  IterableBoolMap
 
class  IterableIntMap
 
class  IterableValueMap
 
class  KarpMmc
 
struct  KarpMmcDefaultTraits
 
class  LessMap
 
class  LgfContents
 
class  LinkedElevator
 
class  ListArcSet
 
class  ListBpGraph
 
class  ListDigraph
 
class  ListEdgeSet
 
class  ListGraph
 
class  ListPath
 
class  LoggerBoolMap
 
class  LpBase
 
class  LpSkeleton
 
class  LpSolver
 
class  MapBase
 
class  MapToFunctor
 
class  MaxCardinalitySearch
 
struct  MaxCardinalitySearchDefaultTraits
 
class  MaxFractionalMatching
 
struct  MaxFractionalMatchingDefaultTraits
 
class  MaxMatching
 
class  MaxWeightedFractionalMatching
 
class  MaxWeightedMatching
 
class  MaxWeightedPerfectFractionalMatching
 
class  MaxWeightedPerfectMatching
 
class  MinCostArborescence
 
struct  MinCostArborescenceDefaultTraits
 
class  MipSkeleton
 
class  MipSolver
 
class  MulMap
 
class  NagamochiIbaraki
 
struct  NagamochiIbarakiDefaultTraits
 
class  NearestNeighborTsp
 
class  NegMap
 
class  NegWriteMap
 
class  NetworkSimplex
 
class  NoCounter
 
class  NoTimeReport
 
class  NotMap
 
class  NotWriteMap
 
class  NullMap
 
class  Opt2Tsp
 
class  Orienter
 
class  OrMap
 
class  OutDegMap
 
class  PairingHeap
 
class  Palette
 
class  Path
 
class  PathNodeIt
 
class  PlanarColoring
 
class  PlanarDrawing
 
class  PlanarEmbedding
 
class  PotentialDifferenceMap
 
class  Preflow
 
struct  PreflowDefaultTraits
 
class  QuadHeap
 
class  RadixHeap
 
class  Random
 
class  RangeIdMap
 
class  RangeMap
 
class  ResidualDigraph
 
class  ReverseDigraph
 
class  ScaleMap
 
class  ScaleWriteMap
 
class  SectionReader
 
class  SectionWriter
 
class  ShiftMap
 
class  ShiftWriteMap
 
class  SimpleBucketHeap
 
class  SimplePath
 
class  SkeletonSolverBase
 
class  SmartArcSet
 
class  SmartBpGraph
 
class  SmartDigraph
 
class  SmartEdgeSet
 
class  SmartGraph
 
class  SoplexLp
 
class  SourceMap
 
class  SparseMap
 
class  SplitNodes
 
class  StaticDigraph
 
class  StaticPath
 
class  SubDigraph
 
class  SubGraph
 
class  SubMap
 
class  Suurballe
 
struct  SuurballeDefaultTraits
 
class  TargetMap
 
class  Timer
 
class  TimeReport
 
class  TimeStamp
 
class  Tolerance
 
class  Tolerance< double >
 
class  Tolerance< float >
 
class  Tolerance< long double >
 
class  TrueMap
 
class  Undirector
 
class  UnionFind
 
class  UnionFindEnum
 

Typedefs

typedef GlpkLp Lp
 
typedef GlpkMip Mip
 
typedef StaticDigraph Graph
 

Functions

BellmanFordWizard< BellmanFordWizardBase< GR, LEN > > bellmanFord (const GR &digraph, const LEN &length)
 
BfsWizard< BfsWizardBase< GR > > bfs (const GR &digraph)
 
Color distantColor (const Color &c)
 
Color distantBW (const Color &c)
 
void function_requires ()
 
void checkConcept ()
 
bool connected (const Graph &graph)
 
int countConnectedComponents (const Graph &graph)
 
int connectedComponents (const Graph &graph, NodeMap &compMap)
 
bool stronglyConnected (const Digraph &digraph)
 
int countStronglyConnectedComponents (const Digraph &digraph)
 
int stronglyConnectedComponents (const Digraph &digraph, NodeMap &compMap)
 
int stronglyConnectedCutArcs (const Digraph &digraph, ArcMap &cutMap)
 
int countBiNodeConnectedComponents (const Graph &graph)
 
bool biNodeConnected (const Graph &graph)
 
int biNodeConnectedComponents (const Graph &graph, EdgeMap &compMap)
 
int biNodeConnectedCutNodes (const Graph &graph, NodeMap &cutMap)
 
int countBiEdgeConnectedComponents (const Graph &graph)
 
bool biEdgeConnected (const Graph &graph)
 
int biEdgeConnectedComponents (const Graph &graph, NodeMap &compMap)
 
int biEdgeConnectedCutEdges (const Graph &graph, EdgeMap &cutMap)
 
bool dag (const Digraph &digraph)
 
void topologicalSort (const Digraph &digraph, NodeMap &order)
 
bool checkedTopologicalSort (const Digraph &digraph, NodeMap &order)
 
bool acyclic (const Graph &graph)
 
bool tree (const Graph &graph)
 
bool bipartite (const Graph &graph)
 
bool bipartitePartitions (const Graph &graph, NodeMap &partMap)
 
bool loopFree (const Graph &graph)
 
bool parallelFree (const Graph &graph)
 
bool simpleGraph (const Graph &graph)
 
int countItems (const Graph &g)
 
int countNodes (const Graph &g)
 
int countRedNodes (const Graph &g)
 
int countBlueNodes (const Graph &g)
 
int countArcs (const Graph &g)
 
int countEdges (const Graph &g)
 
int countOutArcs (const Graph &g, const typename Graph::Node &n)
 
int countInArcs (const Graph &g, const typename Graph::Node &n)
 
int countIncEdges (const Graph &g, const typename Graph::Node &n)
 
bool undirected (const GR &g)
 
DigraphCopy< From, To > digraphCopy (const From &from, To &to)
 
GraphCopy< From, To > graphCopy (const From &from, To &to)
 
BpGraphCopy< From, To > bpGraphCopy (const From &from, To &to)
 
Graph::Arc findArc (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Arc prev=INVALID)
 
Graph::Edge findEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge p=INVALID)
 
DfsWizard< DfsWizardBase< GR > > dfs (const GR &digraph)
 
DijkstraWizard< DijkstraWizardBase< GR, LEN > > dijkstra (const GR &digraph, const LEN &length)
 
DimacsDescriptor dimacsType (std::istream &is)
 
void readDimacsMin (std::istream &is, Digraph &g, LowerMap &lower, CapacityMap &capacity, CostMap &cost, SupplyMap &supply, typename CapacityMap::Value infty=0, DimacsDescriptor desc=DimacsDescriptor())
 
void readDimacsMax (std::istream &is, Digraph &g, CapacityMap &capacity, typename Digraph::Node &s, typename Digraph::Node &t, typename CapacityMap::Value infty=0, DimacsDescriptor desc=DimacsDescriptor())
 
void readDimacsSp (std::istream &is, Digraph &g, LengthMap &length, typename Digraph::Node &s, DimacsDescriptor desc=DimacsDescriptor())
 
void readDimacsCap (std::istream &is, Digraph &g, CapacityMap &capacity, typename CapacityMap::Value infty=0, DimacsDescriptor desc=DimacsDescriptor())
 
void readDimacsMat (std::istream &is, Graph &g, DimacsDescriptor desc=DimacsDescriptor())
 
void writeDimacsMat (std::ostream &os, const Digraph &g, std::string comment="")
 
bool eulerian (const GR &g)
 
GraphToEps< DefaultGraphToEpsTraits< GR > > graphToEps (GR &g, std::ostream &os=std::cout)
 
GraphToEps< DefaultGraphToEpsTraits< GR > > graphToEps (GR &g, const char *file_name)
 
GraphToEps< DefaultGraphToEpsTraits< GR > > graphToEps (GR &g, const std::string &file_name)
 
Value kruskal (const Graph &g, const In &in, Out &out)
 
void mapCopy (const GR &gr, const From &from, To &to)
 
bool mapCompare (const GR &gr, const Map1 &map1, const Map2 &map2)
 
Map::Key mapMin (const GR &gr, const Map &map)
 
Map::Key mapMin (const GR &gr, const Map &map, const Comp &comp)
 
Map::Key mapMax (const GR &gr, const Map &map)
 
Map::Key mapMax (const GR &gr, const Map &map, const Comp &comp)
 
Map::Value mapMinValue (const GR &gr, const Map &map)
 
Map::Value mapMinValue (const GR &gr, const Map &map, const Comp &comp)
 
Map::Value mapMaxValue (const GR &gr, const Map &map)
 
Map::Value mapMaxValue (const GR &gr, const Map &map, const Comp &comp)
 
Map::Key mapFind (const GR &gr, const Map &map, const typename Map::Value &val)
 
Map::Key mapFindIf (const GR &gr, const Map &map, const Pred &pred)
 
int mapCount (const GR &gr, const Map &map, const typename Map::Value &val)
 
int mapCountIf (const GR &gr, const Map &map, const Pred &pred)
 
void mapFill (const GR &gr, Map &map, const typename Map::Value &val)
 
bool isNaN (double v)
 
double round (double r)
 
CostMap::Value minCostArborescence (const Digraph &digraph, const CostMap &cost, typename Digraph::Node source, ArborescenceMap &arborescence)
 
std::istream & readNautyGraph (Graph &graph, std::istream &is=std::cin)
 
void pathCopy (const From &from, To &to)
 
void copyPath (To &to, const From &from)
 
bool checkPath (const Digraph &digraph, const Path &path)
 
Digraph::Node pathSource (const Digraph &digraph, const Path &path)
 
Digraph::Node pathTarget (const Digraph &digraph, const Path &path)
 
bool checkPlanarity (const GR &graph)
 
void radixSort (Iterator first, Iterator last, Functor functor)
 
void stableRadixSort (Iterator first, Iterator last, Functor functor)
 
TimeStamp runningTimeTest (F f, double min_time=10, unsigned int *num=NULL, TimeStamp *full_time=NULL)
 
int triangle_count_given_edge (const Graph &G, const Graph::Arc &e, const ArcLookUp< Graph > &look_up)
 
int64_t triangle_count (const Graph &G, int total_edge)
 
int triangle_count_given_node (const Graph &G, const Graph::Node &n, const ArcLookUp< Graph > &look_up, const std::vector< int > &degree_list, std::vector< int > *extra_node_list)
 
int64_t triangle_count_vertex_iteration (const Graph &G, const std::vector< int > &degree_list, int max_degree)
 
int collect_degree_info (const Graph &G, std::vector< int > *degree_list, int node_size)
 compute the degree for each node and save them to degree_list
 
int64_t get_edge (std::ifstream &fin)
 
std::pair< int, int > read_binfile_to_arclist (const char *file_name, std::vector< std::pair< int, int >> *arcs)
 read the binary graph file and initialize the arcs data structure
 
void construct_graph_from_arclist (Graph *G, const std::vector< std::pair< int, int > > &arcs, int node_size)
 construct the static graph from given arc list
 

Variables

const Invalid INVALID
 
const Color WHITE (1, 1, 1)
 
const Color BLACK (0, 0, 0)
 
const Color RED (1, 0, 0)
 
const Color GREEN (0, 1, 0)
 
const Color BLUE (0, 0, 1)
 
const Color YELLOW (1, 1, 0)
 
const Color MAGENTA (1, 0, 1)
 
const Color CYAN (0, 1, 1)
 
const Color GREY (0, 0, 0)
 
const Color DARK_RED (.5, 0, 0)
 
const Color DARK_GREEN (0,.5, 0)
 
const Color DARK_BLUE (0, 0,.5)
 
const Color DARK_YELLOW (.5,.5, 0)
 
const Color DARK_MAGENTA (.5, 0,.5)
 
const Color DARK_CYAN (0,.5,.5)
 
const long double E
 
const long double LOG2E
 
const long double LOG10E
 
const long double LN2
 
const long double LN10
 
const long double PI
 
const long double PI_2
 
const long double PI_4
 
const long double SQRT2
 
const long double SQRT1_2
 
Random rnd
 

Detailed Description

lemon original namespace

Function Documentation

◆ triangle_count()

int64_t lemon::triangle_count ( const Graph G,
int  total_edge 
)

use edge iteration method to count the triangle

Returns
the exact number of triangle in the graph

◆ triangle_count_vertex_iteration()

int64_t lemon::triangle_count_vertex_iteration ( const Graph G,
const std::vector< int > &  degree_list,
int  max_degree 
)

use node iteration method to count the triangle

Returns
the exact number of triangle in the graph