C#. Undirected Graph Basics Altogether

Graph

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    public class Graph
    {
        public int V { get; set; }
        public int E { get; set; }
        public Bag<int>[] adj;
        public Graph(int V) // init empty graph with V verticles
        {
            if (V < 0)
            {
                throw new ArgumentException();
            }

            this.V = V;
            this.E = 0;
            adj = new Bag<int>[V];
            for (int v = 0; v <= V; v++)
            {
                adj[v] = new Bag<int>();
            }
        }
        public Graph(string aFilePath) // init graph from filePath
        {
       
            if (!File.Exists(aFilePath)) throw new Exception("file not exists");
            string[] ReadText = File.ReadAllLines(aFilePath);
            this.V = Convert.ToInt32(ReadText[0]);
            this.E = 0; //Convert.ToInt32(ReadText[1]);
            // init adj obj
            adj = new Bag<int>[V];
            for (int v = 0; v < V; v++)
            {
                adj[v] = new Bag<int>();
            }
            for (var i = 2; i < ReadText.Length; i++)
            {
                string[] splitted;
                splitted = ReadText[i].Split(' ');
                //if (splitted.Count<string> = 2)
                {
                    int v = Convert.ToInt32(splitted[0]);
                    int w = Convert.ToInt32(splitted[1]);
                    this.AddEdge(v, w);
                }

            }
        }
        // vertices and edges
        public int Vertices() { return V; }
        public int Edges() { return E; }
        public void ValidateVertex(int v)
        {
            if (v < 0 || v > V) { throw new ArgumentException(); }
        }
        // adding undirected edge to the graph
        public void AddEdge(int v, int w)
        {
            ValidateVertex(v);
            ValidateVertex(w);
            E++;
            adj[v].Push(w);
            adj[w].Push(v);
        }
        //returns vertices adjacent to vertex
        public Bag<int> AdjacentVerticles(int v)
        {
            ValidateVertex(v);
            return adj[v];
        }
        // returns degree of vertex
        public int Degree(int v)
        {
            ValidateVertex(v);
            return adj[v].Size();
        }
        // returns string representation of Graph
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append(V + " vertices, " + E + " edges " + "\n");
            for (var v = 0; v < V; v++)
            {
                sb.Append(v + ":");
                foreach (int w in adj[v])
                {
                    sb.Append(w + " ");
                }
                sb.AppendLine();
            }
            return sb.ToString();
        }
    }
}

100

101

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

public class Graph

