Added the graph_has_symmetric_edges() routine.

daben · Apr 28, 2012 · deaf47f · deaf47f
1 parent 4d2d6dd
commit deaf47f
Show file tree

Hide file tree

Showing 2 changed files with 51 additions and 0 deletions.
diff --git a/dlib/graph_utils/graph_utils.h b/dlib/graph_utils/graph_utils.h
@@ -410,6 +410,37 @@ namespace dlib
         return (visited.size() == g.number_of_nodes());
     }
 
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename T
+        >
+    bool graph_has_symmetric_edges (
+        const T& graph
+    )
+    {
+        for (unsigned long i = 0; i < graph.number_of_nodes(); ++i)
+        {
+            for (unsigned long j = 0; j < graph.node(i).number_of_children(); ++j)
+            {
+                const unsigned long jj = graph.node(i).child(j).index();
+                // make sure every edge from a parent to a child has an edge linking back
+                if (graph.has_edge(jj,i) == false)
+                    return false;
+            }
+
+            for (unsigned long j = 0; j < graph.node(i).number_of_parents(); ++j)
+            {
+                const unsigned long jj = graph.node(i).parent(j).index();
+                // make sure every edge from a child to a parent has an edge linking back
+                if (graph.has_edge(i,jj) == false)
+                    return false;
+            }
+        }
+
+        return true;
+    }
+
 // ----------------------------------------------------------------------------------------
 
     template <

diff --git a/dlib/graph_utils/graph_utils_abstract.h b/dlib/graph_utils/graph_utils_abstract.h
@@ -81,6 +81,26 @@ namespace dlib
               parent node g.node(parent_idx) to child node g.node(child_idx).
     !*/
 
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename T
+        >
+    bool graph_has_symmetric_edges (
+        const T& graph
+    );
+    /*!
+        requires
+            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h 
+        ensures
+            - if (All nodes have either 0 edges between them or 2 edges between them.  
+              That is, if there is an edge pointing from node A to node B then there is
+              also an edge from B to A) then
+                - returns true
+            - else
+                - returns false
+    !*/
+
 // ----------------------------------------------------------------------------------------
 
     template <