CXXGraph

https://github.com/zigrazor/cxxgraph
Admin
CXXGraph is a comprehensive C++ header-only library for managing and manipulating graph algorithms,...
Tokens:88,808
Snippets:474
Trust Score:8.5
License:MPL-2.0
Update:7 months ago
Show doc for...
Tokens:
Raw
### Build and Install Benchmark with CMake

Source: https://github.com/zigrazor/cxxgraph/wiki/Home

Commands to clone the Google Test dependency, configure the build environment using CMake, and compile the benchmark suite. This process ensures the library is properly linked and installed.

```bash
git clone https://github.com/google/googletest.git benchmark/googletest
cd benchmark
cmake -E make_directory "build"
cmake -E chdir "build" cmake -DCMAKE_BUILD_TYPE=Release ../
cmake --build "build" --config Release
sudo cmake --build "build" --config Release --target install
```

--------------------------------

### Build and Run Google Benchmark for CXXGraph

Source: https://github.com/zigrazor/cxxgraph/blob/master/README.md

Outlines the steps to install the Google Benchmark library, compile the project with benchmarking enabled, and execute the benchmark binary to evaluate performance.

```bash
git clone https://github.com/google/benchmark.git
git clone https://github.com/google/googletest.git benchmark/googletest
cd benchmark
cmake -E make_directory "build"
cmake -E chdir "build" cmake -DCMAKE_BUILD_TYPE=Release ../
cmake --build "build" --config Release
sudo cmake --build "build" --config Release --target install

# Compile benchmarks
mkdir -p build
cd build
cmake -DBENCHMARK=ON ..
make

# Run benchmarks
./benchmark
```

--------------------------------

### Build and Run GoogleTest for CXXGraph

Source: https://github.com/zigrazor/cxxgraph/blob/master/README.md

Provides the shell commands required to clone, compile, and install the GoogleTest framework, followed by instructions to compile the project tests and execute the test binary.

```bash
git clone https://github.com/google/googletest.git
cd googletest
mkdir -p build
cd build
cmake ..
make
sudo make install

# Compile tests
mkdir -p build
cd build
cmake -DTEST=ON ..
make

# Run tests
./test_exe
```

--------------------------------

### Configure CXXGraph CMake Build System

Source: https://github.com/zigrazor/cxxgraph/blob/master/CMakeLists.txt

This script sets up the C++17 standard, defines compiler-specific warning and optimization flags, and manages project dependencies. It also handles the installation and packaging of the interface library using the PackageProject module.

```cmake
cmake_minimum_required(VERSION 3.9)
project(CXXGraph VERSION 4.1.0)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED True)

if (MSVC)
	add_compile_options(/bigobj /WX /W4)
else ()
	add_compile_options(-Werror -Wall -Wextra -Wpedantic)
endif(MSVC)

# CPM.cmake dependency management
if(NOT (EXISTS ${CPM_DOWNLOAD_LOCATION}))
	file(DOWNLOAD https://github.com/cpm-cmake/CPM.cmake/releases/latest/download/CPM.cmake ${CPM_DOWNLOAD_LOCATION})
endif()

include(${CPM_DOWNLOAD_LOCATION})
add_library(${PROJECT_NAME} INTERFACE)

CPMAddPackage("gh:TheLartians/PackageProject.cmake@1.6.0")
packageProject(
  NAME ${PROJECT_NAME}
  VERSION ${PROJECT_VERSION}
  INCLUDE_DIR ${PROJECT_SOURCE_DIR}/include
  COMPATIBILITY AnyNewerVersion
  ARCH_INDEPENDENT YES
)
```

--------------------------------

### Graph Input/Output Operations in C++ with CXXGraph

Source: https://context7.com/zigrazor/cxxgraph/llms.txt

Demonstrates reading from and writing to various file formats (CSV, DOT, MTX, binary) using the CXXGraph library. It requires the CXXGraph library and standard C++ libraries. The example shows writing a graph to CSV, then loading it back, and also includes placeholders for reading from DOT and MTX formats.

```cpp
#include <CXXGraph/CXXGraph.hpp>
#include <iostream>

int main() {
    // Create a sample graph
    CXXGraph::Node<int> node1("1", 1);
    CXXGraph::Node<int> node2("2", 2);
    CXXGraph::Node<int> node3("3", 3);

    CXXGraph::UndirectedWeightedEdge<int> edge1("e1", node1, node2, 5.0);
    CXXGraph::UndirectedWeightedEdge<int> edge2("e2", node2, node3, 3.0);

    CXXGraph::T_EdgeSet<int> edgeSet;
    edgeSet.insert(std::make_shared<CXXGraph::UndirectedWeightedEdge<int>>(edge1));
    edgeSet.insert(std::make_shared<CXXGraph::UndirectedWeightedEdge<int>>(edge2));

    CXXGraph::Graph<int> graph(edgeSet);

    // Write graph to CSV file
    int writeResult = graph.writeToFile(
        CXXGraph::InputOutputFormat::STANDARD_CSV,
        "./",           // working directory
        "my_graph",     // filename (without extension)
        false,          // compress
        true,           // write node features
        true            // write edge weights
    );

    if (writeResult == 0) {
        std::cout << "Graph saved to CSV successfully" << std::endl;
    }

    // Read graph from file
    CXXGraph::Graph<int> loadedGraph;
    int readResult = loadedGraph.readFromFile(
        CXXGraph::InputOutputFormat::STANDARD_CSV,
        "./",
        "my_graph",
        false,          // compressed
        true,           // read node features
        true            // read edge weights
    );

    if (readResult == 0) {
        std::cout << "Graph loaded successfully" << std::endl;
        std::cout << "Edges: " << loadedGraph.getEdgeSet().size() << std::endl;
    }

    // Read from DOT format
    CXXGraph::Graph<int> dotGraph;
    dotGraph.readFromDotFile("./", "graph");  // reads graph.dot

    // Read from Matrix Market format
    CXXGraph::Graph<int> mtxGraph;
    mtxGraph.readFromMTXFile("./", "matrix");  // reads matrix.mtx

    return 0;
}

```

