[C #] Utilizzo di strutture Dictionary

[LS1987]

Buonasera, sto realizzando un programma in C # in cui devo salvare gli elementi all'interno di un Dizionario di tipo Dictionary<KeyValueTriple<int, int, double>, double> , che rappresenta gli archi di un grafo, dove KeyValueTriple è un tipo di dato che ho realizzato io, di seguito fornirò il codice. Il codice che posto è (molto) liberamente ispirato ad un pezzo di codice open source, dell'Università dell'Arizona, serve che posti anche le note di copyright? Utilizzo un oggetto KeyValueTriple, perché ci possono essere più archi con peso diverso che partono dal nodo i e arrivano al nodo j.
Fino a che utilizzavo al posto di un KeyValueTriple un KeyValuePair, tipo predefinito, non riscontravo problemi di nessun genere, cancellavo le chiavi dal dizionario senza alcun problema, passando ai KeyValueTriple inizio a non riuscire più a rimuovere gli elementi nel modo corretto, il risultato sia della remove che della remove_edge dà sempre false, nonostante gli passi un elemento che appartiene al dizionario, verificato, stampando tutti gli elementi.
Per semplificare ho realizzato un programma di tipo ConsoleApplication, non ho fatto un'interfaccia grafica, è soltanto un programma di base, anche perché il resto non potrei comunque postarlo.
Teoricamente se non ci fossero alternative, potrei risolverlo ricrendo un nuovo dizionario con tutti gli elementi tranne quello che deve essere rimosso, ma ovviamente non è la soluzione migliore, visto che sarebbe piuttosto inefficiente, oppure ancora posso cambiare la struttura dati utilizzata, ma dovrei cambiare un buon numero di righe di codice del resto del programma, e sinceramente vorrei evitarlo.

Struttura dati del grafo:



graph.cs

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


namespace ConsoleApplication2
{
public class Graph
{
public static double DISCONNECTED;

// index for edge weights in the graph
public Dictionary<KeyValueTriple<int, int, double>, double> _vertex_pair_weight_index;

// the number of arcs in the graph
public int _edge_num;

/**
* Constructor 1
* @param data_file_name
*/
public Graph(string data_file_name)
{
DISCONNECTED = double.MaxValue;

// index for edge weights in the graph
_vertex_pair_weight_index = new Dictionary<KeyValueTriple<int, int, double>, double>();

// the number of arcs in the graph
_edge_num = 0;

import_from_file(data_file_name);
}

/**
* Constructor 2
*
* @param graph
*/
public Graph(Graph graph_)
{
DISCONNECTED = double.MaxValue;

// index for edge weights in the graph
_vertex_pair_weight_index = new Dictionary<KeyValueTriple<int, int, double>, double>(graph_._vertex_pair_weight_index);

// the number of arcs in the graph
_edge_num = graph_._edge_num;
}

/**
* Default constructor
*/
public Graph()
{
DISCONNECTED = double.MaxValue;

// index for edge weights in the graph
_vertex_pair_weight_index = new Dictionary<KeyValueTriple<int, int, double>, double>();

// the number of arcs in the graph
_edge_num = 0;
}

/**
* Clear members of the graph.
*/
public void Clear()
{
_edge_num = 0;
_vertex_pair_weight_index.Clear();
}

/**
* There is a requirement for the input graph.
* The ids of vertices must be consecutive.
*
* @param data_file_name
*/
public void import_from_file(string data_file_name)
{
try
{
// 1. read the file and put the content in the buffer
TextReader bufRead = new StreamReader(data_file_name);

bool is_first_line = true;
string line; // String that holds current file line

// 2. Read first line
line = bufRead.ReadLine();
while (line != null)
{
// 2.1 skip the empty line
if (line.Trim().Equals(""))
{
line = bufRead.ReadLine();
continue;
}

// 2.2 generate nodes and edges for the graph
if (is_first_line)
{
//2.2.1 obtain the number of nodes in the graph

is_first_line = false;

}
else
{
//2.2.2 find a new edge and put it in the graph
string[] str_list = line.Trim().Split('\r', '\n', '\t', ' ');

int start_vertex_id = int.Parse(str_list[0]);
int end_vertex_id = int.Parse(str_list[1]);
double weight = double.Parse(str_list[2]);
add_edge(start_vertex_id, end_vertex_id, weight);
}
//
line = bufRead.ReadLine();
}
bufRead.Close();

}
catch (IOException e)
{
// If another exception is generated, print a stack trace
Console.Write(e.Message);
}
}

/**
* Note that this may not be used externally, because some other members in the class
* should be updated at the same time.
*
* @param start_vertex_id
* @param end_vertex_id
* @param weight
*/
public void add_edge(int start_vertex_id, int end_vertex_id, double weight)
{
// actually, we should make sure all vertices ids must be correct.
if (start_vertex_id == end_vertex_id)
{
throw new System.ArgumentOutOfRangeException("The edge from " + start_vertex_id
+ " to " + end_vertex_id + " does not exist in the graph.");
}

// store the new edge
_vertex_pair_weight_index.Add(new KeyValueTriple<int, int, double>(start_vertex_id, end_vertex_id, weight),
weight);

++_edge_num;
}


}

public class VariableGraph : Graph
{
HashSet<KeyValueTriple<int, int, double>> _rem_edge_set;

/**
* Default constructor
*/
public VariableGraph()
{
_rem_edge_set = new HashSet<KeyValueTriple<int, int, double>>();
}

/**
* Constructor 1
*
* @param data_file_name
*/
public VariableGraph(string data_file_name)
: base(data_file_name)
{
_rem_edge_set = new HashSet<KeyValueTriple<int, int, double>>();
}

/**
* Constructor 2
*
* @param graph
*/
public VariableGraph(Graph graph)
: base(graph)
{
_rem_edge_set = new HashSet<KeyValueTriple<int, int, double>>();
}

/**
* Add an edge to the set of removed edges
*
* @param edge
*/
public void remove_edge(KeyValueTriple<int, int, double> edge)
{
Console.WriteLine("I'M REMOVING AN EDGE <" + edge.key1 + "," + edge.key2 + "," + edge.value + "> -> " + edge.value);
_rem_edge_set.Add(edge);
bool esito = _vertex_pair_weight_index.Remove(edge);
Console.WriteLine("Esito della rimozione, remove_edge : " + esito);
if (_vertex_pair_weight_index.ContainsKey(edge))
Console.WriteLine("L'ARCO E' ANCORA PRESENTE\n");
_vertex_pair_weight_index.Add(edge, DISCONNECTED);
}

public void recover_removed_edges()
{
_rem_edge_set.Clear();
}

public void recover_removed_edge(KeyValueTriple<int, int, double> edge)
{
Console.WriteLine("I'M RECOVERING A REMOVED EDGE <" + edge.key1 + "," + edge.key2 + "," + edge.value + "> -> " + edge.value);
bool esito = _rem_edge_set.Remove(edge);
Console.WriteLine("Esito della rimozione recover_removed_edge: " + esito);
if (_rem_edge_set.Contains(edge))
Console.WriteLine("L'ARCO E' ANCORA VIRTUALMENTE NON RIPRISTINATO\n");
_vertex_pair_weight_index.Add(edge, DISCONNECTED);
}
}

//tripla da utilizzare all'interno del dizionario
public class KeyValueTriple<TKey1, TKey2, TValue>
{
public TKey1 key1;
public TKey2 key2;
public TValue value;

public KeyValueTriple(TKey1 key1, TKey2 key2, TValue value)
{
this.key1 = key1;
this.key2 = key2;
this.value = value;
}

public TKey1 getKey1()
{
return key1;
}

public TKey2 getKey2()
{
return key2;
}

public TValue getValue()
{
return value;
}

public override bool Equals(System.Object obj)
{
if (obj == null) return false;
KeyValueTriple<int, int, double> k = new KeyValueTriple<int, int, double>(1, 1, 1.0); //serve per avere il tipo
Type t = k.GetType();
if (obj.GetType() != t)
{
throw new InvalidCastException("L'oggetto passato non è del tipo corretto\n");
}
KeyValueTriple<TKey1, TKey2, TValue> kvt = (KeyValueTriple<TKey1, TKey2, TValue>)obj;
if ((this.key1.Equals(kvt.key1)) && (this.key2.Equals(kvt.key2)) && (this.value.Equals(kvt.value)))
return true;
return false;
}

public override int GetHashCode()
{
return base.GetHashCode();
}
}
}



main:



program.cs

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

namespace ConsoleApplication2
{
class Program
{
static VariableGraph vg = new VariableGraph("test_7");
static void printAll()
{
Dictionary<KeyValueTriple<int, int, double>, double> dic2 = vg._vertex_pair_weight_index;
foreach (KeyValuePair<KeyValueTriple<int, int, double>, double> kvp in dic2)
{
KeyValueTriple<int, int, double> kvt = kvp.Key;
KeyValueTriple<int, int, double> kvtCopy = new KeyValueTriple<int, int, double>(kvt.key1, kvt.key2, kvt.value);
double value = kvp.Value;
Console.WriteLine("<" + kvt.key1 + "," + kvt.key2 + "," + kvt.value + " > " + value + " -> " + " equals : " + kvt.Equals(kvtCopy));
}
}

static void Main(string[] args)
{
Dictionary<KeyValueTriple<int, int, double>, double> dic = vg._vertex_pair_weight_index;
printAll();
vg.remove_edge(new KeyValueTriple<int, int, double>(1, 3, 3.0));
Console.WriteLine("-------------------------------");
printAll();
vg.recover_removed_edge(new KeyValueTriple<int, int, double>(1, 3, 3.0));
Console.WriteLine("-------------------------------");
printAll();
Console.ReadLine();
}
}
}


file di input degli archi del grafo:



test_7

7

0 1 1
1 0 1
0 2 7
2 0 7
1 2 1
2 1 1
1 3 3
1 3 4
3 1 3
1 4 2
4 1 2
2 4 4
4 2 4
3 5 6
5 3 6
3 4 1
4 3 1
4 5 2
5 4 2
3 6 100
6 3 100
6 1 1
1 6 1

[LS1987]

Up!

[gugoXX]

Implementa l'interfaccia IEquatable<KeyValueTriple>
(Per questioni di chiarezza e pulizia)

E scrivi un GetHashCode che abbia un senso, non il semplice

public override int GetHashCode()
{
return base.GetHashCode();
}

Il tuo hashcode deve dipendere dagli hascode degli elementi che compongono la chiave, in questa classe tutti e 3 gli elementi.
Il criterio e' che oggetti uguali devono avere lo stesso hashcode.

Richiamare l'hashcode base e' il problema principale.
2 oggetti (object), anche se hanno contenuti uguali avranno hashcode diverso, perche' la object.GetHashCode restituisce l'indirizzo di memoria, che e' appunto diverso in 2 istanze diverse, quand'anche uguali in contenuto.
Per quello che non trovi gli elementi nella Dictionary, anche se apparentemente presenti.

Quindi prima approssimazione metti
Key1.GetHashCode() + Key2.GetHashCode() + Key3.GetHashCode()
Meglio sarebbe cucinare per qualche fattore primo moltiplicativo per evitare quanto piu' possibile overlapping di valori tra oggetti diversi che avranno invece stessa HashCode (Che non e' vietato, solo meno efficiente)

