Digraph.Digraph Class Reference

Collaboration diagram for Digraph.Digraph:

Public Member Functions
	__init__ (self, V=0, fn='')
	fromFile (self, fn)
	addEdge (self, v, w)
	adj (self, v)
	reverse (self)
	__str__ (self)

Public Attributes
dict	adjTable_ = {}
int	E = 0
	V = V

Detailed Description

Digraph is an implementation of digraphs which supports
adding edges and reversal

Definition at line 5 of file Digraph.py.

Constructor & Destructor Documentation

__init__()

Digraph.Digraph.__init__	(		self,
			V = 0,
			fn = '' )

Definition at line 9 of file Digraph.py.

    def __init__(self, V=0, fn=''):
        self.adjTable_ = {}
        self.E = 0
        if fn:
            self.fromFile(fn)
        else:
            self.V = V
            for i in range(V):
                self.adjTable_[i] = []
 

Member Function Documentation

__str__()

Digraph.Digraph.__str__

(

self

)

Definition at line 62 of file Digraph.py.

    def __str__(self):
        lines = ['Digraph. V: '+ str(self.V) + ' E: ' + str(self.E)]
        for v in range(self.V):
            for w in self.adj(v):
                lines.append('%d -> %d' % (v, w))
 
        return '\n'.join(lines)

addEdge()

Digraph.Digraph.addEdge	(		self,
			v,
			w )

Definition at line 45 of file Digraph.py.

    def addEdge(self, v, w):
        assert v < self.V
        assert w < self.V
        self.adjTable_[v].append(w)
        self.E += 1
 

adj()

Digraph.Digraph.adj	(		self,
			v )

Definition at line 51 of file Digraph.py.

    def adj(self, v):
        assert v < self.V
        return self.adjTable_[v]
 

fromFile()

Digraph.Digraph.fromFile	(		self,
			fn )

Definition at line 19 of file Digraph.py.

    def fromFile(self, fn):
        state = 'START'
        with open(fn, 'r') as fh:
            for ll in fh:
                l = ll.strip()
                if not l or l.startswith('#'): continue
                
                if state == 'START':
                    self.V = int(l.strip())
                    for i in range(self.V):
                        self.adjTable_[i] = list()
                    state = 'NE'
                    continue
                if state == 'NE':
                    # self.E = int(l.strip())
                    state = 'EDGES'
                    continue
 
                if state == 'EDGES':
                    toks = l.strip().split()
                    assert len(toks) == 2
                    v = int(toks[0])
                    w = int(toks[1])
                    self.addEdge(v, w)
                    continue
    

reverse()

Digraph.Digraph.reverse

(

self

)

Definition at line 55 of file Digraph.py.

    def reverse(self):
        R = Digraph(self.V)
        for v in range(self.V):
            for w in self.adj(v):
                R.addEdge(w, v)
        return R
 

Member Data Documentation

adjTable_

dict Digraph.Digraph.adjTable_ = {}

Definition at line 10 of file Digraph.py.

E

int Digraph.Digraph.E = 0

Definition at line 11 of file Digraph.py.

V

Digraph.Digraph.V = V

Definition at line 15 of file Digraph.py.

---

The documentation for this class was generated from the following file:

• Digraph.py