--------------------------------

### Graph Slicing using DFS in C++

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d9/d69/Graph_8hpp_source.html

Implements graph slicing by performing a depth-first search (DFS) from a starting node. It identifies nodes reachable from the start node and nodes not reachable from the complement set. This function is templated to work with generic node types.

```cpp
template <typename T>
const std::vector<Node<T>> Graph<T>::graph_slicing(const Node<T> &start) const
{
 std::vector<Node<T>> result;

 auto nodeSet = Graph<T>::getNodeSet();
 // check if start node in the graph
 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
 {
 return result;
 }
 std::vector<Node<T>> C = Graph<T>::depth_first_search(start);
 std::deque<const Node<T> *> C1; // complement of C i.e. nodeSet - C
 for (auto const &node : nodeSet)
 {
 // from the set of all nodes, remove nodes that exist in C
 if (std::find_if(C.begin(), C.end(), [node](const Node<T> nodeC)
 { return (*node == nodeC); }) == C.end())
 C1.push_back(node);
 }

 // For all nodes in C', apply DFS
 // and get the list of reachable nodes and store in M
 std::vector<Node<T>> M;
 for (auto const &node : C1)
 {
 std::vector<Node<T>> reachableNodes = Graph<T>::depth_first_search(*node);
 M.insert(M.end(), reachableNodes.begin(), reachableNodes.end());
 }
 // removes nodes from C that are reachable from M.
 for (const auto &nodeC : C)
 {
 if (std::find_if(M.begin(), M.end(), [nodeC](const Node<T> nodeM)
 { return (nodeM == nodeC); }) == M.end())
 result.push_back(nodeC);
 }
 return result;
 }
```

--------------------------------

### Perform Graph Slicing - C++

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/da/da5/classCXXGRAPH_1_1Graph__TS.html

This function performs graph slicing based on connectivity, starting from a specified node. It returns a vector of nodes that are connected to the start node. This method is part of the CXXGRAPH::Graph class and is not thread-safe. It requires a const reference to a Node<T> as input.

```cpp
virtual const std::vector< Node< T > > & graph_slicing(const Node< T > &start) const = 0;
// This function performs Graph Slicing based on connectivity.
```

--------------------------------

### Compile and Execute Benchmark

Source: https://github.com/zigrazor/cxxgraph/wiki/Home

Standard procedure to compile the benchmark executable from the base directory and run the resulting binary.

```bash
mkdir -p build
cd build
cmake -DBENCHMARK=ON ..
make
./benchmark
```

--------------------------------

### POST /graph/slicing

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d0/df2/classCXXGRAPH_1_1Graph.html

Performs graph slicing based on connectivity starting from a specific node.

```APIDOC
## POST /graph/slicing

### Description
Performs graph slicing. It identifies nodes reachable from the start node that are not reachable from the complement set.

### Method
POST

### Parameters
#### Request Body
- **start** (Node) - Required - The starting node for the traversal.

### Response
#### Success Response (200)
- **nodes** (std::vector<Node>) - A vector of nodes belonging to the sliced set.
```

--------------------------------

### GET /graph/analysis

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d0/df2/classCXXGRAPH_1_1Graph.html

Analytical methods to determine graph properties such as connectivity, directionality, and cycles.

```APIDOC
## GET /graph/analysis/connectivity

### Description
Checks if the graph is connected (undirected) or strongly connected (directed).

### Method
GET

### Response
#### Success Response (200)
- **connected** (bool) - True if the graph meets the connectivity criteria.

---

## GET /graph/analysis/cycles

### Description
Detects cycles in a directed graph using either BFS or DFS algorithms.

### Method
GET

### Response
#### Success Response (200)
- **hasCycle** (bool) - True if a cycle is detected.
```

--------------------------------

### Initialize Partitioner and Partitioning Algorithms

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d8/d91/Partitioner_8hpp_source.html

The copy constructor initializes the partitioning algorithm based on the strategy defined in the GLOBALS configuration. It supports multiple algorithms including HDRF, EdgeBalancedVertexCut, GreedyVertexCut, and EBV.

```cpp
template <typename T>
Partitioner<T>::Partitioner(const Partitioner& other){
	this->dataset = other.dataset;
	this->GLOBALS = other.GLOBALS;
	if (GLOBALS.partitionStategy == PartitionAlgorithm::HDRF_ALG)
	{
		algorithm = new HDRF<T>(GLOBALS);
	} else if (GLOBALS.partitionStategy == PartitionAlgorithm::EDGEBALANCED_VC_ALG)
	{
		algorithm = new EdgeBalancedVertexCut<T>(GLOBALS);
	} else if (GLOBALS.partitionStategy == PartitionAlgorithm::GREEDY_VC_ALG)
	{
		algorithm = new GreedyVertexCut<T>(GLOBALS);
	} else if (GLOBALS.partitionStategy == PartitionAlgorithm::EBV_ALG)
	{
		algorithm = new EBV<T>(GLOBALS);
	}
}
```

--------------------------------

### Calculate Shortest Path with Dijkstra Algorithm in C++

Source: https://github.com/zigrazor/cxxgraph/blob/master/README.md

