graph-algos.h

#ifndef GRAPH_ALGOS
#define GRAPH_ALGOS

#include "../graph-helpers/stack/Stack.h"

// ===== Traversals =====

/**
 * DFS: dfs <v1> 
 * Performs a depth first search from the given starting vertex
 */
void dfs(Graph, Vertex);
static void dfsRecursive(Graph g, Vertex currVertex, bool *visited);

/**
 * BFS: bfs <v1>  
 * Performs a breadth first search from the given starting vertex
 */
void bfs(Graph, Vertex);

// ===== Graph Properties =====

/**
 * CYCLE: cycle
 * Checks whether a cycle exists in the graph
 */
bool hasCycle(Graph g);

// Helper function for hasCycle
static bool dfsFindCycle(Graph g, Vertex curr, Vertex pred, bool *visited);

/**
 * PATH: path <v1> <v2>
 * Checks whether a path exists between the two vertices using DFS.
 * 
 * pathTrace prints output while isReachable doesn't.
 */
bool pathTrace(Graph g, Vertex src, Vertex dest);
bool isReachable(Graph g, Vertex src, Vertex dest);

// Helper function for pathTrace and isReachable
static bool checkReachable(Graph g, Vertex src, Vertex dest, bool *visited, Vertex *pred);

/**
 * CONNECTED: connected
 * Lists every isolated subgraph and their vertices within the graph
 */
void showConnectedComponents(Graph g);

// Helper function for showConnectedComponents
static void setComponent(Graph g, Vertex curr, int id, int *vertexIDs);

/**
 * CLOSURE: closure
 * Shows the transitive closure matrix, generated by Floyd-Warshall's algorithm
 */
void transitiveClosure(Graph g);

/**
 * HAMILTON: hamilton <v1> <v2> 
 * Shows a Hamiltonian path from src to dest, if it exists. Returns true/false
 * depending on whether a Hamiltonian path exists
 */
bool showHamiltonPath(Graph g, Vertex src, Vertex dest);

/**
 * HAMILTON: hamilton circuit
 * Shows a Hamiltonian circuit, if it exists. Returns true/false depending
 * on whether a Hamiltonian circuit exists
 */
bool showHamiltonCircuit(Graph g);

/**
 * Traces the Hamilton path between src and dest, if it exists. Helper function for the
 * showHamiltonPath and showHamiltonCircuit functions
 */
static bool traceHamiltonPath(Graph g, Vertex src, Vertex dest, int distanceRemaining, bool *visited, Vertex *pred);

/**
 * EULER: euler <v1> <v2>
 * Determines if there exists an Euler path between v1 and v2
 */
bool showEulerPath(Graph g, Vertex src, Vertex dest);

/**
 * EULER CIRCUIT: euler circuit 
 * Determines whether an Euler circuit exists in the graph
 */
bool showEulerCircuit(Graph g);

/**
 * Traces the Euler path between src and dest, if it exists. This is a helper function for the
 * showEulerPath and showEulerCircuit functions
 */
static bool traceEulerPath(Graph g, Vertex src, Vertex dest, int edgesRemaining, bool *visited, Stack pathStack);

// ===== Other Helper Functions =====

/**
 * Mallocates a bool array for tracking whether each node of the graph
 * has been visited or not
 */
bool *newVisitedArray(Graph g); 

/**
 * Mallocates a Vertex array for tracking the predecessor vertex for each
 * vertex
 */
Vertex *newPredArray(Graph g);

/**
 * Prints the visited vertices
 */
void showVisited(Graph g, bool *visited);

/**
 * Prints the route from the destination traced by the given predecessor array
 */
void tracePred(Vertex *pred, Vertex dest);

/**
 * Prints the circuit from the src traced by the given predecessor array
 */
void traceCircuit(Vertex *pred, Vertex src);

/**
 * Prints out a pretty structure illustrating the traversal paths
 * taken from a starting vertex
 */
void showTraversalTrace(Graph g, Vertex startingVertex);
static void traversalTracer(Graph g, Vertex currVertex, bool *visited, int indentLevel, bool *levelConnector);

/**
 * Given a starting vertex and an array for tracking visited nodes,
 * follows every path from that starting vertex and marks each vertex
 * crossed as visited  
 */
static void markVisited(Graph g, Vertex startVertex, bool *visited);

/**
 * Given a starting vertex, returns the number of paths this vertex
 * must diverge to
 */
static int numNextHops(Graph g, Vertex startVertex, bool *visited);

#endif