[LS1987]

Implementa l'interfaccia IEquatable<KeyValueTriple>
(Per questioni di chiarezza e pulizia)

E scrivi un GetHashCode che abbia un senso, non il semplice

public override int GetHashCode()
{
return base.GetHashCode();
}

Il tuo hashcode deve dipendere dagli hascode degli elementi che compongono la chiave, in questa classe tutti e 3 gli elementi.
Il criterio e' che oggetti uguali devono avere lo stesso hashcode.

Richiamare l'hashcode base e' il problema principale.
2 oggetti (object), anche se hanno contenuti uguali avranno hashcode diverso, perche' la object.GetHashCode restituisce l'indirizzo di memoria, che e' appunto diverso in 2 istanze diverse, quand'anche uguali in contenuto.
Per quello che non trovi gli elementi nella Dictionary, anche se apparentemente presenti.

Quindi prima approssimazione metti
Key1.GetHashCode() + Key2.GetHashCode() + Key3.GetHashCode()
Meglio sarebbe cucinare per qualche fattore primo moltiplicativo per evitare quanto piu' possibile overlapping di valori tra oggetti diversi che avranno invece stessa HashCode (Che non e' vietato, solo meno efficiente)

Ti ringrazio, ho aggiunto il metodo Equals che estende quello di IEquatable<KeyValueTriple<TKey1, TKey2, TValue>> e ho aggiustato GetHashCode