Demonstrates how to construct a graph using nodes and weighted edges and execute Dijkstra's algorithm to find the shortest path between two nodes. It utilizes the CXXGraph library and outputs the path nodes to the console.

```cpp
#include <iostream>
#include "CXXGraph/CXXGraph.hpp"

int main(){
  CXXGraph::Node<int> nodeA("A", 1);
  CXXGraph::Node<int> nodeB("B", 2);
  CXXGraph::Node<int> nodeC("C", 3);

  CXXGraph::DirectedWeightedEdge<int> edge1("1", nodeA, nodeB, 1);
  CXXGraph::DirectedWeightedEdge<int> edge2("2", nodeB, nodeC, 1);
  CXXGraph::UndirectedWeightedEdge<int> edge3("3", nodeA, nodeC, 6);

  CXXGraph::T_EdgeSet<int> edgeSet;
  edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge1));
  edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge2));
  edgeSet.insert(make_shared<CXXGraph::UndirectedWeightedEdge<int>>(edge3));

  CXXGraph::Graph<int> graph(edgeSet);
  CXXGraph::DijkstraResult res = graph.dijkstra(nodeA, nodeC);

  for(auto node_user_id : res.path){
    std::cout << node_user_id << '\n';
  }
}
```

--------------------------------

### GET /graph/structure

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d0/df2/classCXXGRAPH_1_1Graph.html

Methods to retrieve the structural components of the graph, including nodes and edges.

```APIDOC
## GET /graph/edges

### Description
Returns the set of edges currently present in the graph.

### Method
GET

### Response
#### Success Response (200)
- **edges** (T_EdgeSet) - A list of Edges of the graph.

---

## GET /graph/nodes

### Description
Returns the set of nodes currently present in the graph.

### Method
GET

### Response
#### Success Response (200)
- **nodes** (std::set<Node*>) - A list of Nodes of the graph.
```

--------------------------------

### GET /graph/analysis

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/de/d77/classCXXGRAPH_1_1Graph-members.html

Methods for analyzing graph properties such as connectivity and cycle detection.

```APIDOC
## GET /graph/analysis

### Description
Provides various analytical checks for the graph structure.

### Method
GET

### Endpoint
/graph/analysis

### Response
#### Success Response (200)
- **isCyclic** (boolean) - Returns true if the graph contains cycles.
- **isDirected** (boolean) - Returns true if the graph is directed.
- **isStronglyConnected** (boolean) - Returns true if the graph is strongly connected.
```

--------------------------------

### PartitionStrategy Class

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/de/deb/classCXXGRAPH_1_1PARTITIONING_1_1PartitionStrategy.html

Documentation for the abstract base class `PartitionStrategy` used for graph partitioning algorithms.

```APIDOC
## Class CXXGRAPH::PARTITIONING::PartitionStrategy< T >

### Description
This is an abstract base class template that defines the interface for graph partitioning strategies. It is designed to be inherited by specific partitioning algorithms.

### Method
N/A (Class Definition)

### Endpoint
N/A (Class Definition)

### Parameters
N/A (Class Definition)

### Request Example
N/A (Class Definition)

### Response
N/A (Class Definition)

## Public Member Functions

### virtual void performStep (const Edge< T > &t, PartitionState< T > &Sstate) = 0

#### Description
This is a pure virtual function that must be implemented by derived classes. It represents a single step in the partitioning process.

#### Method
N/A (Pure Virtual Function)

#### Endpoint
N/A (Pure Virtual Function)

#### Parameters
*   **t** (const Edge< T > &) - Required - The edge to process.
*   **Sstate** (PartitionState< T > &) - Required - The current state of the partitioning.

#### Request Example
N/A (Pure Virtual Function)

#### Response
N/A (Pure Virtual Function)

### Source File
`/github/workspace/include/Partitioning/PartitionStrategy.hpp`
```

--------------------------------

### GET /bellmanford

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/da/da5/classCXXGRAPH_1_1Graph__TS.html

Calculates the shortest path between two nodes using the Bellman-Ford algorithm.

```APIDOC
## GET /bellmanford

### Description
Runs the Bellman-Ford algorithm to find the shortest distance between a source and target node. Returns an error if a negative cycle is detected or the target is unreachable.

### Method
GET

### Parameters
#### Query Parameters
- **source** (Node<T>) - Required - The starting vertex.
- **target** (Node<T>) - Required - The destination vertex.

### Response
#### Success Response (200)
- **distance** (double) - The shortest distance from source to target.

#### Error Response (400)
- **error** (string) - Description of negative cycle or reachability failure.
```

--------------------------------

### Partitioning Graphs with CXXGraph

Source: https://context7.com/zigrazor/cxxgraph/llms.txt

Demonstrates how to create a graph and apply partitioning algorithms like HDRF to divide the graph into multiple segments. It includes steps for graph initialization, edge set configuration, and retrieving partition statistics.

```cpp
#include <CXXGraph/CXXGraph.hpp>
#include <iostream>
#include <memory>

using std::make_shared;

int main() {
    CXXGraph::Node<int> nodes[10];
    for (int i = 0; i < 10; i++) {
        nodes[i] = CXXGraph::Node<int>(std::to_string(i), i);
    }

    CXXGraph::T_EdgeSet<int> edgeSet;
    for (int i = 0; i < 9; i++) {
        auto edge = make_shared<CXXGraph::UndirectedEdge<int>>(
            std::to_string(i), nodes[i], nodes[i + 1]
        );
        edgeSet.insert(edge);
    }
    edgeSet.insert(make_shared<CXXGraph::UndirectedEdge<int>>("9", nodes[0], nodes[5]));
    edgeSet.insert(make_shared<CXXGraph::UndirectedEdge<int>>("10", nodes[2], nodes[7]));

    CXXGraph::Graph<int> graph(edgeSet);

    auto partitioned = CXXGraph::Partitioning::Partitioner<int>::partitionGraph(
        graph,
        CXXGraph::Partitioning::HDRF_ALG,
        4,
        1,
        1,
        1,
        4
    );

    auto stats = CXXGraph::Partitioning::getPartitionStats(partitioned);
    std::cout << "Partition Statistics: " << stats << std::endl;

    return 0;
}
```