{

public int V { get; set; }

public int E { get; set; }

public Bag<int>[] adj;

public Graph(int V) // init empty graph with V verticles

{

if (V < 0)

{

throw new ArgumentException();

}

this.V = V;

this.E = 0;

adj = new Bag<int>[V];

for (int v = 0; v <= V; v++)

{

adj[v] = new Bag<int>();

}

public Graph(string aFilePath) // init graph from filePath

{

if (!File.Exists(aFilePath)) throw new Exception("file not exists");

string[] ReadText = File.ReadAllLines(aFilePath);

this.V = Convert.ToInt32(ReadText[0]);

this.E = 0; //Convert.ToInt32(ReadText[1]);

// init adj obj

adj = new Bag<int>[V];

for (int v = 0; v < V; v++)

{

adj[v] = new Bag<int>();

}

for (var i = 2; i < ReadText.Length; i++)

{

string[] splitted;

splitted = ReadText[i].Split(' ');

//if (splitted.Count<string> = 2)

{

int v = Convert.ToInt32(splitted[0]);

int w = Convert.ToInt32(splitted[1]);

this.AddEdge(v, w);

}

// vertices and edges

public int Vertices() { return V; }

public int Edges() { return E; }

public void ValidateVertex(int v)

{

if (v < 0 || v > V) { throw new ArgumentException(); }

}

// adding undirected edge to the graph

public void AddEdge(int v, int w)

{

ValidateVertex(v);

ValidateVertex(w);

E++;

adj[v].Push(w);

adj[w].Push(v);

}

//returns vertices adjacent to vertex

public Bag<int> AdjacentVerticles(int v)

{

ValidateVertex(v);

return adj[v];

}

// returns degree of vertex

public int Degree(int v)

{

ValidateVertex(v);

return adj[v].Size();

}

// returns string representation of Graph

public override string ToString()

{

StringBuilder sb = new StringBuilder();

sb.Append(V + " vertices, " + E + " edges " + "\n");

for (var v = 0; v < V; v++)

{

sb.Append(v + ":");

foreach (int w in adj[v])

{

sb.Append(w + " ");

}

sb.AppendLine();

}

return sb.ToString();

}

Bag

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    public class Bag<T> : IEnumerable<T>
    {
        Node<T> first;
        private int N;
        class Node<T>
        {
            public T item;
            public Node<T> next;
        }
        public bool IsEmpty() { return (first == null) || (N == 0); }
        public int Size() { return N; }
        public void Push(T item) // adding to the begining always
        {
            Node<T> tempNode = first;
            first = new Node<T>();
            first.item = item;
            first.next = tempNode;
            N++;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<T> GetEnumerator()
        {
            var node = first;
            while (node != null)
            {
                yield return node.item;
                node = node.next;
            }
        }
    }
}

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

public class Bag<T> : IEnumerable<T>

{

Node<T> first;

private int N;

class Node<T>

{

public T item;

public Node<T> next;

}

public bool IsEmpty() { return (first == null) || (N == 0); }

public int Size() { return N; }

public void Push(T item) // adding to the begining always

{

Node<T> tempNode = first;

first = new Node<T>();

first.item = item;

first.next = tempNode;

N++;

}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()

{

return GetEnumerator();

}

public IEnumerator<T> GetEnumerator()

{

var node = first;

while (node != null)

{

yield return node.item;

node = node.next;

}

DFS

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    public class DepthFirstSearch
    {
        private Boolean[] isMarked;
        private int count;
        public DepthFirstSearch(Graph G, int s) // s - source vertex
        {
            isMarked = new Boolean[G.V];
            // validate vertex
            validateVertex(s);
            dfs(G, s);
        }

        // depth first search
        private void dfs(Graph G, int v)
        {
            // do smth with vertex
            isMarked[v] = true;
            count++;
            // go deep
            foreach (var w in G.adj[v])
            {
                if (!isMarked[w])
                    dfs(G, v);
            }
        }

        // validation
        private void validateVertex(int v)
        {
            int V = isMarked.Length;
            if (v < 0 || v >= V)
            {
                throw new ArgumentException();
            }
        }
        // is path beetwen s and v
        public Boolean Marked(int v)
        {
            validateVertex(v);
            return isMarked[v];
        }
        /**
    * Returns the number of vertices connected to the source vertex {@code s}.
    * @return the number of vertices connected to the source vertex {@code s}
    */
        public int Count()
        {
            return count;
        }


    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

public class DepthFirstSearch

{

private Boolean[] isMarked;

private int count;

public DepthFirstSearch(Graph G, int s) // s - source vertex

{

isMarked = new Boolean[G.V];

// validate vertex

validateVertex(s);

dfs(G, s);

}

// depth first search

private void dfs(Graph G, int v)

{

// do smth with vertex

isMarked[v] = true;

count++;

// go deep

foreach (var w in G.adj[v])

{

if (!isMarked[w])

dfs(G, v);

}

// validation

private void validateVertex(int v)

{

int V = isMarked.Length;

if (v < 0 || v >= V)

{

throw new ArgumentException();

}

// is path beetwen s and v

public Boolean Marked(int v)

{

validateVertex(v);

return isMarked[v];

}

/**

* Returns the number of vertices connected to the source vertex {@code s}.

* @return the number of vertices connected to the source vertex {@code s}

public int Count()

{

return count;

}

DFS Path

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    //https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/DepthFirstPaths.java.html
    class DepthFirstPaths
    {
        private Boolean[] isMarked; // marked[v] = is there an s-v path?
        private int[] edgeTo; // // edgeTo[v] = last edge on s-v path
        private int s; // source vertex
        DepthFirstPaths(Graph G, int s)
        {
            this.s = s;
            edgeTo = new int[G.V];
            isMarked = new Boolean[G.V];
            ValidateVertex(s);
        }
        // depth first search from v
        private void dfs(Graph G, int v)
        {
            isMarked[v] = true;
            foreach (var w in G.adj[v])
            {
                if (!isMarked[w])
                {
                    edgeTo[w] = v; // last edge 
                    dfs(G, w);
                }
            }
        }
        //  Is there a path between the source vertex {@code s} and vertex {@code v}?
        public Boolean hasPathTo(int v)
        {
            ValidateVertex(v);
            return isMarked[v];
        }
        // Returns a path between the source vertex {@code s} and vertex {@code v}, or
        // * {@code null} if no such path.
        public IEnumerable<int> pathTo(int v)
        {
            ValidateVertex(v);
            if (!hasPathTo(v)) return null;
            Stack<int> path = new Stack<int>();
            for (int x = v; x != s; x = edgeTo[x])            
                path.Push(x);            
            path.Push(s); 
            return path;
        }
        //

        // validation
        private void ValidateVertex(int v)
        {
            int V = isMarked.Length;
            if (v < 0 || v >= V)
            {
                throw new ArgumentException();
            }
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

//https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/DepthFirstPaths.java.html

class DepthFirstPaths

{

private Boolean[] isMarked; // marked[v] = is there an s-v path?

private int[] edgeTo; // // edgeTo[v] = last edge on s-v path

private int s; // source vertex

DepthFirstPaths(Graph G, int s)

{

this.s = s;

edgeTo = new int[G.V];

isMarked = new Boolean[G.V];

ValidateVertex(s);

}

// depth first search from v

private void dfs(Graph G, int v)

{

isMarked[v] = true;

foreach (var w in G.adj[v])

{

if (!isMarked[w])

{

edgeTo[w] = v; // last edge

dfs(G, w);

}

// Is there a path between the source vertex {@code s} and vertex {@code v}?

public Boolean hasPathTo(int v)

{

ValidateVertex(v);

return isMarked[v];

}

// Returns a path between the source vertex {@code s} and vertex {@code v}, or

// * {@code null} if no such path.

public IEnumerable<int> pathTo(int v)

{

ValidateVertex(v);

if (!hasPathTo(v)) return null;

Stack<int> path = new Stack<int>();

for (int x = v; x != s; x = edgeTo[x])

path.Push(x);

path.Push(s);

return path;

}

// validation

private void ValidateVertex(int v)

{

int V = isMarked.Length;

if (v < 0 || v >= V)

{

throw new ArgumentException();

}

BFS

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    //https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BreadthFirstPaths.java.html
    class BreadthFirstPaths
    {
        private bool[] marked; //marked[v] = is there an s-v path
        private int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path
        private int[] distTo;  // distTo[v] = number of edges shortest s-v path
        private int infinity = int.MaxValue; // some infinity integer
        public BreadthFirstPaths(Graph G, IEnumerable<int> sources)
        {
            marked = new bool[G.V];
            distTo = new int[G.V];
            edgeTo = new int[G.V];
            for (int v = 0; v < G.V; v++) distTo[v] = infinity;
            ValidateVertices(sources);
        }
        // breadth-first search from a single source
        private void Bfs(Graph G, int s)
        {
            Queue<int> q = new Queue<int>();
            for (int v = 0; v < G.V; v++) distTo[v] = infinity;
            distTo[s] = 0;
            marked[s] = true;
            q.Enqueue(s);
            while (q.Count!=0)
            {
                int v = q.Dequeue();
                foreach (int w in G.adj[v])
                {
                    if (!marked[w])
                    {
                        edgeTo[w] = v;
                        distTo[w] = distTo[v] + 1;
                        marked[w] = true;
                        q.Enqueue(w);
                    }
                }
            }
        }
        // breadth-first search from multiple sources
        private void bfs(Graph G, IEnumerable<int> sources)
        {
            Queue<int> q = new Queue<int>();
            foreach (int s in sources)
            {
                marked[s] = true;
                distTo[s] = 0;
                q.Enqueue(s);
            }
            while (q.Count != 0)
            {
                int v = q.Dequeue();
                foreach (int w in G.adj[v])
                {
                    if (!marked[w])
                    {
                        edgeTo[w] = v;
                        distTo[w] = distTo[v] + 1;
                        marked[w] = true;
                        q.Enqueue(w);
                    }
                }
            }
        }
        //Is there a path between the source vertex {@code s} (or sources) and vertex {@code v}?
        public Boolean HasPathTo(int v)
        {
            ValidateVertex(v);
            return marked[v];
        }
        // throw an IllegalArgumentException unless {@code 0 <= v < V}
        private void ValidateVertex(int v)
        {
            int V = marked.Length;
            if (v < 0 || v >= V)
                throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }

        //Returns the number of edges in a shortest path between the source vertex {@code s}
        public int DistanceTo(int v)
        {
            ValidateVertex(v);
            return distTo[v];
        }
        /** Returns a shortest path between the source vertex {@code s} (or sources)
     * and {@code v}, or {@code null} if no such path.*/
        public IEnumerable<int> ShortestPathTo(int v)
        {
            ValidateVertex(v);
            if (!HasPathTo(v)) return null;
            Stack<int> path = new Stack<int>();
            int x;
            for (x = v; DistanceTo(x) != 0; x = edgeTo[x])
            {
                path.Push(x);
            }
            path.Push(x);
            return path;
        }

        // throw an IllegalArgumentException unless {@code 0 <= v < V}
        private void ValidateVertices(IEnumerable<int> vertices)
        {
            if (vertices == null)
            {
                throw new ArgumentException("argument is null");
            }
            int V = marked.Length;
            foreach (int v in vertices)
            {
                if (v < 0 || v >= V)
                {
                    throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
                }
            }
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

//https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BreadthFirstPaths.java.html

class BreadthFirstPaths

{

private bool[] marked; //marked[v] = is there an s-v path

private int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path

private int[] distTo; // distTo[v] = number of edges shortest s-v path

private int infinity = int.MaxValue; // some infinity integer

public BreadthFirstPaths(Graph G, IEnumerable<int> sources)

{

marked = new bool[G.V];

distTo = new int[G.V];

edgeTo = new int[G.V];

for (int v = 0; v < G.V; v++) distTo[v] = infinity;

ValidateVertices(sources);

}

// breadth-first search from a single source

private void Bfs(Graph G, int s)

{

Queue<int> q = new Queue<int>();

for (int v = 0; v < G.V; v++) distTo[v] = infinity;

distTo[s] = 0;

marked[s] = true;

q.Enqueue(s);

while (q.Count!=0)

{

int v = q.Dequeue();

foreach (int w in G.adj[v])

{

if (!marked[w])

{

edgeTo[w] = v;

distTo[w] = distTo[v] + 1;

marked[w] = true;

q.Enqueue(w);

}

// breadth-first search from multiple sources

private void bfs(Graph G, IEnumerable<int> sources)

{

Queue<int> q = new Queue<int>();

foreach (int s in sources)

{

marked[s] = true;

distTo[s] = 0;

q.Enqueue(s);

}

while (q.Count != 0)

{

int v = q.Dequeue();

foreach (int w in G.adj[v])

{

if (!marked[w])

{

edgeTo[w] = v;

distTo[w] = distTo[v] + 1;

marked[w] = true;

q.Enqueue(w);

}

//Is there a path between the source vertex {@code s} (or sources) and vertex {@code v}?

public Boolean HasPathTo(int v)

{

ValidateVertex(v);

return marked[v];

}

// throw an IllegalArgumentException unless {@code 0 <= v < V}

private void ValidateVertex(int v)

{

int V = marked.Length;

if (v < 0 || v >= V)

throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));

}

//Returns the number of edges in a shortest path between the source vertex {@code s}

public int DistanceTo(int v)

{

ValidateVertex(v);

return distTo[v];

}

/** Returns a shortest path between the source vertex {@code s} (or sources)

* and {@code v}, or {@code null} if no such path.*/

public IEnumerable<int> ShortestPathTo(int v)

{

ValidateVertex(v);

if (!HasPathTo(v)) return null;

Stack<int> path = new Stack<int>();

int x;

for (x = v; DistanceTo(x) != 0; x = edgeTo[x])

{

path.Push(x);

}

path.Push(x);

return path;

}

// throw an IllegalArgumentException unless {@code 0 <= v < V}

private void ValidateVertices(IEnumerable<int> vertices)

{

if (vertices == null)

{

throw new ArgumentException("argument is null");

}

int V = marked.Length;

foreach (int v in vertices)

{

if (v < 0 || v >= V)

{

throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));

}

Connected Components Graph

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    public class CC // connected components Graph
    {
        private bool[] marked;  // marked[v] = has vertex v been marked?
        private int[] idGroup; // id[v] = id of connected component containing v
        private int[] size; // size[id] = number of vertices in given component
        private int count; // number of connected components
        public CC(Graph G)
        {
            marked = new bool[G.V];
            idGroup = new int[G.V];
            size = new int[G.V];
        }
        // depth-first search for a Graph
        private void Dfs(Graph G, int v)
        {
            marked[v] = true;
            idGroup[v] = count;
            size[count]++;
            foreach (int w in G.adj[v])
            {
                if (!marked[w]) Dfs(G, w);
                count++;
            }
        }
        public int GetId(int v)
        {
            ValidateVertex(v);
            return idGroup[v];
        }
        // throw an IllegalArgumentException unless {@code 0 <= v < V}
        private void ValidateVertex(int v)
        {
            int V = marked.Length;
            if (v < 0 || v >= V)
                throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }
        public int getCount()
        {
            return count;
        }
        public bool IsConnected(int v, int w)
        {
            ValidateVertex(v);
            ValidateVertex(w);
            return GetId(v) == GetId(w);
        }
        public int GetSize(int v)
        {
            ValidateVertex(v);
            return size[idGroup[v]];
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

public class CC // connected components Graph

{

private bool[] marked; // marked[v] = has vertex v been marked?

private int[] idGroup; // id[v] = id of connected component containing v

private int[] size; // size[id] = number of vertices in given component

private int count; // number of connected components

public CC(Graph G)

{

marked = new bool[G.V];

idGroup = new int[G.V];

size = new int[G.V];

}

// depth-first search for a Graph

private void Dfs(Graph G, int v)

{

marked[v] = true;

idGroup[v] = count;

size[count]++;

foreach (int w in G.adj[v])

{

if (!marked[w]) Dfs(G, w);

count++;

}

public int GetId(int v)

{

ValidateVertex(v);

return idGroup[v];

}

// throw an IllegalArgumentException unless {@code 0 <= v < V}

private void ValidateVertex(int v)

{

int V = marked.Length;

if (v < 0 || v >= V)

throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));

}

public int getCount()

{

return count;

}

public bool IsConnected(int v, int w)

{

ValidateVertex(v);

ValidateVertex(w);

return GetId(v) == GetId(w);

}

public int GetSize(int v)

{

ValidateVertex(v);

return size[idGroup[v]];

}

Cycle

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    // https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Cycle.java.html
    class Cycle
    {
        private bool[] marked;
        private int[] edgeTo;
        private Stack<int> cycle;
        /**
    * Determines whether the undirected graph {@code G} has a cycle and,
    * if so, finds such a cycle.
    *
    * @param G the undirected graph
    */
        public Cycle(Graph G)
        {
            if (HasSelfLoop(G)) return;
            if (HasParallelEdges(G)) return;
            marked = new bool[G.V];
            edgeTo = new int[G.V];
            for (int v = 0; v < G.V; v++)
            {
                if (!marked[v]) Dfs(G, -1, v);
            }
        }
        // u-v like path here
        private void Dfs(Graph G, int u, int v)
        {
            marked[v] = true;
            foreach (int w in G.adj[v])
            {
                if (cycle != null) return;
                if (!marked[v])
                {
                    edgeTo[w] = v;
                    Dfs(G, v, w);
                }
                // already marked[v] and again - means cycle
                else if (w != u)
                {
                    // writing cycle to stack
                    cycle = new Stack<int>();
                    for (int x = 0; x != w; x = edgeTo[x])
                        cycle.Push(x);
                    cycle.Push(w);
                    cycle.Push(v);
                }
            }
        }
        // does this graph have two parallel edges?
        // side effect: initialize cycle to be two parallel edges
        private bool HasParallelEdges(Graph G)
        {
            marked = new bool[G.V];
            for (int v = 0; v < G.V; v++)
            {
                foreach (int w in G.adj[v])
                {
                    if (marked[w])
                    {
                        cycle = new Stack<int>();
                        cycle.Push(v);
                        cycle.Push(w);
                        cycle.Push(v);
                        return true;
                    }
                    marked[w] = true;
                }
                //reset all marked to false
                foreach (int w in G.adj[v])
                {
                    marked[w] = false;
                }
            }
            return false;
        }
        // does this graph have a self loop?
        // side effect: initialize cycle to be self loop
        private bool HasSelfLoop(Graph G)
        {
            for (int v = 0; v < G.V; v++)
            {
                foreach (var w in G.adj[v])
                {
                    if (v == w)
                    {
                        cycle = new Stack<int>();
                        cycle.Push(v);
                        cycle.Push(v);
                        return true;
                    }
                }
            }
            return false;
        }

        public bool HasCycle()
        {
            return cycle != null;
        }
    }
}

100

101

102

103

104

105

106

107

108

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

// https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Cycle.java.html

class Cycle

{

private bool[] marked;

private int[] edgeTo;

private Stack<int> cycle;

/**

* Determines whether the undirected graph {@code G} has a cycle and,

* if so, finds such a cycle.

* @param G the undirected graph

public Cycle(Graph G)

{

if (HasSelfLoop(G)) return;

if (HasParallelEdges(G)) return;

marked = new bool[G.V];

edgeTo = new int[G.V];

for (int v = 0; v < G.V; v++)

{

if (!marked[v]) Dfs(G, -1, v);

}

// u-v like path here

private void Dfs(Graph G, int u, int v)

{

marked[v] = true;

foreach (int w in G.adj[v])

{

if (cycle != null) return;

if (!marked[v])

{

edgeTo[w] = v;

Dfs(G, v, w);

}

// already marked[v] and again - means cycle

else if (w != u)

{

// writing cycle to stack

cycle = new Stack<int>();

for (int x = 0; x != w; x = edgeTo[x])

cycle.Push(x);

cycle.Push(w);

cycle.Push(v);

}

// does this graph have two parallel edges?

// side effect: initialize cycle to be two parallel edges

private bool HasParallelEdges(Graph G)

{

marked = new bool[G.V];

for (int v = 0; v < G.V; v++)

{

foreach (int w in G.adj[v])

{

if (marked[w])

{

cycle = new Stack<int>();

cycle.Push(v);

cycle.Push(w);

cycle.Push(v);

return true;

}

marked[w] = true;

}

//reset all marked to false

foreach (int w in G.adj[v])

{

marked[w] = false;

}

return false;

}

// does this graph have a self loop?

// side effect: initialize cycle to be self loop

private bool HasSelfLoop(Graph G)

{

for (int v = 0; v < G.V; v++)

{

foreach (var w in G.adj[v])

{

if (v == w)

{

cycle = new Stack<int>();

cycle.Push(v);

return true;

}

return false;

}

public bool HasCycle()

{

return cycle != null;

}

Bipartite

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    class Bipartite
    {
        public bool IsBipartite { get; set; } // is the graph bipartite?
        private bool[] color; // color[v] gives vertices on one side of bipartition
        private bool[] marked; // marked[v] = true if v has been visited in DFS
        private int[] edgeTo; // edgeTo[v] = last edge on path to v
        private Stack<int> cycle; // odd-length cycle
                                  /**
                               * Determines whether an undirected graph is bipartite and finds either a
                               * bipartition or an odd-length cycle.
                               *
                               * @param  G the graph
                               */
        public Bipartite(Graph G)
        {
            IsBipartite = true;
            color = new bool[G.V];
            marked = new bool[G.V];
            edgeTo = new int[G.V];
            for (int v = 0; v < G.V; v++)
            {
                if (!marked[v]) { }
            }
        }
        private void Dfs(Graph G, int v)
        {
            foreach (int w in G.adj[v])
            {
                if (cycle != null) return;
                if (!marked[w])
                {
                    edgeTo[w] = v;
                    color[w] = !color[v];
                    Dfs(G, v);
                }
                else if (color[w] == color[v])
                {
                    IsBipartite = false;
                    cycle = new Stack<int>();
                    cycle.Push(w); // don't need this unless you want to include start vertex twice
                    for (int x = v; x != w; x = edgeTo[x])
                    {
                        cycle.Push(x);
                    }
                    cycle.Push(w);
                }
            }
        }
        public bool GetColor(int v)
        {
            ValidateVertex(v);
            if (!IsBipartite) throw new Exception("not Bipartite");
            return color[v];
        }
        public IEnumerable<int> OddCycle()
        {
            return cycle;
        }
        public bool IsBipartiteCheck(Graph G)
        {
            for (int v = 0; v < G.V; v++)
            {
                foreach (var w in G.adj[v])
                {
                    if (color[w] == color[v]) return false;
                }
            }
            return true;
        }
        private void ValidateVertex(int v)
        {
            int V = marked.Length;
            if (v < 0 || v >= V) throw new ArgumentException("wrong vertex");
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

class Bipartite

{

public bool IsBipartite { get; set; } // is the graph bipartite?

private bool[] color; // color[v] gives vertices on one side of bipartition

private bool[] marked; // marked[v] = true if v has been visited in DFS

private int[] edgeTo; // edgeTo[v] = last edge on path to v

private Stack<int> cycle; // odd-length cycle

/**

* Determines whether an undirected graph is bipartite and finds either a

* bipartition or an odd-length cycle.

* @param G the graph

public Bipartite(Graph G)

{

IsBipartite = true;

color = new bool[G.V];

marked = new bool[G.V];

edgeTo = new int[G.V];

for (int v = 0; v < G.V; v++)

{

if (!marked[v]) { }

}

private void Dfs(Graph G, int v)

{

foreach (int w in G.adj[v])

{

if (cycle != null) return;

if (!marked[w])

{

edgeTo[w] = v;

color[w] = !color[v];

Dfs(G, v);

}

else if (color[w] == color[v])

{

IsBipartite = false;

cycle = new Stack<int>();

cycle.Push(w); // don't need this unless you want to include start vertex twice

for (int x = v; x != w; x = edgeTo[x])

{

cycle.Push(x);

}

cycle.Push(w);

}

public bool GetColor(int v)

{

ValidateVertex(v);

if (!IsBipartite) throw new Exception("not Bipartite");

return color[v];

}

public IEnumerable<int> OddCycle()

{

return cycle;

}

public bool IsBipartiteCheck(Graph G)

{

for (int v = 0; v < G.V; v++)

{

foreach (var w in G.adj[v])

{

if (color[w] == color[v]) return false;

}

return true;

}

private void ValidateVertex(int v)

{

int V = marked.Length;

if (v < 0 || v >= V) throw new ArgumentException("wrong vertex");

}

SymbolGraph

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphBasics
{
    public class SymbolGraph
    {
        private Dictionary<string, int> d;
        private string[] keys; // index  -> string
        private Graph G; // the underlying graph
        public SymbolGraph(string filepath, char delimiter)
        {
            d = new Dictionary<string, int>();
            try
            {
                using (StreamReader sr = new StreamReader(filepath))
                {
                    while (sr.Peek() >= 0)
                    {
                        string s = sr.ReadLine();
                        string[] substrings = s.Split(delimiter);
                        foreach (var substring in substrings)
                        {
                            if (!d.ContainsKey(substring))
                                d.Add(substring, d.Count);
                        }
                    }
                }
            }
            catch (Exception e) { Console.WriteLine(e.Message); }
            // inverted index
            keys = new string[d.Count];
            foreach (KeyValuePair<string, int> entry in d)
                keys[entry.Value] = entry.Key;
            // graph
            G = new Graph(d.Count);
            try
            {
                using (StreamReader sr = new StreamReader(filepath))
                {
                    while (sr.Peek() >= 0)
                    {
                        string s = sr.ReadLine();
                        string[] substrings = s.Split(delimiter);
                        int v = d[substrings[0]];
                        int w = d[substrings[1]];
                        /*
                        // or more universal
                        for (var i = 1; i < substrings.Length; i++)
                        {
                            int w = d[substrings[i]];
                        }
                        */
                        G.AddEdge(v, w);
                    }
                }
            }
            catch (Exception e) { Console.WriteLine(e.Message); }
        }
        /**
* Does the graph contain the vertex named {@code s}?
* @param s the name of a vertex
* @return {@code true} if {@code s} is the name of a vertex, and {@code false} otherwise
*/
        public bool Contains(String s)
        {
            // return d.FirstOrDefault(x => x.Key == s).Key!=null; //st.contains(s);
            return d.ContainsKey(s); //st.contains(s);
        }
        /**
* Returns the integer associated with the vertex named {@code s}.
* @param s the name of a vertex
* @return the integer (between 0 and <em>V</em> - 1) associated with the vertex named {@code s}
*/
        public int IndexOf(String s)
        {
            return d.FirstOrDefault(x => x.Key == s).Value;
        }
        /**
* Returns the name of the vertex associated with the integer {@code v}.
* @param  v the integer corresponding to a vertex (between 0 and <em>V</em> - 1) 
* @throws IllegalArgumentException unless {@code 0 <= v < V}
* @return the name of the vertex associated with the integer {@code v}
*/
        public String nameOf(int v)
        {
            //validateVertex(v);
            return keys[v];
        }
        /**
* Returns the graph assoicated with the symbol graph. It is the client's responsibility
* not to mutate the graph.
* @return the graph associated with the symbol graph
*/
        public Graph GetGraph()
        {
            return G;
        }
        private void validateVertex(int v)
        {
            int V = G.V;
            if (v < 0 || v >= V)
                throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }
        public string toString()
        {
            StringBuilder s = new StringBuilder();
            s.Append(G.V + " vertices, " + G.E + " edges " + "\n");

            for (int v = 0; v < G.V; v++)
            {
                s.Append(nameOf(v) + ": ");
                foreach (int w in G.adj[v])
                {
                    s.Append(nameOf(w) + " ");
                }
                s.Append("\n");
            }
            return s.ToString();
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

public class SymbolGraph

{

private Dictionary<string, int> d;

private string[] keys; // index -> string

private Graph G; // the underlying graph

public SymbolGraph(string filepath, char delimiter)

{

d = new Dictionary<string, int>();

try

{

using (StreamReader sr = new StreamReader(filepath))

{

while (sr.Peek() >= 0)

{

string s = sr.ReadLine();

string[] substrings = s.Split(delimiter);

foreach (var substring in substrings)

{

if (!d.ContainsKey(substring))

d.Add(substring, d.Count);

}

catch (Exception e) { Console.WriteLine(e.Message); }

// inverted index

keys = new string[d.Count];

foreach (KeyValuePair<string, int> entry in d)

keys[entry.Value] = entry.Key;

// graph

G = new Graph(d.Count);

try

{

using (StreamReader sr = new StreamReader(filepath))

{

while (sr.Peek() >= 0)

{

string s = sr.ReadLine();

string[] substrings = s.Split(delimiter);

int v = d[substrings[0]];

int w = d[substrings[1]];

// or more universal

for (var i = 1; i < substrings.Length; i++)

{

int w = d[substrings[i]];

}

G.AddEdge(v, w);

}

catch (Exception e) { Console.WriteLine(e.Message); }

}

/**

* Does the graph contain the vertex named {@code s}?

* @param s the name of a vertex

* @return {@code true} if {@code s} is the name of a vertex, and {@code false} otherwise

public bool Contains(String s)

{

// return d.FirstOrDefault(x => x.Key == s).Key!=null; //st.contains(s);

return d.ContainsKey(s); //st.contains(s);

}

/**

* Returns the integer associated with the vertex named {@code s}.

* @param s the name of a vertex

* @return the integer (between 0 and <em>V</em> - 1) associated with the vertex named {@code s}

public int IndexOf(String s)

{

return d.FirstOrDefault(x => x.Key == s).Value;

}

/**

* Returns the name of the vertex associated with the integer {@code v}.

* @param v the integer corresponding to a vertex (between 0 and <em>V</em> - 1)

* @throws IllegalArgumentException unless {@code 0 <= v < V}

* @return the name of the vertex associated with the integer {@code v}

public String nameOf(int v)

{

//validateVertex(v);

return keys[v];

}

/**

* Returns the graph assoicated with the symbol graph. It is the client's responsibility

* not to mutate the graph.

* @return the graph associated with the symbol graph

public Graph GetGraph()

{

return G;

}

private void validateVertex(int v)

{

int V = G.V;

if (v < 0 || v >= V)

throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));

}

public string toString()

{

StringBuilder s = new StringBuilder();

s.Append(G.V + " vertices, " + G.E + " edges " + "\n");

for (int v = 0; v < G.V; v++)

{

s.Append(nameOf(v) + ": ");

foreach (int w in G.adj[v])

{

s.Append(nameOf(w) + " ");

}

s.Append("\n");

}

return s.ToString();

}

C#. Undirected Graph Basics Altogether

MY PROJECTS

Recent Posts

Categories