Boost logo

Boost-Commit :

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.


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk