Big Graph In Memory

I want to record all used ports within huge pcaps. There are 65535 ports available, and each port is able to talk each other port: 65535 x 65535 links in total The matrix will be v

Solution 1:

In Python, and depending on how sparse is sparse, a dict-of-dicts will handle this quite well.

connections = { ..., 8080: { 4545:17, 20151:3, ...}, ...}

If I have understood what you are doing correctly, then the count of connections to port p is

count = sum( connections[8080].values() )

removing port p is

delconnections[p]forconninconnections.values():  # edit, bugfixed.
    ifpinconn: 
         delconn[p]

If you want to try to save memory by storing only half the pairs, then simplicity suffers greatly.

Solution 2:

Look into the adjacency list representation of Graph, it will most probably suits your needs.

However, a graph containing 65535 vertices is not that big. Even if you cannot represent it with a simple matrix.

The memory consumption is O(E+V) with V number of vertices (65535) and E number of edges (on a sparse graph, it has the same magnitude order than V).