0
votes

I am trying to write a function to encode and decode an undirected graph in the format stated.

I understand the format encodes numerical values as readable characters. I read the description here.

I need a simple example that can be done manually at first.

For example steps required to encode and decode a complete graph on 4 vertices, labelled 0 to 3.

The edge list in this case (0,1) (0,2) (0,3) (1,0) (1,2) (1,3) (2,0) (2,1) (2,3) (3,0) (3,1) (3,2)

2

2 Answers

0
votes

I read the description. Lets put it like this:

edge list <--> bit vector <--> decimal vector <--> ASCI II string

Let's use the example stated in the description. Consider a graph with 5 nodes and edges 0-2, 0-4, 1-3 and 3-4. All possible edges on 5 nodes are 0-1,0-2,1-2,0-3,1-3,2-3,0-4,1-4,2-4,3-4. Now you build a bit vector by writing 1 for each edge occurring in this list and 0 otherwise. Hence, you get 0100101001. Next, add zeros to get a multiple of 6 many elements. So, 010010 100100. Convert it to decimal numbers to get 18,36. Now, you can represent your graph with the decimal vector [5+63 18+63 36+63]=[68 81 99] and convert each decimal to an ASCI II character. --> DQc

In short:

0-2,0-4,1-3,3-4 <--> 0100101001 <--> [68 81 99] <--> DQc

0
votes

For example steps required to encode and decode a complete graph on 4 vertices, labelled 0 to 3.

The edge list in this case (0,1) (0,2) (0,3) (1,0) (1,2) (1,3) (2,0) (2,1) (2,3) (3,0) (3,1) (3,2)

Description of graph6 format.

Data type: simple undirected graphs of order 0 to 68719476735.

Your example case is inept, since e. g. the edges 0,1 and 1,0 are one and the same in an undirected graph.