N-sim v0.9.4

00001 
00014 /*
00015  * Copyright 2007. Los Alamos National Security, LLC. This material
00016  * was produced under U.S. Government contract DE-AC52-06NA25396 for
00017  * Los Alamos National Laboratory (LANL), which is operated by Los
00018  * Alamos National Security, LLC, for the Department of Energy. The
00019  * U.S. Government has rights to use, reproduce, and distribute this
00020  * software. NEITHER THE GOVERNMENT NOR LOS ALAMOS NATIONAL SECURITY,
00021  * LLC, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL
00022  * LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to
00023  * produce derivative works, such modified software should be clearly
00024  * marked, so as not to confuse it with the version available from LANL.
00025  *
00026  * Additionally, this program is free software; you can redistribute
00027  * it and/or modify it under the terms of the GNU General Public
00028  * License as published by the Free Software Foundation; version 2 of
00029  * the License. Accordingly, this program is distributed in the hope
00030  * it will be useful, but WITHOUT ANY WARRANTY; without even the
00031  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00032  * PURPOSE. See the GNU General Public License for more details.
00033  */
00034 
00035 
00036 #include "graph.h"
00037 
00038 
00039 Graph::Graph()
00040 {
00041         vertices = 0;
00042         V = 0;
00043         edges = 0;
00044         E = 0;
00045 }
00046 
00047 
00048 void Graph::_delete_vertices()
00049 {
00050         Vertex *v = vertices;
00051         while (v != 0) {
00052                 Vertex *tmp = v;
00053                 v = v->next;
00054                 delete tmp;
00055         }
00056 }
00057 
00058 
00059 void Graph::_delete_edges()
00060 {
00061         Edge *e = edges;
00062         while (e != 0) {
00063                 Edge *tmp = e;
00064                 e->u->edges = 0;
00065                 e = e->next;
00066                 delete tmp;
00067         }
00068 }
00069 
00070 
00071 Graph::~Graph()
00072 {
00073         _delete_edges();
00074         edges = 0;
00075         E = 0;
00076 
00077         _delete_vertices();
00078         vertices = 0;
00079         V = 0;
00080 }
00081 
00082 
00083 Vertex *Graph::_vertex_exists(unsigned long v)
00084 {
00085         Vertex *vertex = vertices;
00086         for (; vertex != 0; vertex = vertex->next) {
00087                 if (vertex->id == v)
00088                         return vertex;
00089         }
00090         return 0;
00091 }
00092 
00093 
00094 Edge *Graph::_edge_exists(unsigned long a, unsigned long b)
00095 {
00096         Edge *edge = edges;
00097         while (edge != 0) {
00098                 if (edge->u->id == a && edge->v->id == b)
00099                         return edge;
00100                 else if (edge->u->id == b && edge->v->id == a)
00101                         return edge;
00102                 edge = edge->next;
00103         }
00104         return 0;
00105 }
00106 
00107 
00108 Vertex *Graph::find_vertex(unsigned long v)
00109 {
00110         Vertex *vertex, *tail = 0;
00111         if ((vertex = _vertex_exists(v)) != 0)
00112                 return vertex;
00113 
00114         vertex = vertices;
00115         while (vertex != 0) {
00116                 tail = vertex;
00117                 vertex = vertex->next;
00118         }
00119 
00120         vertex = new Vertex();
00121         vertex->id = v;
00122         vertex->adjacencies = 0;
00123         vertex->depth = 1;
00124         vertex->edges = 0;
00125         vertex->next = 0;
00126         vertex->parent = 0;
00127         if (tail != 0)
00128                 tail->next = vertex;
00129         else
00130                 vertices = vertex;
00131         V++;
00132         return vertex;
00133 }
00134 
00135 
00136 Edge *Graph::find_edge(unsigned long a, unsigned long b)
00137 {
00138         Vertex *u = find_vertex(a);
00139         Vertex *v = find_vertex(b);
00140         Edge *edge, *tail = 0;
00141         if ((edge = _edge_exists(a, b)) != 0)
00142                 return edge;
00143 
00144         edge = edges;
00145         while (edge != 0) {
00146                 tail = edge;
00147                 edge = edge->next;
00148         }
00149 
00150         edge = new Edge();
00151         edge->u = u;
00152         edge->v = v;
00153         edge->dist = -1;
00154         edge->next = edge->next_adj = edge->prev_adj = 0;
00155         edge->prev = tail;
00156         if (tail != 0)
00157                 tail->next = edge;
00158         else
00159                 edges = edge;
00160         E++;
00161         return edge;
00162 }
00163 
00164 
00165 Graph::Graph(Graph *orig)
00166 {
00167         Edge *edge;
00168         for (edge = orig->edges; edge != 0; edge = edge->next) {
00169                 Edge *new_edge = find_edge(edge->u->id, edge->v->id);
00170                 new_edge->dist = edge->dist;
00171         }
00172 }
/home/brennan/n-sim/OrbisQuartus/control/graph.cpp