--------------------------------

### Initialize Doxygen Search Interface

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/classes.html

Initializes the Doxygen search box and menu functionality for the documentation portal. This script is typically injected by Doxygen to enable client-side search capabilities.

```javascript
var searchBox = new SearchBox("searchBox", "search", false, 'Search', '.html');
$(function() {
  initMenu('', true, false, 'search.php', 'Search');
  $(document).ready(function() {
    init_search();
  });
});
```

--------------------------------

### GET /getAdjMatrix

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/da/da5/classCXXGRAPH_1_1Graph__TS.html

Retrieves the adjacency matrix of the graph, containing target nodes and corresponding edges.

```APIDOC
## GET /getAdjMatrix

### Description
Generates a list representing the adjacency matrix of the graph. Each element contains the destination node and the corresponding edge.

### Method
GET

### Endpoint
/getAdjMatrix

### Response
#### Success Response (200)
- **matrix** (List) - A list of adjacency matrix elements.

#### Response Example
{
  "matrix": [{"target": "NodeB", "edge": "Edge1"}]
}
```

--------------------------------

### Get All Edges from CXXGRAPH Graph (C++)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d3/d91/Graph__TS_8hpp_source.html

Returns a constant reference to the list of all edges currently in the graph. This operation is thread-safe.

```cpp
const std::list< const Edge< T > * > & getEdgeSet() const override
```

--------------------------------

### CXXGraph PartitionerThread Constructor

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d7/d1b/classCXXGRAPH_1_1PARTITIONING_1_1PartitionerThread.html

Initializes the PartitionerThread with a list of edges, a partition state, and a partitioning algorithm. This constructor is crucial for setting up the partitioning process.

```cpp
PartitionerThread(std::vector< const Edge< T > * > &list, PartitionState< T > *state, PartitionStrategy< T > *algorithm)
```

--------------------------------

### Graph Pathfinding and MST Algorithms

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/de/d59/classCXXGRAPH_1_1PARTITIONING_1_1Partition.html

A collection of graph algorithms including Eulerian path detection, shortest path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall), and Minimum Spanning Tree algorithms (Prim, Boruvka, Kruskal).

```cpp
virtual std::vector< Node< T > > eulerianPath() const;
virtual const DijkstraResult dijkstra(const Node< T > &source, const Node< T > &target) const;
virtual const BellmanFordResult bellmanford(const Node< T > &source, const Node< T > &target) const;
virtual const FWResult floydWarshall() const;
virtual const MstResult prim() const;
virtual const MstResult boruvka() const;
virtual const MstResult kruskal() const;
```

--------------------------------

### GET /traversal

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/da/da5/classCXXGRAPH_1_1Graph__TS.html

Performs graph traversal algorithms including Breadth-First Search (BFS) and Depth-First Search (DFS).

```APIDOC
## GET /traversal

### Description
Executes BFS or DFS starting from a specified node to return a list of visited nodes.

### Method
GET

### Parameters
#### Query Parameters
- **type** (string) - Required - 'bfs' or 'dfs'.
- **start** (Node<T>) - Required - The starting node for the traversal.

### Response
#### Success Response (200)
- **visited_nodes** (Array<Node<T>>) - List of nodes visited during the traversal.
```

--------------------------------

### Manage Partition Identifiers

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d4/d32/classCXXGRAPH_1_1Partition.html

Methods for getting and setting the unique identifier for a partition object. These are template-based methods within the CXXGRAPH::Partition class.

```cpp
template<typename T>
unsigned int getPartitionId();

template<typename T>
void setPartitionId(unsigned int partitionId);
```

--------------------------------

### Graph Partitioning Management in C++

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/de/d59/classCXXGRAPH_1_1PARTITIONING_1_1Partition.html

Utilities for partitioning graphs using specific algorithms and managing partition identifiers.

```cpp
virtual PartitionMap<T> partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions, double param1=0.0, double param2=0.0, double param3=0.0, unsigned int numberOfthreads=std::thread::hardware_concurrency()) const;

template<typename T>
unsigned int Partition<T>::getPartitionId();

template<typename T>
void Partition<T>::setPartitionId(unsigned int partitionId);
```

--------------------------------

### CXXGraph PartitionerThread Run Method

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d7/d1b/classCXXGRAPH_1_1PARTITIONING_1_1PartitionerThread.html

Executes the partitioning algorithm. This method is the entry point for performing the graph partitioning operation using the configured state and algorithm.

```cpp
void run()
```

--------------------------------

### Initialize and Handle Search Results in JavaScript

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/search/all_0.html

This snippet initializes the search results functionality and sets up an event listener for messages. It handles UI element visibility and focuses on the next search result when a 'take_focus' message is received. Dependencies include the SearchResults class and DOM manipulation.

```javascript
document.getElementById("Loading").style.display="none";
document.getElementById("NoMatches").style.display="none";
var searchResults = new SearchResults("searchResults");
searchResults.Search();
window.addEventListener("message", function(event) {
  if (event.data == "take_focus") {
    var elem = searchResults.NavNext(0);
    if (elem) elem.focus();
  }
});
```

--------------------------------

### Depth-First Search in CXXGraph

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d4/d32/classCXXGRAPH_1_1Partition.html

