How do I store this in an adjacency list for graphs in python?
<p>Suppose I have a text file containing this:</p>

<pre><code>0 1 4
0 2 3
1 4 7
5 3 8
</code></pre>

<p>The columns represent:</p>

<ol>
<li>a vertex</li>
<li>another vertex</li>
<li>the distance between these two vertices.  </li>
</ol>

<p>For example, in the first line in the text file, 4 is the distance between points 0 and 1.  </p>

<p>So how would I store the vertices and distances in an adjacency list in python?</p>

<p>In graph theory, an <a href="https://en.wikipedia.org/wiki/Adjacency_list" rel="nofollow">adjacent-list</a>, is a collection of unordered lists used to represent a graph. Each list describes the set of neighbors of a vertex in the graph.</p>

<p>Since you are talking about adjacent list of weighted graph, you need to define a structure to store both <code>vertex</code> and <code>weight</code>. A graph theory or data structure way to implement adjacent list is like this:</p>

<pre><code>class Node():
    def __init__(self, v, w, next=None):
        self.v = v
        self.w = w
        self.next = next
    ...

class LinkedList():
    def __init__(self, head=None)
        self.head = head

    def add_node():
        pass
    ...
</code></pre>

<p>Here <code>Node</code> class is the base element to compose <code>LinkedList</code> and <code>LinkedList</code> is used to represent adjacent list of one vertex. I do not implement the whole classes for you. See <a href="https://www.codefellows.org/blog/implementing-a-singly-linked-list-in-python/" rel="nofollow">python-linked-list</a>. </p>

<p>Assuming your graph is <strong>directed</strong>, the adjacent list of this graph is:</p>

<pre><code>0 -&gt; [1:4]-&gt; [2:3]
1 -&gt; [4:7]
2 -&gt; []
3 -&gt; []
4 -&gt; []
5 -&gt; [3:8]
</code></pre>

<p>in which, <code>0 -&gt; [1:4] -&gt; [2:3]</code> represents the adjacent list of vertex <code>0</code>, which contains two edges: <code>0-&gt;1</code> with weight <code>4</code> and <code>0-&gt;2</code> with weight <code>3</code>. <code>[1:4]</code> could be described by class <code>Node</code>, and the whole row could be represented by class <code>LinkedList</code>.  Check <a href="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/weighted.html" rel="nofollow">weighted-graph-adjacent-list</a> for more information.</p>

<p>To represent the whole graph, you can simply use a list of <code>LinkedList</code>, e.g., </p>

<pre><code>g = [LinkedList_for_0, LinkedList_for_1, ...]
</code></pre>

<p>In this approach, <code>g[i]</code> will be the adjacent list of vertex <code>i</code>. </p>

<p>To build the whole graph, you can iterate over all edges:</p>

<pre><code>g = [[] for v in range(number_of_vertex)]
for f, t, w in edges:
    g[f].add_node(Node(t,w))
</code></pre>

<p>In above, as I said, <strong>it's a more data structure way</strong> to implement the adjacent list. If you would to practice your understanding of data structure and graph theory knowledge, you can try this way. But, actually, unlike <code>C/C++</code> <code>array</code> type (fixed size), python <code>list</code> is a mutable type, you can do operations like add, delete on a python <code>list</code>.  So <code>LinkedList</code> is actually unnecessarily needed. We can redefine the these classes in a <strong>pythonic way</strong>:</p>

<pre><code>class Node():
    def __init__(self, v, w):
        self.v = v
        self.w = w
</code></pre>

<p>Here, the <code>Node</code> class do not contain <code>next</code> member. So the adjacent list can be represented as a list of <code>Node</code>, e.g., adjacent list of vertex <code>0</code>:</p>

<pre><code>[Node(1,4), Node(2,3)]
</code></pre>

<p>And the whole graph can be represented as a two dimensional list (Here we assume this is a <strong>undirected</strong> graph.):</p>

<pre><code>[
 [Node(1,4), Node(2,3)],
 [Node(0,4), Node(4,7)],
 [Node(0,3)],
 [Node(5,8)],
 [Node(1,7)],
 [Node(3,8)]
] 
</code></pre>

<p>The python way algorithm:</p>

<pre><code>g = [[] for v in range(number_of_vertex)]
for f,t,w in edges:
    g[f].append(Node(t,w))
    g[t].append(Node(f,w))
</code></pre>

<p>Note: you need to add a new node for <strong>both ends of an edge</strong>.</p>

<p>In practice, when handling graph problems, I believe edge-list or sparse matrix is the most common representation. So if it possible, I would suggest you used this kind of representation. </p>

<p>Thanks.</p>

python adjacency-list