public override bool Equals(KeyValueTriple<TKey1, TKey2, TValue> obj)
{
if (obj == null) return false;
if ((this.key1.Equals(obj.key1)) && (this.key2.Equals(obj.key2)) && (this.value.Equals(obj.value)))
return true;
return false;
}

public override int GetHashCode()
{
if ((key1 == null) || (key2 == null) || (value == null))
throw new NullReferenceException("Arguments null");
return key1.GetHashCode() + key2.GetHashCode() + value.GetHashCode();
}


Adesso non ho fissato dei valori moltiplicatori, ma non mi interessa anche se è meno efficiente, per ora vorrei risolvere i problemi.

Mi viene restituito l'errore "Error 1 'ConsoleApplication3.KeyValueTriple<TKey1,TKey2,TValue>.Equals(ConsoleApplication3.KeyValueTriple<TKey1,TKey2,TValue>)': no suitable method found to override"

Eppure dovrebbe effettuare l'override del metodo Equals di IEquatable<KeyValueTriple<TKey1, TKey2, TValue>> L'override del metodo Equals di Object viene effettuata senza problemi, ho anche provato a toglierla, per vedere se ci sono dei conflitti, ma non riesco a risolvere.

Per il resto il programma funziona, anche senza effettuare l'override del metodo Equals.

[gugoXX]

Bene la GetHashcode(), che era di fatto il tuo problema.

Per quanto riguarda la "Equals", togli semplicemente la keyword "override"

Non stai facendo override di quel metodo. Stai implementando un contratto di interfaccia, che non ha bisgno di override, perche' di fatto non esiste un metodo base, in quanto le interfaccie non hanno body.