// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey // Author(s): Chris Burrows (Trenton State College) // This software is copyrighted by the DIMACS Center at Rutgers, The State // University of New Jersey. IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND // RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY DISCLAIM // ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL // DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY // DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE // POSSIBILITY OF SUCH DAMAGE. // THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT. THIS SOFTWARE // IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE // NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR // MODIFICATIONS. // The authors hereby grant permission to use, copy, modify, distribute, // and license this software and its documentation for any purpose, provided // that existing copyright notices are retained in all copies and that this // notice is included verbatim in any distributions. No written agreement, // license, or royalty fee is required for any of the authorized uses. // Modifications to this software may be copyrighted by their authors // and need not follow the licensing terms described here, provided that // the new terms are clearly indicated on the first page of each file where // they apply. // Last File Update: 31-Jul-1996 // /////////////////////////////////////////////////////////////////////////// // LINK: Generic Graph Tool and Class Library // // Function name: BreadthSearch(Graph*, char*, Vertex*) // Breadth First Search on a graph // // Synopsis: // Do a breadth first search on a hypergraph or binary graph // // Description: // 1. Initialize an ordered search list by choosing an unmarked vertex. // 2. If there are no unmarked vertices, we are finished. // Initialize a queue by marking and placing all the // neighbors of the present vertex on the queue. // 3. If the queue is empty, choose a new unmarked vertex, // add it to the search list, and return to step 2. // Otherwise, remove a vertex from the queue, add it to // the search list, and mark and place on the queue all // of its unmarked neighbors. // 4. Repeat 3. // // Creation: 1993 March 25, Patricia K. Fasel, pkf@lanl.gov // // Routines used: Queue.cc // // Related files: // // Test suite: none // // User documentation: none // // Development History: // 08-01-95 berryj@dimacs.rutgers.edu changed dequeue // 08-24-95 berryj@dimacs.rutgers.edu changed dequeue // again - this time to conform with // the new Deque class // 06-24-96 burrows@trenton.edu // severely altered behavior to conform // with CLR, 470. now accepts source // vertex, and spans only reachable // vertices. animated. // // Testing History: // // Code Review: // // Bugs and Deficiencies: // /////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include #include #include static char white [] = "white"; static char gray [] = "gray"; static char black [] = "black"; static char edgeType[] = "tree"; static char edgeColor[] = "red"; static char inf_str[] = "-"; // // mark all neigbors of the passed vertex and add to the passed stack // // void // markNeighbors(Queue& passed_queue, Vertex* passed_vertex) // { // Set neighbors = passed_vertex->outNeighbors(); // Iterator get_neighbor(&neighbors); // Vertex* vertex; // while (get_neighbor(vertex)) { // int mark; // getAttribute((GraphObject*) vertex, "mark", mark); // if (mark == 0) { // setAttribute((GraphObject*) vertex, "mark", 1); // passed_queue.enqueue(vertex); // } // } // } // // breadth first search returns an ordered sequence of vertices // Sequence BreadthFirstSearch(Graph* graph, char *graph_view, Vertex *s) { // initialize attributes on all vertices ResetAttributes(graph); Sequence result; if(graph->order() == 0) { return result; } Vertex** V = graph->vertexStart(); for (int i=0; i < graph->order(); i++) { animateVertex(V[i], graph_view, "label", "vertex-label", INIT_STEP, (char*)inf_str); } // get source if (!s) s = graph->vertex(0); // initialize source setAttribute((GraphObject*) s, "distance", 0); setAttribute((GraphObject*) s, "mark", 1); char *temp; temp = "0"; // for our vertex labels animateVertex(s, graph_view, "color", "color", INIT_STEP, (char*)gray); animateVertex(s, graph_view, "label", "vertex-label", ALG_STEP, temp); Queue Q; Q.enqueue(s); while(!Q.emptyQ()) { Vertex *u = Q.front(); int distance; getAttribute((GraphObject*) u, "distance", distance); distance++; // Set neighbors = u->outNeighbors(); // Iterator u_neighbor(&neighbors); // Vertex* v; Set outEdges = graph->outIncidentEdges(u); Iterator getEdge(&outEdges); Edge* e; while (getEdge(e)) { Sequence neighbors = e->otherVertices(u); Iterator u_neighbor(&neighbors); Vertex* v; // only animate the edge if it gets us somewhere! int treeEdge = 0; while(u_neighbor(v)) { int mark; getAttribute((GraphObject*) v, "mark", mark); if(mark == 0) treeEdge = 1; } if(treeEdge) { animateEdge(e, graph_view, "color", "color", INIT_STEP, (char*)edgeColor); animateEdge(e, graph_view, "label", "edge-label", ALG_STEP, (char*)edgeType); } u_neighbor.reset(); while(u_neighbor(v)) { int mark; getAttribute((GraphObject*) v, "mark", mark); if (mark == 0) { setAttribute((GraphObject*) v, "mark", 1); setAttribute((GraphObject*) v, "distance", distance); animateVertex(v, graph_view, "color", "color", INIT_STEP, (char*) gray); ostrstream string; string << distance << ends; temp = string.str(); animateVertex(v, graph_view, "label", "vertex-label", ALG_STEP, (char*)temp); delete[] temp; Q.enqueue(v); } } } result.append(Q.dequeue()); animateVertex(u, graph_view, "color", "color", ALG_STEP, (char*)black); } return result; }