Loading ...
Sorry, an error occurred while loading the content.
 

BGL: what constitutes an undirected graph?

Expand Messages
  • hankel_o_fung@yahoo.com
    Hi folks, What constitutes an undirected graph? In graph_theory_review.html, it says: In an undirected graph ... (u,v) and (v,u) are two ways of writing the
    Message 1 of 5 , Feb 1, 2001
      Hi folks,

      What constitutes an undirected graph? In graph_theory_review.html,
      it says:

      "In an undirected graph ... (u,v) and (v,u) are two ways of
      writing the same edge.

      "In an undirected graph edge (u,v) is incident on vertices u and v."

      In graph_concepts.html :
      "When using undirected graphs just mentally disregard the
      directionality in the function names ...

      "If the undirected graph is a multigraph then (u,v) and (v,u)
      might be parallel edges. If the graph is not a multigraph then
      (u,v) and (v,u) must be the same edge."

      In using_graph_algorithms.html :

      And in Graph.html, it reads
      "boost::graph_traits<G>::edge_descriptor
      An edge descriptor corresponds to a unique edge (u,v) in a graph.
      An edge descriptor must be DefaultConstructible, Assignable, and
      EqualityComparable."

      However, the meanings of e1==e2, source(e,g) and target(e,g) are
      ambiguous when e1, e2 are edge descriptors and g is undirected,
      even if g is not a multigraph:

      tie(e1,found) = edge(u, v, g);
      tie(e2,found) = edge(v, u, g);
      cout << source(e1,g) == source(e2,g) << endl;
      cout << target(e1,g) == target(e2,g) << endl;

      Currently, the BGL interface does not require both comparisons
      to return true/false. If we view logical equality as an indication
      of identical observable behaviours, then both equalities above
      should return true. If we want to traverse all vertices on a path
      delimited by two edge iterators, we may want "source" and "target"
      to depend on the direction we traverse (this seems to be the case
      in the current implementation of adjacency_list).

      Contrast to source, target and ==, although BGL also does not
      states clearly the semantics of add_edge(u, v, g) and
      add_edge(u, v, ep, g) for a general undirected graph g, they are
      clearly defined in adjacency_list. Although I think it is natural
      for one to follow this semantics for a general undirected, it is
      still desirable to get it defined in the BGL requirements.

      Cheers, Hankel

      (BTW, I find that the following two files are not "reachable"
      from index.html: (1)using_boost_graph_library.html, (2)faq.html.
      The first one seems to be a copy of using_adjacency_list.html.)
    • Jeremy Siek
      Hi Hankel, On Thu, 1 Feb 2001 hankel_o_fung@yahoo.com wrote: hankel hankel However, the meanings of e1==e2, source(e,g) and target(e,g) are hankel ambiguous
      Message 2 of 5 , Feb 1, 2001
        Hi Hankel,

        On Thu, 1 Feb 2001 hankel_o_fung@... wrote:
        hankel>
        hankel> However, the meanings of e1==e2, source(e,g) and target(e,g) are
        hankel> ambiguous when e1, e2 are edge descriptors and g is undirected,
        hankel> even if g is not a multigraph:
        hankel>
        hankel> tie(e1,found) = edge(u, v, g);
        hankel> tie(e2,found) = edge(v, u, g);
        hankel> cout << source(e1,g) == source(e2,g) << endl;
        hankel> cout << target(e1,g) == target(e2,g) << endl;
        hankel>
        hankel> Currently, the BGL interface does not require both comparisons
        hankel> to return true/false. If we view logical equality as an indication
        hankel> of identical observable behaviours, then both equalities above
        hankel> should return true. If we want to traverse all vertices on a path
        hankel> delimited by two edge iterators, we may want "source" and "target"
        hankel> to depend on the direction we traverse (this seems to be the case
        hankel> in the current implementation of adjacency_list).

        I'm not exactly sure as to your point: are you saying that the BGL
        definition and/or implementation of undirected edges is inconsistent, or
        are you asking for a change in the definition? In the various docs that
        you quoted, I don't see an inconsistency... if you disagree could you
        point it out more explicitly.

        The definition of of equality for an undirected edge is that if e1 = (u,v)
        and e2 = (v,u) then e1 = e2. Now, the source and target functions merely
        return the first and second vertex of the pair respectively, so in this
        case source(e1) = u and source(e2) = v. Anotherwords, the statement e1 =
        e2 does not imply that source(e1) = source(e2). Instead it implies the
        more complicated statement:
        (( source(e1) = source(e2) && target(e1) = target(e2) )
        || ( source(e1) = target(e2) && target(e1) = source(e2) ))
        To the best of my knowledge, this definition is the standard one
        used in graph theory.

        So are you asking for this definition to be changed? If so, exactly what
        new definition are you proposing? Or perhaps is there some sort of
        auxiliary functionality that you need to write some algorithm? If you
        could tell me more about the path traversal that you are trying to
        implement (show me code), perhaps I could suggest a way to implement it
        using the current interface/definition.

        hankel> Contrast to source, target and ==, although BGL also does not
        hankel> states clearly the semantics of add_edge(u, v, g) and
        hankel> add_edge(u, v, ep, g) for a general undirected graph g, they are
        hankel> clearly defined in adjacency_list. Although I think it is natural
        hankel> for one to follow this semantics for a general undirected, it is
        hankel> still desirable to get it defined in the BGL requirements.

        Thanks for pointing this out. I'll add to the documentation of
        MutableGraph::add_edge the same semantic requirements as adjacency_list.
        (that the requirement was not already there was an oversight).

        Cheers,
        Jeremy


        ----------------------------------------------------------------------
        Jeremy Siek www: http://www.lsc.nd.edu/~jsiek/
        Ph.D. Candidate email: jsiek@...
        Univ. of Notre Dame work phone: (219) 631-3906
        ----------------------------------------------------------------------
      • Jeremy Siek
        I m guessing, but perhaps you are looking for some kind of guarantee like the following for undirected graphs: for (tie(ui, ui_end) = out_edges(u, g); ui !=
        Message 3 of 5 , Feb 1, 2001
          I'm guessing, but perhaps you are looking for some kind of guarantee
          like the following for undirected graphs:

          for (tie(ui, ui_end) = out_edges(u, g); ui != ui_end; ++ui)
          assert(source(*ui, g) == u);

          This certainly should be made explicit. I know most of the BGL graph
          algorithms assume the above to be true for both directed and undirected
          graphs.

          Cheers,
          Jeremy


          On Thu, 1 Feb 2001, Jeremy Siek wrote:

          jsiek> Hi Hankel,
          jsiek>
          jsiek> On Thu, 1 Feb 2001 hankel_o_fung@... wrote:
          jsiek> hankel>
          jsiek> hankel> However, the meanings of e1==e2, source(e,g) and target(e,g) are
          jsiek> hankel> ambiguous when e1, e2 are edge descriptors and g is undirected,
          jsiek> hankel> even if g is not a multigraph:
          jsiek> hankel>
          jsiek> hankel> tie(e1,found) = edge(u, v, g);
          jsiek> hankel> tie(e2,found) = edge(v, u, g);
          jsiek> hankel> cout << source(e1,g) == source(e2,g) << endl;
          jsiek> hankel> cout << target(e1,g) == target(e2,g) << endl;
          jsiek> hankel>
          jsiek> hankel> Currently, the BGL interface does not require both comparisons
          jsiek> hankel> to return true/false. If we view logical equality as an indication
          jsiek> hankel> of identical observable behaviours, then both equalities above
          jsiek> hankel> should return true. If we want to traverse all vertices on a path
          jsiek> hankel> delimited by two edge iterators, we may want "source" and "target"
          jsiek> hankel> to depend on the direction we traverse (this seems to be the case
          jsiek> hankel> in the current implementation of adjacency_list).
          jsiek>
          jsiek> I'm not exactly sure as to your point: are you saying that the BGL
          jsiek> definition and/or implementation of undirected edges is inconsistent, or
          jsiek> are you asking for a change in the definition? In the various docs that
          jsiek> you quoted, I don't see an inconsistency... if you disagree could you
          jsiek> point it out more explicitly.
          jsiek>
          jsiek> The definition of of equality for an undirected edge is that if e1 = (u,v)
          jsiek> and e2 = (v,u) then e1 = e2. Now, the source and target functions merely
          jsiek> return the first and second vertex of the pair respectively, so in this
          jsiek> case source(e1) = u and source(e2) = v. Anotherwords, the statement e1 =
          jsiek> e2 does not imply that source(e1) = source(e2). Instead it implies the
          jsiek> more complicated statement:
          jsiek> (( source(e1) = source(e2) && target(e1) = target(e2) )
          jsiek> || ( source(e1) = target(e2) && target(e1) = source(e2) ))
          jsiek> To the best of my knowledge, this definition is the standard one
          jsiek> used in graph theory.
          jsiek>
          jsiek> So are you asking for this definition to be changed? If so, exactly what
          jsiek> new definition are you proposing? Or perhaps is there some sort of
          jsiek> auxiliary functionality that you need to write some algorithm? If you
          jsiek> could tell me more about the path traversal that you are trying to
          jsiek> implement (show me code), perhaps I could suggest a way to implement it
          jsiek> using the current interface/definition.
          jsiek>
          jsiek> hankel> Contrast to source, target and ==, although BGL also does not
          jsiek> hankel> states clearly the semantics of add_edge(u, v, g) and
          jsiek> hankel> add_edge(u, v, ep, g) for a general undirected graph g, they are
          jsiek> hankel> clearly defined in adjacency_list. Although I think it is natural
          jsiek> hankel> for one to follow this semantics for a general undirected, it is
          jsiek> hankel> still desirable to get it defined in the BGL requirements.
          jsiek>
          jsiek> Thanks for pointing this out. I'll add to the documentation of
          jsiek> MutableGraph::add_edge the same semantic requirements as adjacency_list.
          jsiek> (that the requirement was not already there was an oversight).
          jsiek>
          jsiek> Cheers,
          jsiek> Jeremy
          jsiek>
          jsiek>
          jsiek> ----------------------------------------------------------------------
          jsiek> Jeremy Siek www: http://www.lsc.nd.edu/~jsiek/
          jsiek> Ph.D. Candidate email: jsiek@...
          jsiek> Univ. of Notre Dame work phone: (219) 631-3906
          jsiek> ----------------------------------------------------------------------
          jsiek>
          jsiek>
          jsiek>
          jsiek>
          jsiek>
          jsiek>

          ----------------------------------------------------------------------
          Jeremy Siek www: http://www.lsc.nd.edu/~jsiek/
          Ph.D. Candidate email: jsiek@...
          Univ. of Notre Dame work phone: (219) 631-3906
          ----------------------------------------------------------------------
        • hankel_o_fung@yahoo.com
          ... Yes, that s what I mean. Sorry for not writing concisely. ... So, what is the current status? Is the above property of out_edges already a requirement
          Message 4 of 5 , Feb 1, 2001
            --- In boost@y..., Jeremy Siek <jsiek@l...> wrote:
            >
            > I'm guessing, but perhaps you are looking for some kind of guarantee
            > like the following for undirected graphs:
            >
            > for (tie(ui, ui_end) = out_edges(u, g); ui != ui_end; ++ui)
            > assert(source(*ui, g) == u);
            >
            Yes, that's what I mean. Sorry for not writing concisely.

            > This certainly should be made explicit.
            So, what is the current status? Is the above property of out_edges
            already a requirement (though undocumented) of BGL? Or is it just
            a coincidence that the current implementations in BGL assume the
            above?

            > I know most of the BGL graph
            > algorithms assume the above to be true for both directed and
            > undirected graphs.

            Cheers, Hankel
          • Jeremy Siek
            On Fri, 2 Feb 2001 hankel_o_fung@yahoo.com wrote: hankel --- In boost@y..., Jeremy Siek wrote: hankel hankel I m guessing, but perhaps you
            Message 5 of 5 , Feb 1, 2001
              On Fri, 2 Feb 2001 hankel_o_fung@... wrote:
              hankel> --- In boost@y..., Jeremy Siek <jsiek@l...> wrote:
              hankel> >
              hankel> > I'm guessing, but perhaps you are looking for some kind of guarantee
              hankel> > like the following for undirected graphs:
              hankel> >
              hankel> > for (tie(ui, ui_end) = out_edges(u, g); ui != ui_end; ++ui)
              hankel> > assert(source(*ui, g) == u);
              hankel> >
              hankel> Yes, that's what I mean. Sorry for not writing concisely.
              hankel>
              hankel> > This certainly should be made explicit.
              hankel> So, what is the current status? Is the above property of out_edges
              hankel> already a requirement (though undocumented) of BGL? Or is it just
              hankel> a coincidence that the current implementations in BGL assume the
              hankel> above?

              I would have to say that the current status is that the above property is
              already a requirement, and that this qualifies as a documentation bug.
              I've already updated the descriptions in IncidenceGraph and
              BidirectionalGraph, and added some text to the docs for adjacency_list.

              Thanks for emailing about this!

              Cheers,
              Jeremy



              ----------------------------------------------------------------------
              Jeremy Siek www: http://www.lsc.nd.edu/~jsiek/
              Ph.D. Candidate email: jsiek@...
              Univ. of Notre Dame work phone: (219) 631-3906
              ----------------------------------------------------------------------
            Your message has been successfully submitted and would be delivered to recipients shortly.