A library constructed using c++11 and some others libraries made by Bruno Dantas and Eduardo Guedes.
The library have two constructor methods that return us a type grafo. This type contains the number of Vertex and the graph built using the required structure.
This method construct the representation of Adjacency Vector and write every information of the graph in a txt file named (graphfile). This method returns a grafoVector type, so, be careful on define the variables.
Like the constroiVector, this method construct the representation of Adjacency Vector and write every information of the graph in a txt file named (graphfile). The main difference is that the data structure is representes using Array of Vector and the Vector contains a pair (neighbor, weight). One of the features is that the user can choose a directed graph or not, just setting a boolean true or false in the constructor function.This method returns a grafoVectorComPeso type.
This method construct the representation of Adjacency Matrix and like the Method constroiVector it writes a txt file named graphfile. This method returns a grafoMatriz type.
Like the constroiVector, this method construct the representation of Adjacency Matrix and write every information of the graph in a txt file named (graphfile). The main difference is that the data structure is representes using 2D array of integers, that the integer represent the weight between the vertex. One of the features is that the user can choose a directed graph or not, just setting a boolean true or false in the constructor function. This method returns a grafoMatrizComPeso type.
This library can represent graphs using Adjacency Vector and Adjacency Matrix.
This representation was built using the std vector and the simple array in c++. Also knowed as Array of vector. So, the user can add the max degree without problems about memory allocation.
This representation was built using a 2D array, so it's necessary to determinate the number of elements (number of vertex) to be used in this data structure.
Like every graph, there are some basic functions (All of the functions bellow were implemented on both representations supported by the library) . There are:
The BFS (Breadth First Search) can traverse the graph from the given node (start) and run every node connected to this vertex. This function can give us the spanning tree by giving the father (who discovered the node) and it's degree (father's degree +1). This function can also give us the shortest path from the node start to a vertex. This implementation have a boolean that enable the user save a txt file containing the spanning tree.
The DFS (Depth First Search) can traverse the graph like the BFS can give us the spanning tree but different from this one, it explores as far as possible in a branch and then come back to a fixed point.This implementation have a boolean that enable the user save a txt file containing the spanning tree.
This function give us the number of Connected Components of a graph sorted by their size and the vertex that belongs to a specific component. The function works running a simple bfs in a vertex, and after, inside of a for loop, it's just check if the next one was visited. If yes, just check the next. If no, run the bfs for this vertex. And it's just repeat the process until the number of vertex is the maximum.This implementation have a boolean that enable the user save a txt file containing the Connected Components sorted in a decrescent way.
This function returns the diameter of a graph (The maximum minimum path between two vertex). So, the implementation consisted in run a BFS for each vertex in the graph, so, it's possible to measure the maximum distance between two vertex starting from every nodes.
The Distance is the shortest path from a vertex a to a vertex b. So, the implementation consisted just in use a simple BFS and measure the distance between a and b.
The Dijkstra is a way to traverse the graph like the BFS and DFS, but the difference is that the algorithm choose the shortest path between a vertex and its neighbors. This implementation also return us the distance and path to every vertex in the graph (if there's no argument objective) or return just the distance and path to a vertex objective. OBS: only workable if your graph is weighted and its weight are positive.
The Prim is a algorithm able to build a MST (Minimum Spanning Tree).It's like the BFS and DFS spanning tree, but the difference is that the algorithm choose the shortest cost of a edge to traverse the graph. This implementation have a bool "salve" that enable the user save the MST in a external txt file. In this file contais the MST total cost, every vertex and their parent/level.
The Eccentricity is the longest shortest path between 2 vertex. In this implementation, it calculates the Eccentricity of a given vertex, so it just uses the Dijkstra algorithm and pick up the longest distance in the distancia vector(Vector that contains the information of every distance from start vertex).
The Bipartido (Bipartite) function return trues if the graph is possible to became bipartite, so, it runs a BFS through every vertex non colored in the graph, and try to color it with 2 colors. If it's possible, returns true.
This is a common problem that you can check the maximum number of matchings in a bipartite graph. The algorithm used was developed by John Hopcroft and Richard Karp. So, it returns the number of maximum matchings and, if the user wants, it can return every matches founded.
This is an algorithm similar to Dijkstra, but it works if the graph has edges with negative weights. The implementation of Bellman Ford was optimized, them it takes O(nm) for one run of the algorithm. But, it was required to run the algorithm |V| times, so, the real complexity of this implementation is O(|V|nm), where |V| and n are the same thing. The return of this function (if the user wants) is a Matrix that represents the distances founded in the bellman-ford run, where distance[i][j] represents the distance of the vertex i to the vertex j. Also this function, can detect if the graph has negative cycles in a path.
The colaboradores.cpp have the same implementation of the graph.cpp, but the data structure uses strings instead of integers. That's why one of the cases given by our professor had this requirement.
"Below you can see all the case studies used"
- Unweighted graph:
- Weighted graph:
- Bipartite graph:
- Weighted graph (negative weights):