Performs a Depth-First Search (DFS) traversal starting from a given node. Returns a vector of nodes visited in DFS order. This operation is not thread-safe.

```cpp
virtual const std::vector< CXXGRAPH_1_1Node< T > > depth_first_search(const CXXGRAPH_1_1Node< T > &start) const
```

--------------------------------

### CXXGraph Partitioner Class Constructors

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d8/d6d/classCXXGRAPH_1_1PARTITIONING_1_1Partitioner.html

Defines the constructors for the Partitioner class. The first constructor takes a dataset and global configuration, while the second is a copy constructor.

```cpp
Partitioner(const T_EdgeSet<T> *dataset, Globals &G)
Partitioner(const Partitioner &other)
```

--------------------------------

### Breadth-First Search in CXXGraph

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d4/d32/classCXXGRAPH_1_1Partition.html

Performs a Breadth-First Search (BFS) traversal starting from a given node. Returns a vector of nodes visited in BFS order. This operation is not thread-safe.

```cpp
virtual const std::vector< CXXGRAPH_1_1Node< T > > breadth_first_search(const CXXGRAPH_1_1Node< T > &start) const
```

--------------------------------

### Execute Multi-threaded Coordinated Partitioning

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d8/d91/Partitioner_8hpp_source.html

The startCoordinated method divides the dataset into chunks and processes them in parallel using multiple threads. It manages thread lifecycle, synchronization, and returns the resulting CoordinatedPartitionState.

```cpp
template <typename T>
CoordinatedPartitionState<T> Partitioner<T>::startCoordinated()
{
	CoordinatedPartitionState<T> state(GLOBALS);
	int processors = GLOBALS.threads;
	std::thread myThreads[processors];
	std::shared_ptr<Runnable> myRunnable[processors];
	std::vector<const Edge<T>*> list_vector[processors];
	int n = dataset->size();
	int subSize = n / processors + 1;
	for (int t = 0; t < processors; ++t)
	{
		int iStart = t * subSize;
		int iEnd = std::min((t + 1) * subSize, n);
		if (iEnd >= iStart)
		{
			list_vector[t] = std::vector<const Edge<T>*>(std::next(dataset->begin(), iStart), std::next(dataset->begin(), iEnd));
			myRunnable[t] = std::make_shared<PartitionerThread<T>>(list_vector[t], &state, algorithm);
			myThreads[t] = std::thread(&Runnable::run, myRunnable[t].get());
		}
	}
	for (int t = 0; t < processors; ++t)
	{
		if (myThreads[t].joinable()){
			myThreads[t].join();
		}
	}
	return state;
}
```

--------------------------------

### Partition Class Methods

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d7/dc4/classCXXGRAPH_1_1Partition-members.html

Details the methods and constructors for the CXXGraph::Partition class, used for managing graph partitions.

```APIDOC
## Partition Class Methods

### Description
Provides functionalities for managing and manipulating graph partitions.

### Methods

#### `Partition` (Constructors)

*   **Description**: Constructors for the Partition class.
*   **Method**: N/A (Constructor)
*   **Endpoint**: N/A (Class method)
*   **Constructors**:
    *   `Partition()`: Default constructor.
    *   `Partition(unsigned int partitionId)`: Constructor with a partition ID.
    *   `Partition(const std::list<const Edge<T>*>& edgeSet)`: Constructor with a list of edges.
    *   `Partition(unsigned int partitionId, const std::list<const Edge<T>*>& edgeSet)`: Constructor with a partition ID and a list of edges.

#### `setPartitionId`

*   **Description**: Sets the partition ID for a partition.
*   **Method**: virtual
*   **Endpoint**: N/A (Class method)
*   **Parameters**:
    *   `partitionId` (unsigned int) - The new partition ID.

#### `~Partition`

*   **Description**: Destructor for the Partition class.
*   **Method**: virtual
*   **Endpoint**: N/A (Class method)
```

--------------------------------

### Get All Nodes (CXXGRAPH::Graph_TS)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/da/da5/classCXXGRAPH_1_1Graph__TS.html

Returns a list of all nodes present in the graph. This method is thread-safe and provides access to the graph's node collection.

```cpp
template<typename T >
const std::list< const Node< T > * > CXXGRAPH::Graph_TS< T >::getNodeSet() override virtual;
```

--------------------------------

### Shortest Path and Partitioning Algorithms

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d3/d91/Graph__TS_8hpp_source.html

APIs for running Dijkstra's algorithm, Floyd-Warshall, and graph partitioning.

