// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey // Author(s): Patricia K. Fasel (Los Alamos Nat. Lab.), Jonathan Berry, // 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 // #include #include #include #include #include #include #include #include #include static char white[] = "white"; static char gray[] = "gray"; static char black[] = "black"; const static int white_mark = 0; const static int gray_mark = 1; const static int black_mark = 2; // // visit all the neighbors of the vertex // void DFSvisit(Graph* graph, Vertex* v, Sequence& result, double& time, char* graph_view) { setAttribute((GraphObject*) v, "mark", gray_mark); animateVertex(v, graph_view, "color", "color", INIT_STEP, (char*)gray); time++; setAttribute((GraphObject*) v, "starttime", time); char* label; if (graph_view) { ostrstream oss; oss << time << "/" << ends; label = oss.str(); animateVertex(v, graph_view, "label", "vertex-label", ALG_STEP, label); } Set outIncEdges = graph->outIncidentEdges(v); Iterator get_edge(&outIncEdges); Edge* incEdge; while (get_edge(incEdge)) { int emark; getAttribute((GraphObject*) incEdge, "mark", emark); if (!emark) { Sequence neighbors = incEdge->otherVertices(v); Iterator get_neighbor(&neighbors); Vertex* adjVertex; setAttribute((GraphObject*) incEdge, "mark", 1); char *edgeColor = black; char *edgeType = "none"; while (get_neighbor(adjVertex)) { int vmark; getAttribute((GraphObject*) adjVertex, "mark", vmark); switch (vmark) { case white_mark: // tree edge setAttribute((GraphObject*)adjVertex, "pred", v); result.append(adjVertex); edgeColor = "red"; edgeType = "tree"; animateEdge(incEdge, graph_view, "color", "color", INIT_STEP, edgeColor); animateEdge(incEdge, graph_view, "label", "edge-label", ALG_STEP, edgeType); DFSvisit(graph, adjVertex, result, time, graph_view); setAttribute((GraphObject*) incEdge, "type", TREE_EDGE_TYPE); break; case gray_mark: // back edge int neigh_dtime, v_dtime; getAttribute((GraphObject*) v, "starttime", v_dtime); getAttribute((GraphObject*) adjVertex, "starttime", neigh_dtime); // the following comparison prevents hyperedges // from being re-typed as neighbors are processed if (strcmp(edgeType, "tree")!=0) { edgeColor = "blue"; // backedge edgeType = "back"; setAttribute((GraphObject*) incEdge, "type", BACK_EDGE_TYPE); } break; case black_mark: // cross edge or forward edge getAttribute((GraphObject*) v, "starttime", v_dtime); getAttribute((GraphObject*) adjVertex, "starttime", neigh_dtime); // the following comparison prevents hyperedges // from being re-typed as neighbors are processed if (strcmp(edgeType, "tree")!=0) { if (v_dtime < neigh_dtime) { edgeColor = "green"; // forward edge edgeType = "forward"; setAttribute((GraphObject*) incEdge, "type", FORWARD_EDGE_TYPE); } else { edgeColor = "purple"; // cross edge edgeType = "cross"; setAttribute((GraphObject*) incEdge, "type", CROSS_EDGE_TYPE); } } break; } } if (strcmp(edgeType, "tree")!=0) { animateEdge(incEdge, graph_view, "color", "color", INIT_STEP, edgeColor); animateEdge(incEdge, graph_view, "label", "edge-label", ALG_STEP, edgeType); } } } setAttribute((GraphObject*) v, "mark", black_mark); animateVertex(v, graph_view, "color", "color", INIT_STEP, (char*)black); time++; setAttribute((GraphObject*) v, "finishtime", time); if (graph_view) { ostrstream oss; oss << label << time << ends; delete[] label; label = oss.str(); animateVertex(v, graph_view, "label","vertex-label", ALG_STEP, label); delete[] label; } } // // depth first search returns an ordered sequence of vertices // Sequence DepthFirstSearch(Graph* graph, char *graph_view, VertexComparison compare) { Sequence result; ResetAttributes(graph); MSet edges = graph->edges(); Iterator get_edge(&edges); Edge *e; while(get_edge(e)) setAttribute((GraphObject*) e, "mark", 0); MSet vertices = graph->vertices(); Iterator get_vertex(&vertices); Vertex* v; while(get_vertex(v)) { setAttribute((GraphObject*) v, "mark", white_mark); setAttribute((GraphObject*) v, "pred", (Vertex*) 0); } double time = 0; get_vertex.reset(); if(compare) { // do we have a special order to consider in? List vertex_list; while(get_vertex(v)) vertex_list.insert(v); vertex_list.sort(compare); while(vertex_list.size()) { v = vertex_list.get(); int color; getAttribute((GraphObject*) v, "mark", color); if (color == white_mark) { result.append(v); DFSvisit(graph, v, result, time, graph_view); } } } else { // or not? while(get_vertex(v)) { int color; getAttribute((GraphObject*) v, "mark", color); if (color == white_mark) { result.append(v); DFSvisit(graph, v, result, time, graph_view); } } } return result; }