[Boost-commit] svn:boost r64077 - sandbox/SOC/2010/graph

Subject: [Boost-commit] svn:boost r64077 - sandbox/SOC/2010/graph
From: dbarbosa_at_[hidden]
Date: 2010-07-17 00:48:56

Author: dbarbosa
Date: 2010-07-17 00:48:55 EDT (Sat, 17 Jul 2010)
New Revision: 64077
URL: http://svn.boost.org/trac/boost/changeset/64077

Log:
Some questions to be addressed

Added:
   sandbox/SOC/2010/graph/questions.org   (contents, props changed)

Added: sandbox/SOC/2010/graph/questions.org
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/graph/questions.org	2010-07-17 00:48:55 EDT (Sat, 17 Jul 2010)
@@ -0,0 +1,57 @@
+* How to see that two vertices or two edges in two distinct graphs are the same?
+  Comparing two vertex_descriptor or two edge_descriptor is not valid.
+** For edges we can (at least for now) ignore this problem
+   We can just use the source and the target vertices to see if they are the same
+   Problem: parallel edges
+** For vertices
+   We can use the name or other vertex property or something external.
+   See "globally identifying vertices"
+* Globally identifying vertices
+** Requirements
+*** Two vertices u (in G) and v (in H) are the same if and only if they are associated to the same global id.
+*** Given aq set of global ids, we need to be able to retrieve the global id of a vertex v in a graph g.
+    Why: to check if two vertices in two graphs are the same.
+*** Every vertex must be associated to at most one global id (or it must be associated to an global id). *
+*** Not requiring that all vertices have a global id is probably more efficient and practical.
+    Why: smaller data structure and the user have to set what is in
+    common and is free to set every vertex if it is more easy for him.
+*** Given a graph g, a global id can be associated to at most one vertex in g. *
+*** The set of global id received by an algorithm must have only distinct values. *
+*** It is probably better if the global id has a type defined by the user and have some meaning to the user.
+*** Relate vertices from the output of an algorithm with the input(s).
+    If an operation takes two (or more) graphs G1 and G2 and results
+    in a graph G, it can be useful to know from --> each vertex should
+    have a global id that corresponds to the vertex or vertices that
+    generated this vertex.  Why: probably in some cases the user would
+    like to have an association between vertices and edges in G and
+    the ones in G1 and G2.
+*** the three items marked with * can be summarized as
+    the association between a set of global ids and the vertices of a
+    graph is
+    - a "zero or one to zero or one" relation in a database jargon.
+    or, in other words
+    - a bijection if we ignoring all ids and vertices that are not associated.
+      
+    Why: one vertex in g1 cannot be equal to two distinct vertices in
+    g2 or two distinct vertices in g2 cannot be viewed globally as
+    being the same vertex.
+** How to do it?
+*** Vertex name or other vertex property
+    Depends on the user
+*** A different class (globalVertexMapping)
+    graph -> (vertex_descriptor <-> globalId)
+*** Put the bimap (vertex_descriptor <-> globalId) inside the graph
+*** etc ??
+* If two vertices or edges are identified as the same, what about their properties? They must be the same properties?
+  What if they are different? These properties should be copied to the new graph if this vertex/edge is in the new graph?
+* What about...
+** graph line?
+   If we try to link (set the same global id to) the output with the
+   input, we need to link a vertex to an edge and vice versa. Also,
+   what to do with vertex and edge properties?
+** Graph composition?
+   a vertex in the output is generated by two distinct vertex in the inputs
+* Change copy.hpp?
+  Copy.hpp uses a "orig2copy" to relate a vertex descriptor in g_out
+  with the vertex descriptor in g_in. It is a restricted version of
+  what we are trying to do here.