```APIDOC
## CXXGRAPH::Graph::dijkstra

### Description
Function runs Dijkstra's algorithm for a given source and target node in the graph and returns the shortest path.

### Method
Virtual

### Endpoint
N/A (Class Member Function)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **source** (const Node< T > &) - Required - The source node.
- **target** (const Node< T > &) - Required - The target node.

### Request Example
```
// Assuming 'graph' is an instance of CXXGRAPH::Graph and 'startNode', 'endNode' are Node<T>
graph.dijkstra(startNode, endNode);
```

### Response
#### Success Response (200)
- **DijkstraResult** - An object containing the shortest path and its total weight.

#### Response Example
```json
{
  "path": [
    { "id": 1 },
    { "id": 3 },
    { "id": 5 }
  ],
  "totalWeight": 15.5
}
```

## CXXGRAPH::Graph::partitionGraph

### Description
This function partitions a graph into a specified number of partitions using a given algorithm.

### Method
Virtual

### Endpoint
N/A (Class Member Function)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **algorithm** (PARTITIONING::PartitionAlgorithm) - Required - The partitioning algorithm to use.
- **numberOfPartitions** (unsigned int) - Required - The desired number of partitions.
- **param1** (double) - Optional - Algorithm-specific parameter 1 (default: 0.0).
- **param2** (double) - Optional - Algorithm-specific parameter 2 (default: 0.0).
- **param3** (double) - Optional - Algorithm-specific parameter 3 (default: 0.0).
- **numberOfthreads** (unsigned int) - Optional - The number of threads to use for partitioning (default: hardware concurrency).

### Request Example
```
// Assuming 'graph' is an instance of CXXGRAPH::Graph
graph.partitionGraph(PARTITIONING::PartitionAlgorithm::METIS, 4, 0.1, 0.2);
```

### Response
#### Success Response (200)
- **PartitionMap< T >** - A map where keys are partition IDs and values are lists of nodes belonging to that partition.

#### Response Example
```json
{
  "partitionMap": {
    "0": [ { "id": 1 }, { "id": 3 } ],
    "1": [ { "id": 2 }, { "id": 4 } ]
  }
}
```

## CXXGRAPH::Graph::dial

### Description
This function performs a variation of the shortest path algorithm (potentially Dial's algorithm) within a maximum weight constraint.

### Method
Virtual

### Endpoint
N/A (Class Member Function)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **source** (const Node< T > &) - Required - The source node.
- **maxWeight** (int) - Required - The maximum weight to consider for paths.

### Request Example
```
// Assuming 'graph' is an instance of CXXGRAPH::Graph and 'startNode' is a Node<T>
graph.dial(startNode, 100);
```

### Response
#### Success Response (200)
- **DialResult** - An object containing results from the dial algorithm (details depend on implementation).

#### Response Example
```json
{
  "results": [
    { "nodeId": 1, "distance": 0 },
    { "nodeId": 3, "distance": 5 },
    { "nodeId": 5, "distance": 12 }
  ]
}
```
```

--------------------------------

### Get All Edges (CXXGRAPH::Graph_TS)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/da/da5/classCXXGRAPH_1_1Graph__TS.html

Returns a list of all edges present in the graph. This method is thread-safe and provides access to the graph's edge collection.

```cpp
template<typename T >
const std::list< const Edge< T > * > & CXXGRAPH::Graph_TS< T >::getEdgeSet() override virtual;
```

--------------------------------

### Create and Build Graphs in CXXGraph

Source: https://context7.com/zigrazor/cxxgraph/llms.txt

Shows how to construct a graph in CXXGraph from a set of edges. Covers creating nodes, weighted edges, building an edge set, and initializing a graph. Also demonstrates querying graph properties and dynamically modifying the graph by adding and removing edges.

```cpp
#include <CXXGraph/CXXGraph.hpp>
#include <memory>
#include <iostream>

using std::make_shared;

int main() {
    // Create nodes
    CXXGraph::Node<int> nodeA("A", 1);
    CXXGraph::Node<int> nodeB("B", 2);
    CXXGraph::Node<int> nodeC("C", 3);
    CXXGraph::Node<int> nodeD("D", 4);

    // Create weighted edges
    CXXGraph::DirectedWeightedEdge<int> edge1("e1", nodeA, nodeB, 1.0);
    CXXGraph::DirectedWeightedEdge<int> edge2("e2", nodeB, nodeC, 2.0);
    CXXGraph::DirectedWeightedEdge<int> edge3("e3", nodeA, nodeC, 5.0);
    CXXGraph::DirectedWeightedEdge<int> edge4("e4", nodeC, nodeD, 1.0);

    // Build edge set
    CXXGraph::T_EdgeSet<int> edgeSet;
    edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge1));
    edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge2));
    edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge3));
    edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge4));

    // Create graph from edge set
    CXXGraph::Graph<int> graph(edgeSet);

    // Query graph properties
    std::cout << "Number of edges: " << graph.getEdgeSet().size() << std::endl;
    std::cout << "Number of nodes: " << graph.getNodeSet().size() << std::endl;
    std::cout << "Is directed: " << graph.isDirectedGraph() << std::endl;

    // Dynamically add more edges
    CXXGraph::Node<int> nodeE("E", 5);
    CXXGraph::DirectedWeightedEdge<int> edge5("e5", nodeD, nodeE, 3.0);
    graph.addEdge(&edge5);

    // Remove an edge
    graph.removeEdge("e3");

    return 0;
}
```

--------------------------------

### Depth-First Search in CXXGRAPH::Graph

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d0/df2/classCXXGRAPH_1_1Graph.html

Performs a Depth-First Search (DFS) traversal starting from a given node. Returns a vector of Nodes representing the traversal order. Note: This function is not thread-safe.

```cpp
virtual const std::vector< Node< T > > depth_first_search(const Node< T > &start) const
```

--------------------------------

### Initialize Doxygen Search and Menu

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/dir_701c8f06b1c05dfef7c59ec059aa05bd.html

Initializes the search box and navigation menu for the Doxygen-generated documentation. This script relies on jQuery and the Doxygen search engine to provide interactive documentation features.

```javascript
var searchBox = new SearchBox("searchBox", "search",false,'Search','.html');
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() {
    init_search();
  });
});
```

--------------------------------

### Breadth-First Search in CXXGRAPH::Graph

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d0/df2/classCXXGRAPH_1_1Graph.html

Performs a Breadth-First Search (BFS) traversal starting from a given node. Returns a vector of Nodes representing the traversal order. Note: This function is not thread-safe.

```cpp
virtual const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const
```

--------------------------------

### Depth-First Search in CXXGRAPH Graph (C++)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d3/d91/Graph__TS_8hpp_source.html

