Changeset 52 for sources/src/graph.cc

Timestamp:

Jan 22, 2013, 4:23:22 PM (12 years ago)

Author:

meunier

Message:

Code formatting in all source files.

File:

• sources/src/graph.cc (modified) (4 diffs)

sources/src/graph.cc

@@ -1 +1 @@
 /*------------------------------------------------------------\
-|                                                             |
-| Tool    :                  systemcass                       |
-|                                                             |
-| File    :                 graph.cc                          |
-|                                                             |
-| Author  :                 Petrot Frédéric                   |
-|                           Taktak Sami                       |
-|                           Buchmann Richard                  |
-|                                                             |
-| Date    :                   09_07_2004                      |
-|                                                             |
-\------------------------------------------------------------*/
+  |                                                             |
+  | Tool    :                  systemcass                       |
+  |                                                             |
+  | File    :                 graph.cc                          |
+  |                                                             |
+  | Author  :                 Petrot Frédéric                   |
+  |                           Taktak Sami                       |
+  |                           Buchmann Richard                  |
+  |                                                             |
+  | Date    :                   09_07_2004                      |
+  |                                                             |
+  \------------------------------------------------------------*/
 
 /* 
@@ -121 +121 @@
 /* Sorry for that, Mr Knuth :-) */
 
-Graph *gb_new_graph(int n)
-{
-Graph *g;
-
-   g = (Graph *) malloc(sizeof(Graph));
-   g->n = n;
-   if (n)
-   {
-     g->vertices = (Vertex *) malloc(n * sizeof(Vertex));
-     (void)memset(g->vertices, 0, n * sizeof(Vertex));
-   } else {
-     g->vertices = NULL;
-   }
-   return g;
-}
-
-static void gb_new_arc(Vertex *u, Vertex *v, long l)
-{
-Arc *a;
-
-   a       = (Arc *) malloc(sizeof(Arc));
-   a->next = u->arcs;
-   u->arcs = a;
-   a->tip  = v;
-   a->len  = l;
+Graph * gb_new_graph(int n) {
+    Graph * g;
+
+    g = (Graph *) malloc(sizeof(Graph));
+    g->n = n;
+    if (n) {
+        g->vertices = (Vertex *) malloc(n * sizeof(Vertex));
+        (void) memset(g->vertices, 0, n * sizeof(Vertex));
+    }
+    else {
+        g->vertices = NULL;
+    }
+    return g;
+}
+
+
+static void gb_new_arc(Vertex * u, Vertex * v, long l) {
+    Arc * a;
+    a = (Arc *) malloc(sizeof(Arc));
+    a->next = u->arcs;
+    u->arcs = a;
+    a->tip = v;
+    a->len = l;
 }
 
@@ -152 +150 @@
 #define VERTEX 220898
 
-#define type     u.I
-
-void new_arc(Vertex *u, Vertex *v)
-{
-Arc *a;
+#define type u.I
+
+void new_arc(Vertex * u, Vertex * v) {
+    Arc * a;
 #ifdef CONFIG_DEBUG
-        if ((u == NULL) || (v == NULL))
-                exit(29042004);
+    if ((u == NULL) || (v == NULL)) {
+        exit(29042004);
+    }
 #endif
-   for (a = u->arcs; a; a = a->next)
-      if (a->tip == v)
-         return;
-   gb_new_arc(u, v, 0L);
-}
+    for (a = u->arcs; a != NULL; a = a->next) {
+        if (a->tip == v) {
+            return;
+        }
+    }
+    gb_new_arc(u, v, 0L);
+}
+
 
 #define rank z.I
@@ -181 +182 @@
  * to ones list the components contents (one or more vertices) */
 
-extern strong_component_list_t *strong_component(Graph *g)
-{
-  long nn;
-  Vertex *active_stack;
-  Vertex *settled_stack;
-  Vertex *vv;
-  
-  register Vertex *v;
-  
-  strong_component_list_t *strongcomponents = new strong_component_list_t;
-        typedef std::vector<void*> void_list_t;
-  void_list_t *component;
-
-  if (g->vertices == NULL)
+extern strong_component_list_t *strong_component(Graph * g) {
+    long nn;
+    Vertex * active_stack;
+    Vertex * settled_stack;
+    Vertex * vv;
+
+    register Vertex * v;
+
+    strong_component_list_t * strongcomponents = new strong_component_list_t;
+    typedef std::vector < void *>void_list_t;
+    void_list_t * component;
+
+    if (g->vertices == NULL) {
+        return strongcomponents;
+    }
+
+    /* Make all vertices unseen and all arcs untagged */
+    for (v = g->vertices + g->n - 1; v >= g->vertices; v--) {
+        v->rank = 0;
+        v->untagged = v->arcs;
+    }
+    nn = 0;
+    active_stack = settled_stack = NULL;
+
+    for (vv = g->vertices; vv < g->vertices + g->n; vv++) {
+        if (vv->rank == 0) { /* vv is still unseen */
+            v = vv;
+            v->parent = NULL;
+
+            v->rank = ++nn;
+            v->link = active_stack;
+            active_stack = v;
+            v->min = v;
+
+            do { /* Eplore one step from the current vertex v, possibly moving to another vertex 
+                           and calling it v */
+                register Vertex *u; /* a vertex adjacent to v */
+                register Arc *a = v->untagged; /* v's first remaining untagged arc, if any */
+                if (a) {
+                    u = a->tip;
+                    v->untagged = a->next; /* tag the arc from v to u */
+                    if (u->rank) { /* we've seen u already */
+                        if (u->rank < v->min->rank) { /* non-tree arc, jutt update v->min */
+                            v->min = u;
+                        }
+                    }
+                    else { /* u is presently unseen */
+                        u->parent = v; /* the arcfrom v to u is a new tree arc */
+                        v = u; /* u will now be the currnt vertex */
+                        v->rank = ++nn; /* make vertex v active */
+                        v->link = active_stack;
+                        active_stack = v;
+                        v->min = v;
+                    }
+                }
+                else { /* all arcs from v are tagged, so v matures */
+                    u = v->parent; /* prepare to backtrack in the tree */
+                    if (v->min == v) {
+                        /* Remove v and all its successors on the activestack from the tree,
+                           and mark them as a strong component of the graph */
+                        register Vertex * t; /* runs though the vertices of the new strong component */
+
+                        t = active_stack;
+                        active_stack = v->link;
+                        v->link = settled_stack;
+                        settled_stack = t; /* we've moved the top of one stack to the other */
+                        component = new void_list_t;
+                        /* singe vetex */
+                        if (t != v) { /* NOT singe vetex */
+                            while (t != v) {
+                                component->push_back(t->data);
+                                t->rank = infinity; /* now t is settled */
+                                t->parent = v; /* and v represents the new strong component */
+                                t = t->link;
+                            }
+                        }
+                        component->push_back(v->data);
+                        strongcomponents->push_back(component);
+                        v->rank = infinity; /* v too is settled */
+                        v->parent = v; /* and represents its own strong component */
+                    }
+                    else {
+                        /* the arc from u to v has just matured, making v->min visible from u */
+                        if (v->min->rank < u->min->rank) {
+                            u->min = v->min;
+                        }
+                    }
+                    v = u;/* the former parent of v is the new current vertex v */
+                }
+            } while (v != NULL);
+        }
+    }
+
     return strongcomponents;
-
- /* Make all vertices unseen and all arcs untagged */
- for (v = g->vertices + g->n - 1; v >= g->vertices; v--) {
-   v->rank = 0;
-   v->untagged = v->arcs;
- }
- nn = 0;
- active_stack = settled_stack = NULL;
-
- for (vv = g->vertices; vv < g->vertices + g->n; vv++)
-   if (vv->rank == 0) { /* vv is still unseen */
-     v = vv;
-     v->parent = NULL;
-     
-     v->rank = ++nn;
-     v->link = active_stack;
-     active_stack = v;
-     v->min = v;
-     
-     do { /* Eplore one step from the current vertex v, possibly moving to another vertex 
-             and calling it v */
-       register Vertex *u;               /* a vertex adjacent to v */
-       register Arc *a = v->untagged;    /* v's first remaining untagged arc, if any */
-       if (a) {
-         u = a->tip;
-         v->untagged = a->next;    /* tag the arc from v to u */
-         if (u->rank) {    /* we've seen u already */
-           if (u->rank < v->min->rank) /* non-tree arc, jutt update v->min */
-             v->min = u;
-         } else {   /* u is presently unseen */
-           u->parent = v; /* the arcfrom v to u is a new tree arc */
-           v = u;         /* u will now be the currnt vertex */
-           v->rank = ++nn;  /* make vertex v active */
-           v->link = active_stack;
-           active_stack = v;
-           v->min = v;
-         }
-       } else { /* all arcs from v are tagged, so v matures */
-         u = v->parent; /* prepare to backtrack in the tree */
-         if (v->min == v) {
-           /* Remove v and all its successors on the activestack from the tree,
-              and mark them as a strong component of the graph */
-           register Vertex *t; /* runs though the vertices of the new strong component */
-           
-           t = active_stack;
-           active_stack = v->link;
-           v->link = settled_stack;
-           settled_stack = t; /* we've moved the top of one stack to the other */
-           component = new void_list_t;
-           /* singe vetex */
-           if (t != v) { /* NOT singe vetex */
-             while (t != v) {
-               component->push_back(t->data);
-               t->rank = infinity; /* now t is settled */
-               t->parent = v;  /* and v represents the new strong component */
-               t = t->link;
-             }
-           }
-           component->push_back(v->data);
-           strongcomponents->push_back(component);
-           v->rank = infinity; /* v too is settled */
-           v->parent = v; /* and represents its own strong component */
-         } else /* the arc from u to v has just matured, making v->min visible from u */
-           if (v->min->rank < u->min->rank) u->min = v->min;
-         v = u; /* the former parent of v is the new current vertex v */
-       }
-     } while (v != NULL);
-   }
-
- return strongcomponents;
-}
-
-bool 
-has_cycle (const strong_component_list_t &l)
-{       
-        strong_component_list_t::const_iterator it;
-        for (it = l.begin (); it != l.end (); ++it)
-        {
-                if ((*it)->size() > 1)
-                        return true;
-        }
-        return false;
-}
-
-#if 0
-const component_list_t*
-get_cycle (const strong_component_list_t &l)
-{       
-        strong_component_list_t::const_iterator it;
-        for (it = l.begin (); it != l.end (); ++it)
-        {
-    const component_list_t *c = *it;
-                if (c->size() > 1)
-                        return c;
-        }
-        return NULL;
-}
-
-void
-print_cycle (std::ostream &o, 
-             const component_list_t *c)
-{
-  if (c == NULL)
-    return;
-  component_list_t::const_iterator it;
-  for (it = c->begin (); it != c->end (); ++it)
-  {
-    void *v = *it;
-    o << hex << (int) v << " ";
-  }
-  o << "\n";
-}
-#endif
-
+}
+
+
+bool has_cycle(const strong_component_list_t & l) {
+    strong_component_list_t::const_iterator it;
+    for (it = l.begin(); it != l.end(); ++it) {
+        if ((*it)->size() > 1) {
+            return true;
+        }
+    }
+    return false;
+}
+
+
+/*
+# Local Variables:
+# tab-width: 4;
+# c-basic-offset: 4;
+# c-file-offsets:((innamespace . 0)(inline-open . 0));
+# indent-tabs-mode: nil;
+# End:
+#
+# vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
+*/
+