Opened 9 years ago

Closed 10 months ago

#14657 closed defect (fixed)

Document that set_embedding fails for multigraphs

Reported by: nvcleemp Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-9.5
Component: graph theory Keywords:
Cc: tscrim Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 00de6e6 (Commits, GitHub, GitLab) Commit: 00de6e6d69b40c7e0c9ad207628854292b237bdb
Dependencies: Stopgaps:

Status badges


If you try to set the embedding for a multigraph, you will get an error if you specify all edges. If you bundle each multi-edge into a single edge it works. The following code, e.g., gives an error:

h = Graph({1:[2], 2:[3,3], 3:[]})
h.set_embedding({1:[2], 2:[1,3,3], 3:[2,2]})

The cause of this is the following lines in the method check_embedding_validity:

if len(embedding[v]) != len(self.neighbors(v)):
    return False

A multigraph returns each neighbour only once, and not the number of times that there are edges between these two vertices.

Is this the desired behaviour? If so, then maybe some documentation needs to be added to warn the user that this will not work. If not, how do we change it? Should the method neighbors return the 'multiset' of neighbours and not just the 'set'?

Change History (11)

comment:1 Changed 9 years ago by nvcleemp

  • Status changed from new to needs_info

comment:2 Changed 9 years ago by nvcleemp

Hmm, probably this is not supported, because specifying an embedding like this is not unambiguous. For an edge with multiplicity more than one, you know the order around each vertex, but you don't know which edge around the first vertex corresponds to which edge around the second vertex.

comment:3 Changed 9 years ago by nvcleemp

There is of course a way to get unambiguous embeddings for multigraphs (with loops). Number all edges and instead of listing the neighbours around each vertex, you list all the edges around each vertex.

Is this something that should be added to Sage? Possibly in parallel with the current system of listing all neighbours around each vertex?

comment:4 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 9 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 11 months ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/graphs/14657_set_embedding
  • Cc tscrim added
  • Commit set to 00de6e6d69b40c7e0c9ad207628854292b237bdb
  • Milestone changed from sage-6.4 to sage-9.5
  • Status changed from needs_info to needs_review

With this branch, we clearly say that the method does not work for graphs with loops or multiple edges.

New commits:

00de6e6trac #14657: better documentation for set_embedding

comment:9 Changed 11 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

This will work for now, but probably in the long-term we will want to have a multigraph embedding.

comment:10 Changed 10 months ago by slelievre

  • Summary changed from set_embedding fails for multigraphs to Document that set_embedding fails for multigraphs

comment:11 Changed 10 months ago by vbraun

  • Branch changed from public/graphs/14657_set_embedding to 00de6e6d69b40c7e0c9ad207628854292b237bdb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.