Performs a Depth-First Search (DFS) starting from a given node. Returns a vector of nodes visited in DFS order. This operation is thread-safe.

```cpp
const std::vector< Node< T > > depth_first_search(const Node< T > &start) const override
```

--------------------------------

### Perform Breadth-First Search (BFS) with CXXGraph

Source: https://context7.com/zigrazor/cxxgraph/llms.txt

Demonstrates how to traverse a graph level-by-level using the BFS algorithm. It initializes nodes and undirected edges, constructs a graph, and outputs the traversal order.

```cpp
#include <CXXGraph/CXXGraph.hpp>
#include <iostream>
#include <memory>

using std::make_shared;

int main() {
    CXXGraph::Node<int> node1("1", 1);
    CXXGraph::Node<int> node2("2", 2);
    CXXGraph::Node<int> node3("3", 3);
    CXXGraph::Node<int> node4("4", 4);
    CXXGraph::Node<int> node5("5", 5);

    CXXGraph::UndirectedEdge<int> edge1("e1", node1, node2);
    CXXGraph::UndirectedEdge<int> edge2("e2", node1, node3);
    CXXGraph::UndirectedEdge<int> edge3("e3", node2, node4);
    CXXGraph::UndirectedEdge<int> edge4("e4", node3, node5);

    CXXGraph::T_EdgeSet<int> edgeSet;
    edgeSet.insert(make_shared<CXXGraph::UndirectedEdge<int>>(edge1));
    edgeSet.insert(make_shared<CXXGraph::UndirectedEdge<int>>(edge2));
    edgeSet.insert(make_shared<CXXGraph::UndirectedEdge<int>>(edge3));
    edgeSet.insert(make_shared<CXXGraph::UndirectedEdge<int>>(edge4));

    CXXGraph::Graph<int> graph(edgeSet);

    // Perform BFS starting from node1
    std::vector<CXXGraph::Node<int>> visited = graph.breadth_first_search(node1);

    std::cout << "BFS traversal order: ";
    for (const auto& node : visited) {
        std::cout << node.getUserId() << " ";
    }
    std::cout << std::endl;

    return 0;
}
```

--------------------------------

### Initialize and Manage Search Results in JavaScript

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/search/all_6.html

This script initializes the search result display by hiding loading indicators and executing the search query. It also includes an event listener to handle focus navigation requests from parent windows.

```javascript
document.getElementById("Loading").style.display="none";
document.getElementById("NoMatches").style.display="none";
var searchResults = new SearchResults("searchResults");
searchResults.Search();
window.addEventListener("message", function(event) {
	if (event.data == "take_focus") {
		var elem = searchResults.NavNext(0);
		if (elem) elem.focus();
	}
});
```

--------------------------------

### Breadth-First Search in CXXGRAPH Graph (C++)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d3/d91/Graph__TS_8hpp_source.html

Performs a Breadth-First Search (BFS) starting from a given node. Returns a vector of nodes visited in BFS order. This operation is thread-safe.

```cpp
const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const override
```

--------------------------------

### Apply Kosaraju's Algorithm (CXXGRAPH::Graph)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d7/d41/classCXXGRAPH_1_1PARTITIONING_1_1Partition-members.html

Applies Kosaraju's algorithm, typically used for finding strongly connected components in a directed graph. This method is available in the CXXGRAPH::Graph class.

```cpp
virtual bool kosaraju() const
```

--------------------------------

### Get Minimum Nodes Load per Partition (C++)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/dc/d4d/Partition_8hpp_source.html

Finds the minimum number of nodes present in any partition within a PartitionMap. This helps in identifying the least loaded partition in terms of nodes.

```cpp
template <typename T>
unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap)
{
  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
  for (const auto& it : partitionMap)
  {
    if (it.second->getNodeSet().size() < minLoad)
    {
      minLoad = it.second->getNodeSet().size();
    }
  }
  return minLoad;
}
```

--------------------------------

### Initialize and Query DirectedEdge in CXXGraph

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/de/df5/classCXXGRAPH_1_1DirectedEdge.html

Demonstrates the construction of a DirectedEdge object and the usage of its primary member functions to retrieve graph nodes and edge properties.

```cpp
using namespace CXXGRAPH;

// Constructing a DirectedEdge between two nodes
DirectedEdge<int> edge(1, node1, node2);

// Retrieving source and destination nodes
const Node<int>& source = edge.getFrom();
const Node<int>& destination = edge.getTo();

// Checking edge properties
if (edge.isDirected().value_or(false)) {
    // Edge is directed
}
```

--------------------------------

### Get Edge by ID in CXXGraph

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d4/d32/classCXXGRAPH_1_1Partition.html

Retrieves an Edge object from the graph using its unique ID. Returns an optional containing the edge if found, otherwise an empty optional. This operation is not thread-safe.

```cpp
virtual const std::optional< const CXXGRAPH_1_1Edge< T > * > getEdge(unsigned long edgeId) const
```

--------------------------------

### Graph Slicing by Connectivity - C++

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d0/df2/classCXXGRAPH_1_1Graph.html

This function performs graph slicing based on connectivity, starting from a specified node. It returns a constant reference to a vector of Nodes representing the sliced portion of the graph.

```cpp
virtual const std::vector< Node< T > > graph_slicing(const Node< T > &start) const
```

--------------------------------

### Perform Graph Algorithms in C++

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/de/d59/classCXXGRAPH_1_1PARTITIONING_1_1Partition.html

Methods for executing standard graph algorithms such as Kosaraju for strongly connected components, graph slicing, and Ford-Fulkerson for maximum flow.

