Databases
StackOverflow2013
Postsdbo
POWhy is my adjacency list showing duplicate edges?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy is my adjacency list showing duplicate edges?
    primarykey
    data
    text
    <pre><code> #include &lt;iostream&gt; using namespace std; struct node { int v; node* next; node (int x, node* t) { v = x; next = t; } }; typedef node *link; int **malloc2d(int, int); void printMatrix(int **, int); link *convertToList (int **, link *, int); void printList (link * a, int size); // program begins function execution int main () { // input number of vertices int i, j, V; cout &lt;&lt; "Enter the number of vertices: "; cin &gt;&gt; V; int **adj = malloc2d(V, V); // dynamically allocate matrix for (i = 0; i &lt; V; i++) // initialize matrix with 0's for (j = 0; j &lt; V; j++) adj[i][j] = 0; for (i = 0; i &lt; V; i++) // initialize diagonal with 1's adj[i][i] = 1; // input the edges cout &lt;&lt; "Enter the coordinates for an edge (or 'Ctrl' + 'Z'): "; while (cin &gt;&gt; i &gt;&gt; j) { adj[i][j] = 1; adj[j][i] = 1; cout &lt;&lt; "Enter the coordinates for an edge (or 'Ctrl' + 'Z'): "; } // convert to list link *aList = new link [V]; aList = convertToList(adj, aList, V); cout &lt;&lt; endl; // print matrix cout &lt;&lt; "Adjacency Matrix: " &lt;&lt; endl; printMatrix (adj, V); cout &lt;&lt; endl &lt;&lt; endl; // print adjacency list cout &lt;&lt; "Adjacency List: " &lt;&lt; endl; printList (aList, V); return 0; // indicates successful completion } // end function main int **malloc2d(int r, int c) { int **t = new int*[r]; for (int i = 0; i &lt; r; i++) t[i] = new int[c]; return t; } // end function malloc2d void printMatrix (int ** a, int size) { for (int i = 0; i &lt; size; i++) for (int j = 0; j &lt; size; j++) if (a[i][j] == 1) cout &lt;&lt; "There is an edge between " &lt;&lt; i &lt;&lt; " and " &lt;&lt; j &lt;&lt; "." &lt;&lt; endl; } // end function print link *convertToList (int ** b, link * a, int size) { // create array for (int i = 0; i &lt; size; i++) a[i] = 0; // create lists for (int i = 0; i &lt; size; i++) for (int j = i; j &lt; size; j++) { if (b[i][j] == 1) // if an edge exists on the matrix { // create the edges on the adjacency list a[j] = new node(i, a[j]); a[i] = new node(j, a[i]); } } return a; } // end function convertToList void printList (link * a, int size) { for (int i = 0; i &lt; size; i++) { while (a[i]-&gt;next != NULL) { cout &lt;&lt; "There is an edge between " &lt;&lt; i &lt;&lt; " and " &lt;&lt; a[i]-&gt;v &lt;&lt; "." &lt;&lt; endl; a[i] = a[i]-&gt;next; } } } // end function print </code></pre> <p><em>convertToList</em>: converts an adjacency matrix into an adjacency list.</p> <p><em>printList</em>: traverses the adjacency matrix and prints a message for every edge.</p> <p><strong>Problem:</strong> Some edges are being duplicated. I'm not sure if it is a problem when I create the array of lists or when I traverse the adjacency matrix to print it. Any suggestions?</p> <p>Below is a picture of the program output for 5 vertices with edges (0, 1) and (3, 2). The matrix is correct. The adjacency list is not. Edges (0, 1), (1, 1) and (2, 3) should not be repeated.</p> <p><img src="https://militarystudents.files.wordpress.com/2010/02/adjacency_list.png?w=450" alt="alt text"></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USBrandon
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhy is my adjacency list showing duplicate edges?
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POWhy is my adjacency list showing duplicate edges?
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO-1 for what? This is a programming question . . .
      singulars
      1. POWhy is my adjacency list showing duplicate edges?
      1. USBrandon
    2. COProbably because of the coexistence of a 1 in (i,j) and (j,i) positions. But anyway, why don't you use an std::set of edges? And the line "a[j] = new node(i, a[j]);" looks _very_ awkward...
      singulars
      1. POWhy is my adjacency list showing duplicate edges?
      1. USDaniel Daranas
    3. COWhat does a `link` look like inside? Where's the definition?
      singulars
      1. POWhy is my adjacency list showing duplicate edges?
      1. USOmnifarious
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload