12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696 |
- /*!
- Temelia - Graph algorithms implementation source file
- Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia)
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/graph.h"
- #include "include/vector.h"
- #include "include/queue.h"
- #include "include/pair.h"
- #include "include/sort.h"
- #include "include/heap.h"
- #include <stdlib.h>
- struct _graph_t
- {
- /*! Maximum number of vertices */
- unsigned int size;
- /*! Array of vertices */
- vector_t vertices;
- /*! Graph context */
- void *graph;
- /*! Vertex delete function */
- void (*vertex_delete)(vertex_t);
- /*! Edge delete function */
- void(*edge_delete)(edge_t);
- /*! Pointer to the graph implementation */
- graph_implementation_t implementation;
- };
- // === Private functions declaration ===
- /*!
- * @brief DFS travel starting from node.
- * Complexity O(V)
- *
- * @param Graph
- * @param Node identifier
- */
- static void _graph_dfs(graph_t graph, unsigned int node);
- /*!
- * @brief BFS travel.
- * Complexity O(V)
- *
- * @param Graph
- * @param Node identifier
- */
- static void _graph_bfs(graph_t graph, unsigned int node);
- /*!
- * @brief Time variable, used to synchronize operations.
- * Library doesn't export it because user shouldn't care about this variable.
- */
- static unsigned int current_time = 0;
- /*!
- * @brief Resets parameters of all vertices to their default value :
- * 1. unvisited
- * 2. colored with WHITE
- * 3. parent nil (-1)
- * 4. time_start and time_travel 0
- * Complexity O(V)
- *
- * @param Graph
- */
- static void _graph_reset_vertices(graph_t graph);
- /*!
- * @brief Core function for finding articulation points. It's based on DFS and compares times
- * when vertices are discovered in order to find the cut-vertices.
- * Complexity O(E/V))
- *
- * @param Graph
- * @param Current node
- * @param Color array
- * @param Time start array
- * @param Low time array
- * @param Parent array
- * @param Cut-vertex array. A vertex v is cut-vertex only if cut_vertex[v] = 1
- */
- unsigned int _articulation_points_travel(graph_t graph, unsigned int u,
- int *color, unsigned int *start, unsigned int *low,
- unsigned int *parent, int *cut_vertex);
- /*!
- * @brief Modified DFS travel used to find cycles contained by a graph.
- * Complexity O(V)
- *
- * @param Graph
- * @param Current node
- * @param Linked list where the next cycle is stored
- * @param Pointer to parent
- * @param Pointer to color
- * @param Pointer to visited
- * */
- static void _cycles_travel(graph_t graph, unsigned int current_node,
- linked_list_t current_cycles, unsigned int *parent, int *color,
- int *visited);
- /*!
- * @brief Rebuilds the path from current_node to next_node, basing on parents vector.
- * Complexity O(V)
- *
- * @param Current node identifier
- * @param Next node identifier
- * @param Parent array
- * @param Linked list where the cycle will be stored
- */
- static void _rebuild_cycle(unsigned int current_node, unsigned int next_node,
- unsigned int *parent, linked_list_t small_cycle);
- /*!
- * @brief Comparison function used by Kruskal's algorithm to compare set nodes.
- * @param First node identifier.
- * @param Second node identifier.
- */
- static int _compare_nodes_unsigned(void *x, void *y, void *context);
- /*!
- * @brief Internal function comparing time of two unsigned int vertex identifiers.
- */
- static int _compare_nodes_strongly_connected_components(void *x, void *y,
- void *context);
- /*!
- * @brief Comparison function used by Dijkstra's algorithm. It uses as context the distance vector.
- * @param First vertex identifier.
- * @param Second vertex identifier.
- */
- static int _compare_dijkstra(void *x, void *y, void *context);
- /*!
- * @brief Comparison function used by Prim's algorithm. It uses as context a pointer to minimum weights.
- * @param First vertex identifier
- * @param Second vertex identifier
- */
- static int _compare_prim(void *x, void *y, void *context);
- /*!
- * @brief Comparison function used by Kruskal's algorithm to sort edges by their cost.
- * @param First edge reference
- * @param Second edge reference
- */
- static int _compare_edges_kruskal(void *x, void *y, void *context);
- /*!
- * @brief Comparison function used by Kruskal's algorithm to compare set nodes.
- * @param First node identifier
- * @param Second node identifier
- */
- static int _compare_nodes_kruskal(void *x, void *y, void *context);
- /*!
- * @brief Sets the flow matrix keys to 0 double value.
- * Complexity O(V*V)
- *
- * @param Flow matrix
- */
- static void _init_flow(matrix_t flow);
- /*!
- * @brief Returns the minimum flow over a path in graph.
- * Complexity O(V)
- *
- * @param Graph
- * @param Flow matrix
- * @param Path list
- */
- static double _min_flow_path(graph_t graph, matrix_t max_flow,
- linked_list_t path);
- /*!
- * @brief Computes max_flow using DFS travel - used by Ford-Fulkerson algorithm.
- * Complexity O(E*max_flow)
- *
- * @param Graph
- * @param Start node identifier - source; this variable is changing because DFS travels
- * the vertices in a recursive way
- * @param End node identifier - destination
- * @param Path, where the result is stored
- * @param Max flow matrix
- */
- static void _flow_dfs(graph_t graph, unsigned int current_node,
- unsigned int destination, linked_list_t path, matrix_t max_flow);
- /*!
- * @brief Computer max_flow using BFS travel - used by Edmonds-Karp algorithm.
- * Complexity O(V*E*E)
- *
- * @param Graph
- * @param Start node identifier - source
- * @param End node identifier - destination
- * @param Path, where the result is stored
- * @param Max flow matrix
- */
- static void _flow_bfs(graph_t graph, unsigned int source,
- unsigned int destination, linked_list_t path, matrix_t max_flow);
- /*!
- * @brief Iterates over a path and actualizes the flow on it; the function add the min_flow to
- * all the edges from the path.
- * Complexity O(V)
- *
- * @param Flow matrix
- * @param Path
- * @param Minimum flow value
- */
- static void _add_flow_on_path(matrix_t max_flow, linked_list_t path,
- double min_flow);
- /*!
- * @brief Returns the capacity of edge between vertices i and j.
- * Complexity O(1)
- *
- * @param Graph
- * @param First vertex identifier
- * @param Second vertex identifier
- */
- INLINE static double CAPACITY(graph_t graph, unsigned int i, unsigned int j);
- /*!
- * @brief Returns the flow of edge between vertices i and j.
- * Complexity O(1)
- *
- * @param Flow matrix
- * @param First vertex identifier
- * @param Second vertex identifier
- */
- INLINE static double FLOW(matrix_t max_flow, unsigned int i, unsigned int j);
- // === End ===
- graph_t graph_new(unsigned int max, graph_implementation_t implementation,
- void(*m_vertex_delete)(vertex_t), void(*m_edge_delete)(edge_t))
- {
- graph_t graph;
- LOGGER(
- "[graph new] max size %u, implementation %p, vertex destructor %p, edge destructor\n",
- max, implementation, m_vertex_delete, m_edge_delete);
- _ASSERT(max, <=, 0, INVALID_INPUT, NULL);
- _ASSERT(implementation, ==, NULL, NULL_POINTER, NULL);
- graph = (struct _graph_t *) _new(sizeof(struct _graph_t));
- graph->size = max;
- graph->implementation = implementation;
- graph->graph = graph->implementation->new_g(max);
- _ASSERT(graph->graph, ==, NULL, NULL_POINTER, NULL);
- graph->vertices = vector_new(max);
- _ASSERT(graph->vertices, ==, NULL, NULL_POINTER, NULL);
- if (m_vertex_delete)
- graph->vertex_delete = m_vertex_delete;
- else
- graph->vertex_delete = vertex_delete;
- if (m_edge_delete)
- graph->edge_delete = m_edge_delete;
- else
- graph->edge_delete = edge_delete;
- // free() is the default destructor
- if (graph->implementation->delete_vertex_context == NULL)
- graph->implementation->delete_vertex_context = (void(*)(void **)) free;
- return graph;
- }
- static void _graph_delete_edge(edge_t key, void *context)
- {
- ((void(*)(edge_t)) context)(key);
- }
- void graph_delete(graph_t graph)
- {
- unsigned int i;
- LOGGER("[graph delete] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- graph->implementation->iterate_edges(graph->graph, _graph_delete_edge,
- graph->edge_delete);
- graph->implementation->delete_g(graph->graph);
- for (i = 0; i < graph->size; i++)
- graph->vertex_delete(vector_get_key_at(graph->vertices, i));
- vector_delete(graph->vertices);
- graph->size = 0;
- _delete(graph);
- }
- unsigned int graph_add_vertex(graph_t graph, char *label, void *key)
- {
- unsigned int i, n;
- int empty_place = 0;
- vertex_t vertex;
- LOGGER("[graph add vertex] graph %p, label %s, key %p\n", graph, label, key);
- _ASSERT(graph, ==, NULL, NULL_POINTER, (unsigned int) -1);
- _ASSERT((unsigned int) vector_get_size(graph->vertices), >= , graph->size, FULL, (unsigned int) -1);
- vertex = vertex_new(label, (unsigned int) vector_get_size(graph->vertices), key);
- _ASSERT(vertex, ==, NULL, NULL_POINTER, -1);
- // Find an empty place to insert the vertex.
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- {
- if (vector_get_key_at(graph->vertices, i) == NULL)
- {
- vector_set_key_at(graph->vertices, i, vertex);
- empty_place = 1;
- break;
- }
- }
- if (empty_place)
- return i;
- // If no empty place found, add the vertex to the end
- vector_push_back(graph->vertices, vertex);
- return vector_get_size(graph->vertices) - 1;
- }
- vertex_t graph_remove_vertex(graph_t graph, unsigned int identifier)
- {
- vertex_t vertex;
- unsigned int i, n;
- LOGGER("[graph remove vertex] graph %p, vertex %u\n", graph, identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), EMPTY, NULL);
- vertex = vector_get_key_at(graph->vertices, identifier);
- vector_set_key_at(graph->vertices, identifier, NULL);
- if (graph->implementation->delete_vertex_edges)
- graph->implementation->delete_vertex_edges(graph->graph, identifier,
- graph->edge_delete);
- else
- {
- n = graph->size;
- for (i = 0; i < n; i++)
- {
- graph->edge_delete(graph->implementation->get_edge(graph->graph, i,
- identifier));
- graph->edge_delete(graph->implementation->get_edge(graph->graph,
- identifier, i));
- }
- }
- return vertex;
- }
- int graph_is_vertex(graph_t graph, unsigned int identifier)
- {
- LOGGER("[graph is vertex] graph %p, identifier %u\n", graph, identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, 0);
- return vector_get_key_at(graph->vertices, identifier) != NULL;
- }
- vertex_t graph_get_vertex(graph_t graph, unsigned int identifier)
- {
- LOGGER("[graph get vertex] graph %p, identifier %u\n", graph, identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);
- return vector_get_key_at(graph->vertices, identifier);
- }
- edge_t graph_get_edge(graph_t graph, unsigned int identifier1,
- unsigned int identifier2)
- {
- LOGGER("[graph get edge] graph %p, identifier1 %u, identifier2 %u\n",
- graph, identifier1, identifier2);
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(identifier1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);
- _ASSERT(identifier2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);
- return graph->implementation->get_edge(graph->graph, identifier1,
- identifier2);
- }
- void graph_add_edge(graph_t graph, unsigned int vertex1, unsigned int vertex2,
- double cost, char *label, void *key)
- {
- vertex_t m_vertex1, m_vertex2;
- edge_t edge;
- LOGGER(
- "[graph add edge] graph %p, identifier1 %u, identifier2 %u, cost %lf, label %s, key %p\n",
- graph, vertex1, vertex2, cost, label, key);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(vertex1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, );
- _ASSERT(vertex2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, );
- m_vertex1 = vector_get_key_at(graph->vertices, vertex1);
- m_vertex2 = vector_get_key_at(graph->vertices, vertex2);
- _ASSERT(m_vertex1, ==, NULL, NULL_POINTER,);
- _ASSERT(m_vertex2, ==, NULL, NULL_POINTER,);
- // Create an edge between the two vertices.
- edge = edge_new(m_vertex1, m_vertex2, cost, label, key);
- _ASSERT(edge, ==, NULL, NULL_POINTER,);
- graph->implementation->add_edge(graph->graph, vertex1, vertex2, edge);
- }
- edge_t graph_remove_edge(graph_t graph, unsigned int vertex1,
- unsigned int vertex2)
- {
- LOGGER("[graph remove edge] graph %p, identifier1 %u, identifier2 %u\n",
- graph, vertex1, vertex2);
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(vertex1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);
- _ASSERT(vertex2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);
- return graph->implementation->remove_edge(graph->graph, vertex1, vertex2);
- }
- int graph_is_edge(graph_t graph, unsigned int vertex1, unsigned int vertex2)
- {
- LOGGER("[graph is edge] graph %p, identifier1 %u, identifier2 %u\n", graph,
- vertex1, vertex2);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(vertex1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);
- _ASSERT(vertex2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);
- return graph->implementation->get_edge(graph->graph, vertex1, vertex2)
- != NULL;
- }
- int graph_is_empty(graph_t graph)
- {
- LOGGER("[graph is empty] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- return vector_get_size(graph->vertices) == 0;
- }
- unsigned int graph_get_size(graph_t graph)
- {
- unsigned int count = 0, i, n;
- LOGGER("[graph get size] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- if (vector_get_key_at(graph->vertices, i) != NULL)
- count++;
- return count;
- }
- unsigned int graph_get_dimension(graph_t graph)
- {
- unsigned int count = 0, i, j, n;
- LOGGER("[graph get dimension] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- if (graph->implementation->dimension)
- return graph->implementation->dimension(graph->graph);
- // dimension() not implemented, use default algorithm
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- for (j = 0; j < n; j++)
- if (graph->implementation->get_edge(graph->graph, i, j) != NULL)
- count++;
- return count;
- }
- unsigned int graph_vertex_degree(graph_t graph, unsigned int identifier)
- {
- unsigned int i, n, degree = 0;
- LOGGER("[graph vertex degree] graph %p, identifier %u\n", graph, identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);
- if (graph->implementation->vertex_degree)
- return graph->implementation->vertex_degree(graph->graph, identifier);
- // vertex_degree() not implemented, use default algorithm
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- {
- if (graph->implementation->get_edge(graph->graph, identifier, i))
- degree++;
- if (graph->implementation->get_edge(graph->graph, i, identifier))
- degree++;
- }
- return degree;
- }
- unsigned int graph_vertex_out_degree(graph_t graph, unsigned int identifier)
- {
- unsigned int i, n, out_degree = 0;
- LOGGER("[graph out vertex degree] graph %p, identifier %u\n", graph,
- identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(graph->implementation, ==, NULL, NULL_POINTER, -1);
- _ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);
- if (graph->implementation->vertex_out_degree)
- return graph->implementation->vertex_out_degree(graph->graph,
- identifier);
- // vertex_out_degree() not implemented, use default algorithm
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- if (graph->implementation->get_edge(graph->graph, identifier, i))
- out_degree++;
- return out_degree;
- }
- unsigned int graph_vertex_in_degree(graph_t graph, unsigned int identifier)
- {
- unsigned int i, n, in_degree = 0;
- LOGGER("[graph in vertex degree] graph %p, identifier %u\n", graph,
- identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(graph->implementation, ==, NULL, NULL_POINTER, -1);
- _ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);
- if (graph->implementation->vertex_in_degree)
- return graph->implementation->vertex_in_degree(graph->graph, identifier);
- // vertex_in_degree() not implemented, use default algorithm
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- if (graph->implementation->get_edge(graph->graph, i, identifier))
- in_degree++;
- return in_degree;
- }
- void graph_iterate_vertices(graph_t graph, void vertex_handler(vertex_t v,
- void *context), void *context)
- {
- unsigned int i, n;
- LOGGER(
- "[graph iterate vertices] graph %p, vertex handler %p, context %p\n",
- graph, vertex_handler, context);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(vertex_handler, ==, NULL, NULL_POINTER,);
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- if (vector_get_key_at(graph->vertices, i))
- vertex_handler(vector_get_key_at(graph->vertices, i), context);
- }
- void graph_iterate_edges(graph_t graph, void edge_handler(edge_t e,
- void *context), void *context)
- {
- LOGGER("[graph vertex degree] graph %p, edge handler %p, context %p\n",
- graph, edge_handler, context);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(edge_handler, ==, NULL, NULL_POINTER,);
- graph->implementation->iterate_edges(graph->graph, edge_handler, context);
- }
- void graph_transpose_graph(graph_t graph)
- {
- LOGGER("[graph transpose] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- graph->implementation->transpose(graph->graph);
- }
- void graph_dfs(graph_t graph, unsigned int start_vertex_identifier)
- {
- unsigned int node, nodes_number;
- LOGGER("[graph dfs] graph %p, start vertex %u\n", graph,
- start_vertex_identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, );
- graph_set_current_time(0);
- if (start_vertex_identifier == (unsigned int) -1)
- {
- nodes_number = vector_get_size(graph->vertices);
- for (node = 0; node < nodes_number; node++)
- _graph_dfs(graph, node);
- }
- else
- {
- _ASSERT(start_vertex_identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT,);
- _graph_dfs(graph, start_vertex_identifier);
- }
- }
- void graph_bfs(graph_t graph, unsigned int start_vertex_identifier)
- {
- unsigned int node, nodes_number;
- LOGGER("[graph bfs] graph %p, start vertex %u\n", graph,
- start_vertex_identifier);
- _ASSERT(graph, ==, NULL, NULL_POINTER, );
- graph_set_current_time(0);
- if (start_vertex_identifier == (unsigned int) -1)
- {
- nodes_number = vector_get_size(graph->vertices);
- for (node = 0; node < nodes_number; node++)
- _graph_bfs(graph, node);
- }
- else
- {
- _ASSERT(start_vertex_identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT,);
- _graph_bfs(graph, start_vertex_identifier);
- }
- }
- void graph_reset_vertices(graph_t graph)
- {
- LOGGER("[graph reset vertices] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _graph_reset_vertices(graph);
- }
- int graph_is_undirected(graph_t graph)
- {
- unsigned int i, j, n;
- edge_t u, v;
- LOGGER("[graph is undirected] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- n = vector_get_size(graph->vertices);
- // If there exists an edge from a node to itseft then it's
- // not undirected.
- for (i = 0; i < n; i++)
- if (graph_get_edge(graph, i, i))
- return 0;
- for (i = 0; i < n - 1; i++)
- {
- for (j = i + 1; j < n; j++)
- {
- u = graph_get_edge(graph, i, j);
- v = graph_get_edge(graph, j, i);
- // If there is a pair of NULL and not-NULL edges
- // then the graph_t is undirected
- if ((u && !v) || (v && !u))
- return 0;
- }
- }
- return 1;
- }
- void graph_set_current_time(unsigned int time)
- {
- LOGGER("[graph set current time] time %d\n", time);
- current_time = time;
- }
- int graph_get_current_time()
- {
- LOGGER("[graph get current time] time %d\n", current_time);
- return current_time;
- }
- void graph_dfs_edges_classification(graph_t graph)
- {
- unsigned int i, j, nodes_number, type;
- vertex_t u, v;
- void *context;
- LOGGER("[graph dfs edges classification] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER, );
- /*
- * Start a complete DFS travel in order to compute values,
- * requested by the classification.
- */
- graph_dfs(graph, -1);
- type = DFS_UNKNOWN_EDGE;
- nodes_number = vector_get_size(graph->vertices);
- for (i = 0; i < nodes_number; i++)
- {
- u = vector_get_key_at(graph->vertices, i);
- v = graph->implementation->first_vertex(graph->graph, i, &context);
- while (1)
- {
- if (v == NULL)
- break;
- j = vertex_get_identifier(v);
- if (i == j)
- type = DFS_BACK_EDGE;
- // t_start[u] < t_start[v] < t_stop[v] < t_stop[v]
- else if (vertex_get_time_start(u) < vertex_get_time_start(v)
- && vertex_get_time_stop(v) < vertex_get_time_stop(u))
- {
- // parent[v] = u => tree edge
- if (vertex_get_parent_identifier(v) == vertex_get_identifier(u))
- type = DFS_TREE_EDGE;
- // parent[v] != u => forward edge
- else
- type = DFS_FORWARD_EDGE;
- }
- // t_start[v] < t_start[u] < t_stop[u] < t_stop[v].
- else if (vertex_get_time_start(v) < vertex_get_time_start(u)
- && vertex_get_time_stop(u) < vertex_get_time_stop(v))
- type = DFS_BACK_EDGE;
- // t_start[v] < t_stop[v] < t_start[u] < t_stop[u].
- else if (vertex_get_time_stop(v) < vertex_get_time_start(u))
- type = DFS_CROSS_EDGE;
- edge_set_type(graph_get_edge(graph, i, j), type);
- v = graph->implementation->next_vertex(graph->graph, i, &context);
- }
- }
- }
- void graph_bfs_edges_classification(graph_t graph)
- {
- unsigned int i, j, k, nodes_number, type;
- vertex_t u, v;
- void *context;
- LOGGER("[graph bfs edges classification] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER, );
- /*
- * Start a complete BFS travel in order to compute values,
- * requested by the classification.
- */
- graph_bfs(graph, -1);
- type = BFS_UNKNOWN_EDGE;
- nodes_number = vector_get_size(graph->vertices);
- for (i = 0; i < nodes_number; i++)
- {
- u = vector_get_key_at(graph->vertices, i);
- v = graph->implementation->first_vertex(graph->graph, i, &context);
- while (1)
- {
- if (v == NULL)
- break;
- j = vertex_get_identifier(v);
- // u = parent[v]
- if (i == vertex_get_parent_identifier(v))
- type = BFS_TREE_EDGE;
- else
- {
- k = i;
- while (k != (unsigned) -1 && k != j)
- k = vertex_get_parent_identifier(vector_get_key_at(
- graph->vertices, k));
- if (k != (unsigned) -1)
- type = BFS_BACK_EDGE;
- // parent[..parent[u]] = v;
- else if (vertex_get_cost(v) <= (vertex_get_cost(u) + 1))
- type = BFS_CROSS_EDGE;
- }
- edge_set_type(graph_get_edge(graph, i, j), type);
- v = graph->implementation->next_vertex(graph->graph, i, &context);
- }
- }
- }
- void graph_connected_components(graph_t graph,
- linked_list_t connected_components, int check)
- {
- unsigned int nodes_number, node, it, current_time, max_time, this_time;
- vertex_t u;
- linked_list_t add;
- LOGGER(
- "[graph connected components] graph %p, connected components %p, check %d\n",
- graph, connected_components, (int) check);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(connected_components, ==, NULL, NULL_POINTER,);
- if (check)
- if (!graph_is_undirected(graph))
- return;
- graph_set_current_time(0);
- nodes_number = vector_get_size(graph->vertices);
- max_time = current_time = 0;
- for (node = 0; node < nodes_number; node++)
- {
- _graph_dfs(graph, node);
- /*
- * Find the maximum stop time in order to find a new connected component
- * of the current graph_t. It contains the vertices of which
- * t_start and t_stop is between current_time and max_time
- */
- for (it = 0; it < nodes_number; it++)
- {
- this_time = vertex_get_time_stop(vector_get_key_at(graph->vertices,
- it));
- if (max_time < this_time)
- max_time = this_time;
- }
- add = linked_list_new();
- for (it = 0; it < nodes_number; it++)
- {
- u = vector_get_key_at(graph->vertices, it);
- this_time = vertex_get_time_stop(u);
- if (this_time > current_time && this_time <= max_time)
- linked_list_push_back(add, (void *) it);
- }
- current_time = max_time;
- if (linked_list_get_size(add) > 0)
- linked_list_push_back(connected_components, add);
- else
- linked_list_delete(add);
- }
- }
- static void *key_at(void *data, int index)
- {
- return (void *) ((unsigned int *) data)[index];
- }
- static void set_key_at(void *data, int index, void *new_value)
- {
- ((unsigned int *) data)[index] = (unsigned int) new_value;
- }
- void graph_strongly_connected_components(graph_t graph,
- linked_list_t strongly_connected_components)
- {
- unsigned int *vertices, i, j, nodes_number, t_start, t_stop, aux;
- linked_list_t add;
- LOGGER("[graph strongly connected components] graph %p, list %p\n", graph,
- strongly_connected_components);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(strongly_connected_components, ==, NULL, NULL_POINTER,);
- // Make a complete DFS travel and sort the vertices after t_stop.
- graph_dfs(graph, -1);
- nodes_number = vector_get_size(graph->vertices);
- vertices = (unsigned int *) _new(nodes_number * sizeof(unsigned int));
- for (i = 0; i < nodes_number; i++)
- vertices[i] = i;
- quick_sort(vertices, nodes_number, key_at, set_key_at,
- _compare_nodes_strongly_connected_components, graph->vertices);
- graph_transpose_graph(graph);
- graph_set_current_time(0);
- _graph_reset_vertices(graph);
- for (i = 0; i < nodes_number; i++)
- {
- if (vertex_get_visited(vector_get_key_at(graph->vertices, i)))
- continue;
- t_start = graph_get_current_time();
- _graph_dfs(graph, vertices[i]);
- t_stop = graph_get_current_time();
- add = linked_list_new();
- for (j = 0; j < nodes_number; j++)
- {
- aux = vertex_get_time_stop(vector_get_key_at(graph->vertices, j));
- if (aux > t_start && aux <= t_stop)
- linked_list_push_back(add, (void *) j);
- }
- if (linked_list_get_size(add) > 0)
- linked_list_push_back(strongly_connected_components, add);
- else
- // Delete allocated memory in order to avoid memory leaks.
- linked_list_delete(add);
- }
- _delete(vertices);
- graph_transpose_graph(graph);
- }
- int graph_topological_sort(graph_t graph, linked_list_t sort)
- {
- unsigned int i, j, nodes_number;
- int ok, dead_lock;
- LOGGER("[graph topological sort] graph %p, list %p\n", graph, sort);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(sort, ==, NULL, NULL_POINTER, -1);
- _graph_reset_vertices(graph);
- nodes_number = vector_get_size(graph->vertices);
- while (1)
- {
- dead_lock = 1;
- for (i = 0; i < nodes_number; i++)
- {
- ok = 1;
- // Check if there is a vertex with 0 in-degree. I simulate
- // edges removing by visiting nodes.
- for (j = 0; j < nodes_number; j++)
- {
- if (!vertex_get_visited(vector_get_key_at(graph->vertices, j))
- && graph_is_edge(graph, j, i))
- {
- ok = 0;
- break;
- }
- }
- if (ok
- && !vertex_get_visited(
- vector_get_key_at(graph->vertices, i)))
- {
- // If vertex i has 0 in-degree then add it to
- // topological sort list and visit it.
- linked_list_push_back(sort, (void *) i);
- vertex_set_visited(vector_get_key_at(graph->vertices, i), 1);
- dead_lock = 0;
- }
- }
- if (linked_list_get_size(sort) == nodes_number)
- break;
- if (dead_lock)
- return -1;
- }
- graph_reset_vertices(graph);
- return 0;
- }
- int graph_bipartite(graph_t graph, linked_list_t first_set,
- linked_list_t second_set)
- {
- unsigned int i, j, n, ok;
- vertex_t vertex;
- void *context;
- LOGGER("[graph bipartite] graph %p, first set %p, second set %p\n", graph,
- first_set, second_set);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(first_set, ==, NULL, NULL_POINTER, -1);
- _ASSERT(second_set, ==, NULL, NULL_POINTER, -1);
- // Do a complete BFS travel.
- graph_bfs(graph, -1);
- n = vector_get_size(graph->vertices);
- // Check if all pairs of neighbors don't have even sum distance.
- for (i = 0; i < n - 1; i++)
- {
- vertex = graph->implementation->first_vertex(graph->graph, i, &context);
- ok = 1;
- while (1)
- {
- if (vertex == NULL)
- break;
- j = vertex_get_identifier(vertex);
- if (j > i)
- {
- if (!(vertex_get_cost(vector_get_key_at(graph->vertices, i))
- + vertex_get_cost(vector_get_key_at(graph->vertices, j))))
- ok = 0;
- }
- else
- {
- graph->implementation->delete_vertex_context(&context);
- break;
- }
- vertex = graph->implementation->next_vertex(graph->graph, i,
- &context);
- }
- if (!ok)
- return 1;
- }
- // For-each vertex in graph, if it's distance is odd add to A, else
- // add it to B.
- for (i = 0; i < n; i++)
- {
- if (((unsigned int) vertex_get_cost(vector_get_key_at(graph->vertices,
- i))) % 2)
- linked_list_push_back(first_set, (void *) i);
- else
- linked_list_push_back(second_set, (void *) i);
- }
- return 0;
- }
- unsigned int graph_diameter(graph_t graph, unsigned int *first_node,
- unsigned int *second_node)
- {
- unsigned int max1, max2, i, n, aux;
- LOGGER("[graph diameter] graph %p, first node %p, second node %p\n", graph,
- first_node, second_node);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(first_node, ==, NULL, NULL_POINTER, -1);
- _ASSERT(second_node, ==, NULL, NULL_POINTER, -1);
- // Make two BFS travels: first, starting from first node of graph_t
- // and the second, starting from a leaf node of the first travel.
- // Return the leaf nodes and the distance between them.
- _graph_reset_vertices(graph);
- _graph_bfs(graph, 0);
- n = vector_get_size(graph->vertices);
- max1 = max2 = 0;
- for (i = 0; i < n; i++)
- {
- aux = (unsigned int) vertex_get_cost(vector_get_key_at(graph->vertices,
- i));
- if (max1 < (unsigned int) aux)
- {
- max1 = aux;
- *first_node = i;
- }
- }
- _graph_reset_vertices(graph);
- _graph_bfs(graph, *first_node);
- for (i = 0; i < n; i++)
- {
- aux = (unsigned int) vertex_get_cost(vector_get_key_at(graph->vertices,
- i));
- if (max2 < (unsigned int) aux)
- {
- max2 = aux;
- *second_node = i;
- }
- }
- _graph_reset_vertices(graph);
- return MAX(max1, max2);
- }
- void graph_articulation_points(graph_t graph, linked_list_t articulation_points)
- {
- unsigned int i, n, *parent, *low, *start;
- int *color, *cut_vertex;
- LOGGER("[graph articulation points] graph %p, articulation points\n",
- graph, articulation_points);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(articulation_points, ==, NULL, NULL_POINTER,);
- n = vector_get_size(graph->vertices);
- parent = (unsigned int *) _new(n * sizeof(unsigned int));
- low = (unsigned int *) _new(n * sizeof(unsigned int));
- start = (unsigned int *) _new(n * sizeof(unsigned int));
- color = (int *) _new(n * sizeof(int));
- cut_vertex = (int *) _new(n * sizeof(int));
- for (i = 0; i < n; i++)
- {
- parent[i] = (unsigned int) -1;
- low[i] = 0;
- start[i] = 0;
- cut_vertex[i] = 0;
- color[i] = WHITE;
- }
- for (i = 0; i < n; i++)
- {
- if (color[i] == WHITE)
- {
- if (_articulation_points_travel(graph, i, color, start, low,
- parent, cut_vertex) > 1)
- cut_vertex[i] = 1;
- else
- cut_vertex[i] = 0;
- }
- }
- for (i = 0; i < n; i++)
- if (cut_vertex[i])
- linked_list_push_back(articulation_points, (void *) i);
- _delete(parent);
- _delete(low);
- _delete(start);
- _delete(color);
- _delete(cut_vertex);
- }
- static void _graph_bridges_edges_handler(edge_t edge, void *context)
- {
- int **_bridges = (int **) context;
- _bridges[vertex_get_identifier(edge_get_vertex1(edge))][vertex_get_identifier(
- edge_get_vertex2(edge))] = 1;
- }
- void graph_bridges(graph_t graph, linked_list_t bridges)
- {
- /*
- * This algorithm is based on observation : an edge is a bridge if and only if
- * it's not part of a simple cycle in given graph_t.
- */
- linked_list_t cycles;
- linked_list_iterator_t it_list, it;
- unsigned int i, j, n;
- int **_bridges;
- LOGGER("[graph bridges] graph %p, bridges %p\n", graph, bridges);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(bridges, ==, NULL, NULL_POINTER,);
- cycles = linked_list_new();
- n = vector_get_size(graph->vertices);
- _bridges = (int **) _new(n * sizeof(int *));
- for (i = 0; i < n; i++)
- {
- _bridges[i] = (int *) _new(n * sizeof(int));
- for (j = 0; j < n; j++)
- _bridges[i][j] = 0;
- }
- // This function guarantees O(E) complexity
- graph->implementation->iterate_edges(graph->graph,
- _graph_bridges_edges_handler, _bridges);
- graph_cycles(graph, cycles);
- /*
- * 1. For-each cycle execute :
- * 2. For-each edge (u, v) from current cycle remove (u, v) from bridges list.
- */
- for (it_list = linked_list_get_begin(cycles); it_list != NULL; it_list
- = linked_list_iterator_get_next(it_list))
- {
- i = (unsigned int) linked_list_iterator_get_key(linked_list_get_begin(
- ((linked_list_t) linked_list_iterator_get_key(it_list))));
- j = (unsigned int) linked_list_iterator_get_key(linked_list_get_end(
- ((linked_list_t) linked_list_iterator_get_key(it_list))));
- _bridges[i][j] = _bridges[j][i] = 0;
- for (it = linked_list_get_begin(
- ((linked_list_t) linked_list_iterator_get_key(it_list))); linked_list_iterator_get_next(
- it) != NULL;)
- {
- i = (unsigned int) linked_list_iterator_get_key(it);
- it = linked_list_iterator_get_next(it);
- j = (unsigned int) linked_list_iterator_get_key(it);
- _bridges[i][j] = _bridges[j][i] = 0;
- }
- linked_list_delete(linked_list_iterator_get_key(it_list));
- }
- linked_list_delete(cycles);
- for (i = 0; i < n - 1; i++)
- {
- for (j = i + 1; j < n; j++)
- {
- if (_bridges[i][j])
- linked_list_push_back(bridges, pair_new((void *) i, (void *) j));
- }
- _delete(_bridges[i]);
- }
- _delete(_bridges[n - 1]);
- _delete(_bridges);
- }
- void graph_biconex_components(graph_t graph, linked_list_t biconex_components)
- {
- /*
- * The algorithm chosen for finding the biconex components is:
- * 1. Find the articulation points.
- * 2. Remove the articulation points from the graph.
- * 3. Find the connected components of the graph_t and put them into the given variable.
- * 4. Build the biconex components by adding the articulation points to the
- * connected components calculated above. Also, between two articulation points there is
- * a biconex component.
- */
- linked_list_t cut_vertex, connected_components;
- linked_list_iterator_t it, it_cc, it_cv;
- vertex_t vertex;
- void *copy, *context;
- LOGGER("[graph biconex components] graph %p, biconex components %p\n",
- graph, biconex_components);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(biconex_components, ==, NULL, NULL_POINTER,);
- cut_vertex = linked_list_new();
- graph_articulation_points(graph, cut_vertex);
- // Make a safe copy of initial adjacency matrix.
- copy = graph->implementation->store(graph->graph);
- // Remove cut vertices from graph_t.
- for (it = linked_list_get_begin(cut_vertex); it != NULL; it
- = linked_list_iterator_get_next(it))
- {
- vertex = graph->implementation->first_vertex(graph->graph,
- (unsigned int) linked_list_iterator_get_key(it), &context);
- while (1)
- {
- if (vertex == NULL)
- break;
- graph_remove_edge(graph,
- (unsigned int) linked_list_iterator_get_key(it),
- vertex_get_identifier(vertex));
- graph_remove_edge(graph, vertex_get_identifier(vertex),
- (unsigned int) linked_list_iterator_get_key(it));
- vertex = graph->implementation->next_vertex(graph->graph,
- (unsigned int) linked_list_iterator_get_key(it), &context);
- }
- }
- connected_components = linked_list_new();
- graph_connected_components(graph, connected_components, 0);
- for (it = linked_list_get_begin(connected_components); it != NULL; it
- = linked_list_iterator_get_next(it))
- {
- // linked_list_iterator_get_key(NULL, it, 0) represents a connected component.
- // it_cc = iterator on connected component nodes.
- // it_cv = iterator on cut vertices.
- // Add articulation points.
- for (it_cc = linked_list_get_begin(
- ((linked_list_t) linked_list_iterator_get_key(it))); it_cc
- != NULL; it_cc = linked_list_iterator_get_next(it_cc))
- {
- for (it_cv = linked_list_get_begin(cut_vertex); it_cv != NULL; it_cv
- = linked_list_iterator_get_next(it_cv))
- if (graph->implementation->get_edge(copy,
- (unsigned int) linked_list_iterator_get_key(it_cc),
- (unsigned int) linked_list_iterator_get_key(it_cv))
- && linked_list_iterator_get_key(it_cc)
- != linked_list_iterator_get_key(it_cv)
- && !linked_list_search_key(
- linked_list_iterator_get_key(it),
- linked_list_iterator_get_key(it_cv),
- _compare_nodes_unsigned, NULL))
- linked_list_push_front(linked_list_iterator_get_key(it),
- linked_list_iterator_get_key(it_cv));
- }
- linked_list_push_back(biconex_components, linked_list_iterator_get_key(
- it));
- }
- graph->implementation->delete_g(graph->graph);
- graph->graph = copy;
- linked_list_delete(connected_components);
- linked_list_delete(cut_vertex);
- }
- void graph_cycles(graph_t graph, linked_list_t cycles)
- {
- unsigned int i, n, *parent, current_node = 0;
- int *colour, *visited;
- LOGGER("[graph cycles] graph %p, cycles %p\n", graph, cycles);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(cycles, ==, NULL, NULL_POINTER,);
- n = vector_get_size(graph->vertices);
- parent = (unsigned int *) _new(n * sizeof(unsigned int));
- colour = (int *) _new(n * sizeof(int));
- visited = (int *) _new(n * sizeof(int));
- for (i = 0; i < n; i++)
- {
- parent[i] = (unsigned int) -1;
- colour[i] = WHITE;
- visited[i] = 0;
- }
- while (current_node != (unsigned int) -1)
- {
- _cycles_travel(graph, current_node, cycles, parent, colour, visited);
- current_node = (unsigned int) -1;
- // Find the first unvisited vertex and start new DFS travel from it.
- for (i = 0; i < n; i++)
- {
- if (!visited[i])
- {
- current_node = i;
- break;
- }
- }
- }
- _delete(parent);
- _delete(colour);
- _delete(visited);
- }
- void graph_dijkstra(graph_t graph, unsigned int source, vector_t distances,
- vector_t parents)
- {
- heap_t heap;
- unsigned int i, j, n;
- int *visited;
- double *edge1, *edge2, edge3;
- edge_t m_edge;
- void *context;
- LOGGER("[graph dijkstra] graph %p, source %u, distances %p, parents %p\n",
- graph, source, distances, parents);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(source, >= , graph->size, INVALID_INPUT,);
- _ASSERT(distances, ==, NULL, NULL_POINTER,);
- _ASSERT(parents, ==, NULL, NULL_POINTER,);
- n = vector_get_size(graph->vertices);
- visited = (int *) _new(n * sizeof(int));
- for (i = 0; i < n; i++)
- {
- *(double *) vector_get_key_at(distances, i) = TEMELIA_INFINITY;
- visited[i] = 0;
- }
- *(double *) vector_get_key_at(distances, source) = 0;
- heap = heap_new(n);
- for (i = 0; i < n; i++)
- heap_insert(heap, (void *) i, _compare_dijkstra, distances);
- while (!heap_is_empty(heap))
- {
- i = (unsigned int) heap_get_min_key(heap);
- heap_remove_min_key(heap, _compare_dijkstra, distances);
- visited[i] = 1;
- m_edge = graph->implementation->first_edge(graph->graph, i, &context);
- while (1)
- {
- if (m_edge == NULL)
- break;
- j = vertex_get_identifier(edge_get_vertex2(m_edge));
- edge1 = vector_get_key_at(distances, j);
- edge2 = vector_get_key_at(distances, i);
- edge3 = edge_get_cost(m_edge);
- if (i != j && (*edge1 > *edge2 + edge3))
- {
- *edge1 = *edge2 + edge3;
- vector_set_key_at(parents, j, (void *) i);
- heap_change_key_by_value(heap, (void *) j, (void *) j,
- _compare_dijkstra, distances);
- }
- m_edge
- = graph->implementation->next_edge(graph->graph, i,
- &context);
- }
- }
- heap_delete(heap);
- _delete(visited);
- }
- int graph_bellman_ford(graph_t graph, unsigned int source, vector_t distances,
- vector_t parents)
- {
- unsigned int i, j, k, n;
- double *edge1, *edge2, edge3;
- LOGGER(
- "[graph bellman ford] graph %p, source %u, distances %p, parents %p\n",
- graph, source, distances, parents);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(distances, ==, NULL, NULL_POINTER, -1);
- _ASSERT(parents, ==, NULL, NULL_POINTER, -1);
- n = vector_get_size(graph->vertices);
- for (i = 0; i < n; i++)
- {
- vector_set_key_at(parents, i, (void *) -1);
- *(double *) vector_get_key_at(distances, i) = TEMELIA_INFINITY;
- }
- *(double *) vector_get_key_at(distances, source) = 0;
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- for (k = 0; k < n; k++)
- {
- if (i == j)
- continue;
- edge1 = vector_get_key_at(distances, k);
- edge2 = vector_get_key_at(distances, j);
- edge3 = edge_get_cost(graph_get_edge(graph, j, k));
- if (*edge1 > *edge2 + edge3)
- {
- *edge1 = *edge2 + edge3;
- vector_set_key_at(parents, k, (void *) j);
- }
- }
- }
- }
- // If there exists an edge (i, j) such that distances[j] > distances[i] + graph_t[i][j]
- // then, in the graph_t, is a negative cycle.
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- if (graph_is_edge(graph, i, j))
- {
- if (*(double *) vector_get_key_at(distances, j)
- > *(double *) vector_get_key_at(distances, i)
- + edge_get_cost(graph_get_edge(graph, i, j)))
- return -1;
- }
- }
- }
- return 0;
- }
- void graph_floyd_warshall(graph_t graph, matrix_t distances, matrix_t parents)
- {
- unsigned int i, j, k, n;
- double *edge1, *edge2, *edge3;
- LOGGER("[graph floyd warshall] graph %p, distances %p, parents %p\n",
- graph, distances, parents);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(distances, ==, NULL, NULL_POINTER,);
- _ASSERT(parents, ==, NULL, NULL_POINTER,);
- n = vector_get_size(graph->vertices);
- // The initial distance matrix is equal with the graph_t cost matrix.
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- if (i == j || !graph_is_edge(graph, i, j))
- {
- matrix_set_key_at(parents, i, j, (void *) -1);
- if (i != j)
- *(double *) matrix_get_key_at(distances, i, j)
- = TEMELIA_INFINITY;
- else
- *(double *) matrix_get_key_at(distances, i, j) = 0;
- }
- else
- {
- matrix_set_key_at(parents, i, j, (void *) i);
- *(double *) matrix_get_key_at(distances, i, j) = edge_get_cost(
- graph_get_edge(graph, i, j));
- }
- }
- }
- // Dynamic programming over k.
- for (k = 0; k < n; k++)
- {
- // For-each edge, relax it and adjust : distances and parents.
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- if (i != j)
- {
- edge1 = matrix_get_key_at(distances, i, j);
- edge2 = matrix_get_key_at(distances, i, k);
- edge3 = matrix_get_key_at(distances, k, j);
- if (*edge2 != TEMELIA_INFINITY && *edge3
- != TEMELIA_INFINITY)
- {
- if (*edge1 > *edge2 + *edge3)
- {
- *edge1 = *edge2 + *edge3;
- matrix_set_key_at(parents, i, j, matrix_get_key_at(
- parents, k, j));
- }
- }
- }
- }
- }
- }
- }
- int graph_johnson(graph_t graph, matrix_t distances, matrix_t parents)
- {
- /*
- * The Johnson algorithm computes the minimum distances between all the vertices in the graph_t.
- * 1. First, a new node Q is added to the graph_t, connected by zero-weight edge to each other node.
- * 2. Second, the Bellman-Ford algorithm is used, starting from the new vertex Q, to find for-each
- * vertex v the least weight h(v) of a path from Q to v. If this step detects a negative cycle, the
- * algorithm is terminated.
- * 3. The next edges of original graph_t are reweighted using the values computed by the Bellman-Ford
- * algorithm : an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) - h(v).
- * (graph_t becomes normalized).
- * 4. Finally, for each node s, Dijkstra's algorithm is used to find the shortest paths from s to
- * each other vertex in reweighted graph_t.
- * 5. For-each edge (u,v) add h(v) - h(u) to obtain the minimum distance.
- * (graph_t becomes unnormalized).
- */
- unsigned int i, j, n, q;
- vector_t bf_h, bf_p, v_distances, v_parents;
- edge_t edge;
- void *context;
- LOGGER("[graph johnson] graph %p, distances %p, parents %p\n", graph,
- distances, parents);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(distances, ==, NULL, NULL_POINTER, -1);
- _ASSERT(matrix_get_rows_number(distances), !=, matrix_get_columns_number(distances), INVALID_INPUT, -1);
- _ASSERT(parents, ==, NULL, NULL_POINTER, -1);
- _ASSERT(matrix_get_rows_number(parents), !=, matrix_get_columns_number(parents), INVALID_INPUT, -1);
- n = graph_get_size(graph);
- q = graph_add_vertex(graph, NULL, NULL);
- _ASSERT(q, ==, -1, FULL, -1);
- for (i = 0; i < n; i++)
- graph_add_edge(graph, q, i, 0, NULL, NULL);
- bf_p = vector_new(n + 1);
- bf_h = vector_new(n + 1);
- for (i = 0; i < n + 1; i++)
- vector_push_back(bf_h, _new(sizeof(double)));
- _ASSERT(graph_bellman_ford(graph, q, bf_h, bf_p), ==, -1, INVALID_INPUT, -1);
- // Normalize graph_t.
- for (i = 0; i < n; i++)
- {
- edge = graph->implementation->first_edge(graph->graph, i, &context);
- while (1)
- {
- if (edge == NULL)
- break;
- j = vertex_get_identifier(edge_get_vertex2(edge));
- if (i != j)
- edge_set_cost(edge, edge_get_cost(edge)
- + *(double *) vector_get_key_at(bf_h, i)
- - *(double *) vector_get_key_at(bf_h, j));
- matrix_set_key_at(parents, i, j, (void *) -1);
- *(double *) matrix_get_key_at(distances, i, j) = TEMELIA_INFINITY;
- edge = graph->implementation->next_edge(graph->graph, i, &context);
- }
- }
- v_distances = vector_new(n + 1);
- v_parents = vector_new(n + 1);
- for (i = 0; i < n + 1; i++)
- {
- vector_push_back(v_distances, _new(sizeof(double)));
- vector_push_back(v_parents, (void *) -1);
- }
- // Apply Dijkstra's algorithm for each vertex in graph
- for (i = 0; i < n; i++)
- {
- graph_dijkstra(graph, i, v_distances, v_parents);
- for (j = 0; j < n; j++)
- {
- matrix_set_key_at(parents, i, j, (void *) vector_get_key_at(
- v_parents, j));
- *(double *) matrix_get_key_at(distances, i, j)
- = *(double *) vector_get_key_at(v_distances, j)
- + *(double *) vector_get_key_at(bf_h, j)
- - *(double *) vector_get_key_at(bf_h, i);
- }
- }
- // Re normalize
- for (i = 0; i < n; i++)
- {
- edge = graph->implementation->first_edge(graph->graph, i, &context);
- while (1)
- {
- if (edge == NULL)
- break;
- j = vertex_get_identifier(edge_get_vertex2(edge));
- if (i != j)
- edge_set_cost(edge, edge_get_cost(edge)
- + *(double *) vector_get_key_at(bf_h, j)
- - *(double *) vector_get_key_at(bf_h, i));
- edge = graph->implementation->next_edge(graph->graph, i, &context);
- }
- }
- for (i = 0; i < n + 1; i++)
- {
- _delete(vector_get_key_at(bf_h, i));
- _delete(vector_get_key_at(v_distances, i));
- }
- vector_delete(bf_h);
- vector_delete(bf_p);
- vector_delete(v_distances);
- vector_delete(v_parents);
- return 0;
- }
- double graph_prim(graph_t graph, unsigned int start_vertex_identifier,
- linked_list_t minimum_spanning_tree)
- {
- /*
- * Prim's algorithm finds the minimum spanning tree for connected weighted graph_t.
- * 1. Put all vertices in queue Q.
- * 2. For-each vertex u in graph_t, make key[u] <- INFINITY.
- * 3. key[root] <- 0, parent[root] <- NIL.
- * 4. while queue Q is not empty execute :
- * 5. extract the vertex with minimum key, let it be u.
- * 6. for-each vertex v such that v is neighbor with u execute :
- * 7. if v is in queue Q and weight(u, v) < key[v] execute :
- * 8. parent[v] <- u, key[v] <- weight(u, v).
- */
- heap_t queue;
- unsigned int i, j, n, *parents;
- double *keys, cost;
- int *visited;
- edge_t m_edge;
- void *context;
- LOGGER(
- "[graph prim] graph %p, start vertex %u, minimum spanning tree %p\n",
- graph, start_vertex_identifier, minimum_spanning_tree);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(minimum_spanning_tree, ==, NULL, INVALID_INPUT, -1);
- n = vector_get_size(graph->vertices);
- _ASSERT(start_vertex_identifier, >=, n, INVALID_INPUT, -1);
- queue = heap_new(n);
- keys = (double *) _new(n * sizeof(double));
- parents = (unsigned int *) _new(n * sizeof(unsigned int));
- visited = (int *) _new(n * sizeof(int));
- for (i = 0; i < n; i++)
- {
- keys[i] = TEMELIA_INFINITY;
- visited[i] = 0;
- parents[i] = (unsigned int) -1;
- }
- keys[start_vertex_identifier] = 0;
- for (i = 0; i < n; i++)
- heap_insert(queue, (void *) i, _compare_prim, keys);
- while (!heap_is_empty(queue))
- {
- i = (unsigned int) heap_get_min_key(queue);
- visited[i] = 1;
- heap_remove_min_key(queue, _compare_prim, keys);
- m_edge = graph->implementation->first_edge(graph->graph, i, &context);
- while (1)
- {
- if (m_edge == NULL)
- break;
- j = vertex_get_identifier(edge_get_vertex2(m_edge));
- if (!visited[j] && edge_get_cost(m_edge) < keys[j])
- {
- edge_debug(m_edge, NULL);
- parents[j] = i;
- keys[j] = edge_get_cost(m_edge);
- heap_change_key_by_value(queue, (void *) j, (void *) j,
- _compare_prim, keys);
- }
- m_edge
- = graph->implementation->next_edge(graph->graph, i,
- &context);
- }
- }
- cost = 0;
- for (i = 0; i < n; i++)
- {
- cost += keys[i];
- linked_list_push_back(minimum_spanning_tree, pair_new((void *) i,
- (void *) parents[i]));
- }
- heap_delete(queue);
- _delete(keys);
- _delete(parents);
- _delete(visited);
- return cost;
- }
- double graph_kruskal(graph_t graph, unsigned int start_vertex_identifier,
- linked_list_t *minimum_spanning_tree)
- {
- /*
- * Kruskal's algorithm finds a minimum spanning tree for a connected weighted graph_t.
- * 1. create a forest F (a set of trees), where each vertex in the graph_t is a separate tree
- * 2. create a set S containing all the edges in the graph
- * 3. while S is nonempty
- * 4. remove an edge with minimum weight from S
- * 5. if that edge connects two different trees, then add it to the forest,
- * combining two trees into a single tree
- * 6. otherwise discard that edge
- */
- unsigned int i, j, k, n, k1, k2;
- linked_list_t edges;
- linked_list_iterator_t it;
- linked_list_t *partial_trees;
- int ok;
- double cost;
- edge_t m_edge;
- void *context;
- LOGGER(
- "[graph kruskal] graph %p, start vertex %u, minimum spanning tree %p\n",
- graph, start_vertex_identifier, minimum_spanning_tree);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- _ASSERT(minimum_spanning_tree, ==, NULL, NULL_POINTER, -1);
- n = vector_get_size(graph->vertices);
- _ASSERT(start_vertex_identifier, >=, n, INVALID_INPUT, -1);
- edges = linked_list_new();
- partial_trees = (linked_list_t *) _new(n * sizeof(linked_list_t));
- for (i = 0; i < n; i++)
- partial_trees[i] = linked_list_new();
- linked_list_push_back(partial_trees[0], NULL);
- // Add all the graph_t's edges in the list and sort it.
- for (i = 0; i < n - 1; i++)
- {
- m_edge = graph->implementation->first_edge(graph->graph, i, &context);
- while (1)
- {
- if (m_edge == NULL)
- break;
- j = vertex_get_identifier(edge_get_vertex2(m_edge));
- if (j > i)
- {
- if (edge_get_cost(m_edge) < TEMELIA_INFINITY)
- linked_list_push_back(edges, m_edge);
- }
- m_edge
- = graph->implementation->next_edge(graph->graph, i,
- &context);
- }
- linked_list_push_back(partial_trees[i + 1], (void *) (i + 1));
- }
- // Sort edges by their cost.
- linked_list_sort(edges, _compare_edges_kruskal, NULL);
- cost = 0;
- for (it = linked_list_get_begin(edges); it != NULL; it
- = linked_list_iterator_get_next(it))
- {
- i = vertex_get_identifier(edge_get_vertex1(
- linked_list_iterator_get_key(it)));
- j = vertex_get_identifier(edge_get_vertex2(
- linked_list_iterator_get_key(it)));
- ok = 1;
- k1 = k2 = -1;
- for (k = 0; k < n; k++)
- {
- if (!partial_trees[k])
- continue;
- if (linked_list_search_key(partial_trees[k], (void *) i,
- _compare_nodes_kruskal, NULL) == NULL
- && linked_list_search_key(partial_trees[k], (void *) j,
- _compare_nodes_kruskal, NULL) != NULL)
- k1 = k;
- if (linked_list_search_key(partial_trees[k], (void *) j,
- _compare_nodes_kruskal, NULL) == NULL
- && linked_list_search_key(partial_trees[k], (void *) i,
- _compare_nodes_kruskal, NULL) != NULL)
- k2 = k;
- if (linked_list_search_key(partial_trees[k], (void *) i,
- _compare_nodes_kruskal, NULL) != NULL
- && linked_list_search_key(partial_trees[k], (void *) j,
- _compare_nodes_kruskal, NULL) != NULL)
- {
- ok = 0;
- break;
- }
- }
- if (ok)
- {
- cost += edge_get_cost(graph_get_edge(graph, i, j));
- linked_list_iterator_set_next(
- linked_list_get_end(partial_trees[k1]),
- linked_list_get_begin(partial_trees[k2]));
- linked_list_set_end(partial_trees[k1], linked_list_get_end(
- partial_trees[k2]));
- _delete(partial_trees[k2]);
- partial_trees[k2] = NULL;
- }
- }
- for (i = 0; i < n; i++)
- if (partial_trees[i] != NULL)
- *minimum_spanning_tree = partial_trees[i];
- _delete(partial_trees);
- linked_list_delete(edges);
- return cost;
- }
- double graph_ford_fulkerson(graph_t graph, unsigned int source,
- unsigned int destination, matrix_t max_flow)
- {
- unsigned int n = vector_get_size(graph->vertices);
- linked_list_t path;
- double _max_flow, _min_flow;
- LOGGER(
- "[graph ford fulkerson] graph %u, source %u, destination %u, flow matrix %p\n",
- graph, source, destination, max_flow);
- _ASSERT(graph, ==, NULL, NULL_POINTER, 0);
- _ASSERT(source, >=, n, INVALID_INPUT, 0);
- _ASSERT(destination, >=, n, INVALID_INPUT, 0);
- _ASSERT(max_flow, ==, NULL, NULL_POINTER, 0);
- _ASSERT(matrix_get_columns_number(max_flow), !=, matrix_get_rows_number(max_flow), INVALID_INPUT, 0);
- // Initialize the flow matrix with 0 value.
- _init_flow(max_flow);
- // Initial max flow is 0.
- _max_flow = 0;
- /*
- * The Ford Fulkerson algorithm is :
- * 1. while there is a path from source to destination,
- * such that the flow on that path may increase execute :
- * 2. increase the flow on computed path at step 1.
- * For finding a "good" path, i use DFS search.
- */
- while (1)
- {
- // Initialization for DFS.
- path = linked_list_new();
- _graph_reset_vertices(graph);
- // Find a valid path from source to destination.
- _flow_dfs(graph, source, destination, path, max_flow);
- // End the algorithm if no path is found.
- if (linked_list_get_size(path) == 0)
- {
- linked_list_delete(path);
- break;
- }
- // Compute the min flow on this path
- _min_flow = _min_flow_path(graph, max_flow, path);
- // Add the min flow calculated above to the max_flow matrix
- _add_flow_on_path(max_flow, path, _min_flow);
- // Reset variables: vertices and path list
- _graph_reset_vertices(graph);
- linked_list_delete(path);
- // Add the min-flow to max-flow, in order to return the desired result
- _max_flow += _min_flow;
- }
- return _max_flow;
- }
- double graph_edmonds_karp(graph_t graph, unsigned int source,
- unsigned int destination, matrix_t max_flow)
- {
- unsigned int n = vector_get_size(graph->vertices);
- linked_list_t path;
- double _max_flow, _min_flow;
- LOGGER(
- "[graph ford fulkerson] graph %u, source %u, destination %u, flow matrix %p\n",
- graph, source, destination, max_flow);
- _ASSERT(graph, ==, NULL, NULL_POINTER, 0);
- _ASSERT(source, >=, n, INVALID_INPUT, 0);
- _ASSERT(destination, >=, n, INVALID_INPUT, 0);
- _ASSERT(max_flow, ==, NULL, NULL_POINTER, 0);
- _ASSERT(matrix_get_columns_number(max_flow), !=, matrix_get_rows_number(max_flow), INVALID_INPUT, 0);
- // Initialize the flow matrix with 0 value.
- _init_flow(max_flow);
- // Initial max flow is 0.
- _max_flow = 0;
- /*
- * The Edmonds-Karp algorithm is :
- * 1. while there is a path from source to destination,
- * such that the flow on that path may increase execute :
- * 2. increase the flow on computed path at step 1.
- * For finding a "good" path, i use BFS search.
- */
- while (1)
- {
- // Initialization for BFS.
- path = linked_list_new();
- _graph_reset_vertices(graph);
- // Find a valid path from source to destination.
- _flow_bfs(graph, source, destination, path, max_flow);
- // End the algorithm if no path is found : path contains only
- // the destination vertex.
- if (linked_list_get_size(path) <= 1)
- {
- linked_list_delete(path);
- break;
- }
- // Compute the min flow on this path
- _min_flow = _min_flow_path(graph, max_flow, path);
- // If there is no flow, return.
- // Actually, the algorithm should never execute this break,
- // because _flow_BFS guarantees a "good" path; I wrote this
- // statement "just in case"
- if (_min_flow == 0)
- break;
- // Add the min flow calculated above to the max_flow matrix
- _add_flow_on_path(max_flow, path, _min_flow);
- // Reset variables: vertices and path list
- _graph_reset_vertices(graph);
- linked_list_delete(path);
- // Add the min-flow to max-flow, in order to return the desired result
- _max_flow += _min_flow;
- }
- return _max_flow;
- }
- // === Private functions implementation ===
- static void _graph_dfs(graph_t graph, unsigned int node)
- {
- unsigned int node_next, nodes_number;
- vertex_t vertex = vector_get_key_at(graph->vertices, node), vertex_next;
- void *context;
- // Return is the current node is not white or visited
- if (vertex_get_color(vertex) != WHITE || vertex_get_visited(vertex))
- return;
- // Change vertex color to GRAY.
- vertex_set_color(vertex, GRAY);
- // Visit the node by setting visited variable accordingly
- vertex_set_visited(vertex, 1);
- // Set the time current node was discovered.
- vertex_set_time_start(vertex, current_time++);
- nodes_number = vector_get_size(graph->vertices);
- vertex_next = graph->implementation->first_vertex(graph->graph, node,
- &context);
- while (1)
- {
- // No more neighbors
- if (vertex_next == NULL)
- break;
- node_next = vertex_get_identifier(vertex_next);
- // If 1, 2, 3 and 4 are true then next_node is a valid neighbor, from DFS point of view,
- // I continue the travel from it.
- // 1. node_next is a valid node in graph
- // 2. it's color is white
- // 3. it's not visited yet
- // 4. there is an edge between node and node next
- if (vertex_get_color(vertex_next) == WHITE && !vertex_get_visited(
- vertex_next))
- {
- vertex_set_parent_identifier(vertex_next, node);
- _graph_dfs(graph, node_next);
- }
- vertex_next = graph->implementation->next_vertex(graph->graph, node,
- &context);
- }
- // Finished traveling this node, set it's time stop and it's color to black
- vertex_set_time_stop(vertex, current_time++);
- // Set it's color to black (DFS finished visiting this node)
- vertex_set_color(vertex, BLACK);
- }
- static void _graph_bfs(graph_t graph, unsigned int node)
- {
- unsigned int nodes_number;
- void *context;
- queue_t queue;
- vertex_t vertex, vertex_next;
- vertex = vector_get_key_at(graph->vertices, node);
- // Returns if current node isn't white or visited
- if (vertex_get_color(vertex) != WHITE || vertex_get_visited(vertex))
- return;
- nodes_number = vector_get_size(graph->vertices);
- // Vertices queue can have maximum of nodes_number keys
- queue = queue_new(nodes_number);
- // In BFS cost represents the distance from root to current vertex
- // Root vertex has 0 cost and parent -1
- vertex_set_color(vertex, GRAY);
- vertex_set_cost(vertex, 0);
- vertex_set_parent_identifier(vertex, -1);
- vertex_set_visited(vertex, 1);
- // Put the first vertex in the queue.
- queue_push_back(queue, vertex);
- // 0. while queue is not empty execute
- // 1. extract a node from queue
- // 2. for each unvisited node, adjacent with extracted node, do :
- // 3. set new vertex parameters
- // 4. insert neighbor in queue
- while (!queue_is_empty(queue))
- {
- vertex = queue_get_front(queue);
- node = vertex_get_identifier(vertex);
- queue_pop_front(queue);
- vertex_set_time_start(vertex, current_time++);
- vertex_next = graph->implementation->first_vertex(graph->graph, node,
- &context);
- while (1)
- {
- if (vertex_next == NULL)
- break;
- // If the vertex exists, there is an edge from current node to it,
- // it's color is white and was not visited, then is eligible
- // to pushing back in the bfs travel queue.
- if (vertex_get_color(vertex_next) == WHITE && !vertex_get_visited(
- vertex_next))
- {
- // Push back in queue the next vertex
- queue_push_back(queue, vertex_next);
- // Set next vertex color to gray
- vertex_set_color(vertex_next, GRAY);
- // Set cost as 1 + cost(parent).
- vertex_set_cost(vertex_next, 1 + vertex_get_cost(vertex));
- // Set a link between vertex_next and vertex, by setting
- // vertex_next parent's identifier
- vertex_set_parent_identifier(vertex_next,
- vertex_get_identifier(vertex));
- // Set vertex as visited.
- vertex_set_visited(vertex_next, 1);
- }
- vertex_next = graph->implementation->next_vertex(graph->graph,
- node, &context);
- }
- // Finish BFS travel on this node.
- vertex_set_color(vertex, BLACK);
- vertex_set_time_stop(vertex, current_time++);
- }
- // Free the queue used by BFS.
- queue_delete(queue);
- }
- static void _graph_reset_vertices(graph_t graph)
- {
- unsigned int node, nodes_number;
- vertex_t vertex;
- nodes_number = vector_get_size(graph->vertices);
- for (node = 0; node < nodes_number; node++)
- {
- // For-each vertex in graph_t set their parameters to default value.
- vertex = vector_get_key_at(graph->vertices, node);
- vertex_set_color(vertex, WHITE);
- vertex_set_parent_identifier(vertex, -1);
- vertex_set_time_start(vertex, 0);
- vertex_set_time_stop(vertex, 0);
- vertex_set_visited(vertex, 0);
- }
- }
- unsigned int _articulation_points_travel(graph_t graph, unsigned int u,
- int *color, unsigned int *start, unsigned int *low,
- unsigned int *parent, int *cut_vertex)
- {
- unsigned int subtrees = 0, v;
- vertex_t vertex;
- void *context;
- color[u] = GRAY;
- start[u] = ++current_time;
- low[u] = start[u];
- vertex = graph->implementation->first_vertex(graph->graph, u, &context);
- while (1)
- {
- if (vertex == NULL)
- break;
- v = vertex_get_identifier(vertex);
- if (color[v] == WHITE)
- {
- parent[v] = u;
- _articulation_points_travel(graph, v, color, start, low, parent,
- cut_vertex);
- subtrees++;
- if (low[v] < low[u])
- low[u] = low[v];
- if (low[v] >= start[u])
- cut_vertex[u] = 1;
- }
- else if (color[v] == GRAY)
- {
- if (start[v] < low[u])
- low[u] = start[v];
- }
- vertex = graph->implementation->next_vertex(graph->graph, u, &context);
- }
- color[u] = BLACK;
- return subtrees;
- }
- static void _cycles_travel(graph_t graph, unsigned int current_node,
- linked_list_t current_cycles, unsigned int *parent, int *color,
- int *visited)
- {
- unsigned int next_node, n;
- linked_list_t small_cycle;
- vertex_t vertex;
- void *context;
- color[current_node] = GRAY;
- visited[current_node] = 1;
- n = vector_get_size(graph->vertices);
- vertex = graph->implementation->first_vertex(graph->graph, current_node,
- &context);
- while (1)
- {
- if (vertex == NULL)
- break;
- next_node = vertex_get_identifier(vertex);
- /*
- * If there are two vertices u and v such that :
- * 1. u and v are neighbors.
- * 2. u isn't the parent of v
- * 3. v is the next node in DFS travel, after visiting u.
- * 4. v is already visited.
- * Then u and v close a cycles.
- * Rebuild the path and add the new cycle to cycles list.
- */
- if (visited[next_node] && color[next_node] == GRAY && parent[next_node]
- != current_node)
- {
- small_cycle = linked_list_new();
- _rebuild_cycle(current_node, next_node, parent, small_cycle);
- if (linked_list_get_size(small_cycle) > 2)
- linked_list_push_back(current_cycles, small_cycle);
- else
- linked_list_delete(small_cycle);
- }
- vertex = graph->implementation->next_vertex(graph->graph, current_node,
- &context);
- }
- vertex = graph->implementation->first_vertex(graph->graph, current_node,
- &context);
- while (1)
- {
- if (vertex == NULL)
- break;
- next_node = vertex_get_identifier(vertex);
- if (color[next_node] == WHITE && !visited[next_node])
- {
- parent[next_node] = current_node;
- _cycles_travel(graph, next_node, current_cycles, parent, color,
- visited);
- }
- vertex = graph->implementation->next_vertex(graph->graph, current_node,
- &context);
- }
- color[current_node] = BLACK;
- }
- static void _rebuild_cycle(unsigned int current_node, unsigned int next_node,
- unsigned int *parent, linked_list_t small_cycle)
- {
- if (current_node == next_node)
- {
- linked_list_push_back(small_cycle, (void *) current_node);
- return;
- }
- _rebuild_cycle(parent[current_node], next_node, parent, small_cycle);
- linked_list_push_back(small_cycle, (void *) current_node);
- }
- static int _compare_nodes_unsigned(void *x, void *y, void *context)
- {
- return (int) ((unsigned long) x - (unsigned long) y);
- }
- static int _int_compare(void *x, void *y, void *context)
- {
- return (unsigned int) x - (unsigned int) y;
- }
- static int _compare_nodes_strongly_connected_components(void *x, void *y,
- void *context)
- {
- // Compare the two vertices after their t_stop parameter.
- // The context (vector of vertices) is stored in the global variable.
- return vertex_get_time_stop(vector_get_key_at((vector_t) context,
- (unsigned int) y)) - vertex_get_time_stop(vector_get_key_at(
- (vector_t) context, (unsigned int) x));
- }
- static int _compare_dijkstra(void *x, void *y, void *context)
- {
- vector_t distances = context;
- double *a = (double *) vector_get_key_at(distances, (unsigned int) x);
- double *b = (double *) vector_get_key_at(distances, (unsigned int) y);
- if (*a < *b)
- return -1;
- else if (*a > *b)
- return +1;
- // If the vertices have the same distance from source then
- // i compare them after their identifiers.
- return (unsigned int) x - (unsigned int) y;
- }
- static int _compare_prim(void *x, void *y, void *context)
- {
- double *distances = context;
- unsigned int v1, v2;
- v1 = (unsigned int) x;
- v2 = (unsigned int) y;
- if (distances[v1] < distances[v2])
- return -1;
- else if (distances[v1] > distances[v2])
- return 1;
- // If the vertices have the same distance from source then
- // i compare them after their identifiers.
- return v1 - v2;
- }
- static int _compare_edges_kruskal(void *x, void *y, void *context)
- {
- edge_t edge1, edge2;
- double a, b;
- edge1 = x;
- edge2 = y;
- a = edge_get_cost(edge1);
- b = edge_get_cost(edge2);
- if (a < b)
- return -1;
- if (a > b)
- return 1;
- return 0;
- }
- static int _compare_nodes_kruskal(void *x, void *y, void *context)
- {
- return (int) ((unsigned long) x - (unsigned long) y);
- }
- static void _init_flow(matrix_t flow)
- {
- unsigned int i, j, n;
- n = matrix_get_columns_number(flow);
- // For-each key in the matrix, set it's value to 0.
- for (i = 0; i < n; i++)
- for (j = 0; j < n; j++)
- *(double *) matrix_get_key_at(flow, i, j) = 0;
- }
- static void _flow_dfs(graph_t graph, unsigned int current_node,
- unsigned int destination, linked_list_t path, matrix_t max_flow)
- {
- /*
- * Basically, the current function has the same idea as ordinary DFS travel.
- * The main difference is that this method adds flow constrains on links
- * between vertices.
- * For example, if an edge is saturated (flow = capacity) then the vertices
- * aren't neighbors; in ordinary DFS they are.
- * With other words, _flow_dfs works with function cost equals to edge_capacity - edge_flow;
- * and DFS works with edge_flow as 0 identity function.
- */
- vertex_t u = vector_get_key_at(graph->vertices, current_node);
- unsigned int next_node, nodes_number;
- double capacity;
- nodes_number = vector_get_size(graph->vertices);
- if (vertex_get_visited(u))
- return;
- vertex_set_visited(u, 1);
- linked_list_push_back(path, (void *) current_node);
- if (current_node == destination)
- return;
- for (next_node = 0; next_node < nodes_number; next_node++)
- /* Travel the next_node only if :
- * 1. destination isn't visited
- * 2. next_node isn't visited.
- */
- if (!vertex_get_visited(vector_get_key_at(graph->vertices, destination))
- && !vertex_get_visited(vector_get_key_at(graph->vertices,
- next_node)))
- {
- /*
- * 1. If there is an edge between current_node and next_node
- * then continue only if the flow is smaller then the cost (capacity).
- *
- * 2. If there isn't an edge between current_node and next_node
- * then consider the capacity 0 and go on if the flow is negative.
- */
- if (graph_is_edge(graph, current_node, next_node))
- capacity = edge_get_cost(graph_get_edge(graph, current_node,
- next_node));
- else
- capacity = 0;
- if (*(double *) matrix_get_key_at(max_flow, current_node, next_node)
- < capacity)
- _flow_dfs(graph, next_node, destination, path, max_flow);
- }
- if (!vertex_get_visited(vector_get_key_at(graph->vertices, destination)))
- {
- linked_list_remove_key(path, (void *) current_node, _int_compare, NULL,
- 1);
- vertex_set_visited(vector_get_key_at(graph->vertices, current_node), 0);
- }
- }
- static void _flow_bfs(graph_t graph, unsigned int source,
- unsigned int destination, linked_list_t path, matrix_t max_flow)
- {
- queue_t queue;
- vertex_t vertex, current_vertex;
- unsigned int next_node, current_node, nodes_number;
- void *context;
- /*
- * Basically, this function has the same idea as ordinary BFS function.
- * The main difference is that this method adds flow constrains on links
- * between vertices.
- * See _flow_dfs for more details about the last statement.
- */
- nodes_number = vector_get_size(graph->vertices);
- vertex = vector_get_key_at(graph->vertices, source);
- vertex_set_visited(vertex, 1);
- vertex_set_parent_identifier(vertex, (unsigned int) -1);
- queue = queue_new(nodes_number);
- queue_push_back(queue, vertex);
- while (!queue_is_empty(queue))
- {
- current_vertex = queue_get_front(queue);
- current_node = vertex_get_identifier(current_vertex);
- queue_pop_front(queue);
- vertex = graph->implementation->first_vertex(graph->graph,
- current_node, &context);
- while (1)
- {
- if (vertex == NULL)
- break;
- next_node = vertex_get_identifier(vertex);
- if ((CAPACITY(graph, current_node, next_node)) > (FLOW(max_flow,
- current_node, next_node)) && !vertex_get_visited(vertex))
- {
- vertex_set_visited(vertex, 1);
- vertex_set_parent_identifier(vertex, current_node);
- queue_push_back(queue, vertex);
- }
- vertex = graph->implementation->next_vertex(graph->graph,
- current_node, &context);
- }
- }
- // After the BFS modified travel ended, i compute the path between
- // destination and source, analyzing each vertex parent.
- current_node = destination;
- while (current_node != (unsigned int) -1)
- {
- linked_list_push_front(path, (void *) current_node);
- current_node = vertex_get_parent_identifier(vector_get_key_at(
- graph->vertices, current_node));
- }
- // Free the queue used.
- queue_delete(queue);
- }
- static double _min_flow_path(graph_t graph, matrix_t max_flow,
- linked_list_t path)
- {
- double min_flow, aux;
- unsigned i, j, k, n;
- linked_list_iterator_t it;
- /*
- * Finds the minimum flow for a given path : a(0), a(1) .... a(N).
- * a - list of vertices.
- * The algorithm is trivial :
- * 1. for-each a(K) and a(K+1), K from 0 to N-1 execute :
- * 2. if the current min_flow is greater the flow from a(K) to a(K+1),
- * then actualize current min_flow to the smaller flow value.
- * 3. return the min_flow.
- */
- it = linked_list_get_begin(path);
- i = (unsigned int) linked_list_iterator_get_key(it);
- it = linked_list_iterator_get_next(it);
- j = (unsigned int) linked_list_iterator_get_key(it);
- it = linked_list_iterator_get_next(it);
- min_flow = CAPACITY(graph, i, j) - FLOW(max_flow, i, j);
- n = linked_list_get_size(path);
- for (k = 1; k < n - 1; k++)
- {
- i = j;
- j = (unsigned int) linked_list_iterator_get_key(it);
- it = linked_list_iterator_get_next(it);
- aux = CAPACITY(graph, i, j) - FLOW(max_flow, i, j);
- if (aux < min_flow)
- min_flow = aux;
- }
- return min_flow;
- }
- static void _add_flow_on_path(matrix_t max_flow, linked_list_t path,
- double min_flow)
- {
- unsigned i, j, k, n;
- linked_list_iterator_t it;
- /*
- * Increases the flow from a given path : a(0), a(1) .... a(N).
- * a - list of vertices.
- * The algorithm is trivial :
- * 1.for-each a(K) and a(K+1), increase the flow with min_flow value.
- * 2.for-each a(K+1) and a(K), decrease the flow with min_flow value.
- * The second statement is used because flow(u,v) = -flow(v,u).
- */
- it = linked_list_get_begin(path);
- i = (unsigned int) linked_list_iterator_get_key(it);
- it = linked_list_iterator_get_next(it);
- j = (unsigned int) linked_list_iterator_get_key(it);
- it = linked_list_iterator_get_next(it);
- (*(double *) matrix_get_key_at(max_flow, i, j)) += min_flow;
- (*(double *) matrix_get_key_at(max_flow, j, i)) -= min_flow;
- n = linked_list_get_size(path);
- for (k = 1; k < n - 1; k++)
- {
- i = j;
- j = (unsigned int) linked_list_iterator_get_key(it);
- it = linked_list_iterator_get_next(it);
- (*(double *) matrix_get_key_at(max_flow, i, j)) += min_flow;
- (*(double *) matrix_get_key_at(max_flow, j, i)) -= min_flow;
- }
- }
- INLINE static double CAPACITY(graph_t graph, unsigned int i, unsigned int j)
- {
- if (!graph_is_edge(graph, i, j))
- return 0;
- return edge_get_cost(graph_get_edge(graph, i, j));
- }
- INLINE static double FLOW(matrix_t max_flow, unsigned int i, unsigned int j)
- {
- return *(double *) matrix_get_key_at(max_flow, i, j);
- }
- // === End ===
|