```cpp
virtual std::vector<std::vector<Node<T>>> kosaraju() const;
virtual const std::vector<Node<T>> graph_slicing(const Node<T> &start) const;
virtual double fordFulkersonMaxFlow(const Node<T> &source, const Node<T> &target) const;
```

--------------------------------

### CXXGRAPH::PARTITIONING::EdgeBalancedVertexCut Constructor

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d1/d89/classCXXGRAPH_1_1PARTITIONING_1_1EdgeBalancedVertexCut.html

Constructor for the EdgeBalancedVertexCut class. It initializes the partitioning algorithm with global parameters.

```cpp
template<typename T>
class CXXGRAPH::PARTITIONING::EdgeBalancedVertexCut< T > {
public:
    EdgeBalancedVertexCut(const Globals &G);
    // ... other members
};

// In the implementation file (or directly if header-only):
// template<typename T>
// CXXGRAPH::PARTITIONING::EdgeBalancedVertexCut<T>::EdgeBalancedVertexCut(const Globals &G) {
//     // Constructor implementation
// }
```

--------------------------------

### Get Maximum Nodes Load per Partition (C++)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/dc/d4d/Partition_8hpp_source.html

Calculates the maximum number of nodes contained within any single partition in the provided PartitionMap. This metric is important for understanding node distribution and resource allocation.

```cpp
template <typename T>
unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap)
{
  unsigned int maxLoad = 0;
  for (const auto& it : partitionMap)
  {
    if (it.second->getNodeSet().size() > maxLoad)
    {
      maxLoad = it.second->getNodeSet().size();
    }
  }
  return maxLoad;
}
```

--------------------------------

### Get Minimum Edges Load per Partition (C++)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/dc/d4d/Partition_8hpp_source.html

Determines the minimum number of edges across all partitions in a PartitionMap. This function helps in assessing the most lightly loaded partition and is used in load balancing calculations.

```cpp
template <typename T>
unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap)
{
  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
  for (const auto& it : partitionMap)
  {
    if (it.second->getEdgeSet().size() < minLoad)
    {
      minLoad = it.second->getEdgeSet().size();
    }
  }
  return minLoad;
}
```

--------------------------------

### Graph Traversal Algorithms

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/de/d59/classCXXGRAPH_1_1PARTITIONING_1_1Partition.html

Endpoints for performing Breadth-First Search (BFS) and Depth-First Search (DFS) on a graph.

```APIDOC
## GET /graph/breadth_first_search

### Description
Performs the breadth first search algorithm over the graph. Note: This function is not thread-safe.

### Method
GET

### Parameters
#### Query Parameters
- **start** (Node<T>) - Required - The starting node for the traversal.

### Response
#### Success Response (200)
- **nodes** (vector<Node<T>>) - A list of nodes visited in BFS order.
```

```APIDOC
## GET /graph/depth_first_search

### Description
Performs the depth first search algorithm over the graph. Note: This function is not thread-safe.

### Method
GET

### Parameters
#### Query Parameters
- **start** (Node<T>) - Required - The starting node for the traversal.

### Response
#### Success Response (200)
- **nodes** (vector<Node<T>>) - A list of nodes visited in DFS order.
```

--------------------------------

### Implement PartitionerThread Execution Logic

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/da/d0e/PartitionerThread_8hpp_source.html

The run method iterates through the assigned edges and invokes the performStep method of the provided PartitionStrategy. This allows for modular partitioning logic execution within a thread.

```cpp
template <typename T>
void PartitionerThread<T>::run()
{
	for (const auto &edge_it : list)
	{
		algorithm->performStep(*edge_it, *state);
	}
}
```

--------------------------------

### Get Maximum Edges Load per Partition (C++)

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/dc/d4d/Partition_8hpp_source.html

Iterates through a PartitionMap to find the maximum number of edges present in any single partition. This function is crucial for understanding load distribution and identifying potential bottlenecks.

```cpp
template <typename T>
unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap)
{
  unsigned int maxLoad = 0;
  for (const auto& it : partitionMap)
  {
    if (it.second->getEdgeSet().size() > maxLoad)
    {
      maxLoad = it.second->getEdgeSet().size();
    }
  }
  return maxLoad;
}
```

--------------------------------

### HDRF Edge Partitioning Step with Deadlock Avoidance

Source: https://github.com/zigrazor/cxxgraph/blob/master/docs/html/d2/df2/HDRF_8hpp_source.html

The performStep method implements the core logic for partitioning an edge. It uses a retry-based locking mechanism on node records to ensure thread safety while preventing deadlocks during concurrent updates.

```cpp
template <typename T>
void HDRF<T>::performStep(const Edge<T> &e, PartitionState<T> &state)
{
	int P = GLOBALS.numberOfPartition;
	double lambda = GLOBALS.param1;
	double epsilon = GLOBALS.param2;
	auto nodePair = e.getNodePair();
	int u = nodePair.first->getId();
	int v = nodePair.second->getId();
	std::shared_ptr<Record<T>> u_record = state.getRecord(u);
	std::shared_ptr<Record<T>> v_record = state.getRecord(v);

	bool locks_taken = false;
	while (!locks_taken)
	{
		srand((unsigned)time(NULL));
		int usleep_time = 2;
		while (!u_record->getLock())
		{
			std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
			usleep_time = (int)pow(usleep_time, 2);
		}
		usleep_time = 2;
		if (u != v)
		{
			while (!v_record->getLock())
			{
				std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
				usleep_time = (int)pow(usleep_time, 2);
				if (usleep_time > GLOBALS.SLEEP_LIMIT)
				{
					u_record->releaseLock();
					performStep(e, state);
					return;
				}
			}
		}
		locks_taken = true;
	}
}
```
Tokens:
Raw